Ex - Fill Triangle Editorial by Nyaan
問題の解説に入る前に、二項係数 \(\binom{n}{r} \bmod p\) に関するいくつかの性質を取り上げたいと思います。
\(\binom{p^k}{n} \bmod{p}\)
任意の素数 \(p\) および正整数 \(k\) について以下の式が成り立つ。
\[(x+1)^{p^k} \equiv x^{p^k} + 1 \pmod{p}\]
言い換えると、整数 \(i\) \((0 \leq i \leq p^k)\) について次の事実が成り立つ。
\[\binom{p^k}{n} \bmod p = \begin{cases} 1 & n = 0, p^k \\ 0 & \mathrm{otherwise} \end{cases}\]
(証明) 数学的帰納法を用います。
\(k=1\) のとき、明らかに \(\binom{p}{0}=\binom{p}{p}=1\) です。また、\(1 \leq n \leq p-1\) のとき
\[\binom{p}{n} = \frac{p(p-1) \cdots (p-n+1) }{n!}\]
で分母は \(p\) で割り切れないので \(\binom{p}{n} \equiv 0 \pmod{p}\) です。
\(m \geq 1\) について \(k = m\) のとき命題が成り立つとします。このとき \(k = m+1\) の場合は \(k=m\) の場合を用いて
\[ (x+1)^{p^{m+1}}\equiv ((x+1)^{p^m})^p\equiv (x^{p^m} + 1)^p \pmod{p} \]
と変形できるので \(k=1\) の場合と同様に示せます。(証明終わり)
また、より発展的な定理として、 \(\binom{N}{k}\) が \(p\) で割り切れる回数をクンマーの定理によって計算することができます。
リュカの定理
非負整数 \(n,k\) を \(p\) 進表記したとき以下のように表されるとする。
\[n = a_r p^r + \cdots + a_1 p + a_0\]
\[k = b_r p^r + \cdots + b_1 p + b_0\]
このとき次の式が成り立つ。
\[\binom{n}{k} \equiv \prod_{i=0}^r \binom{a_i}{b_i} \pmod p\]
証明は \((1+x)^n\) を先に示した定理を利用して式変形を進めればよいです。
\[ \begin{aligned} &[x^k] (1+x)^n \\ &\equiv [x^k]\prod_{i=0}^r ((1+x)^{p^i})^{a_i} \\ &\equiv [x^k]\prod_{i=0}^r (1 + x^{p^i})^{a_i} \\ &\equiv \prod_{i=0}^r [x^{p^i b_i}](1 + x^{p^i})^{a_i}\\ &\equiv \prod_{i=0}^r \binom{a_i}{b_i} \end{aligned} \]
- 余談ですが、\(\binom{p^k}{n} \bmod{p}\) やリュカの定理は大学入試の数論に関する問題やその背景としてしばしば登場しています。高校生以下の AtCoder 参加者の皆さんはこの機会に上の話を理解しておくと学業に役立つかも？
二項係数 \(\text{mod }2\) とフラクタル
元の問題の話からは逸れますが、リュカの定理に関連してこのテーマを最近 AtCoder で見かけたので簡単に触れておきます。
リュカの定理を \(p=2\) に適用すると、二項係数 \(\text{mod }2\) は次のような式で表すことができます。 (\(\mathrm{AND}\) はビットごとの論理積)
\[\binom{n}{k} \bmod 2 = \begin{cases} 1 & n \text{ AND } k = k \\ 0 & \mathrm{otherwise} \end{cases}\]
また、これに関連して、パスカルの三角形の値が奇数の部分(すなわち二項係数 \(\text{mod }2\) が \(1\) になる部分)を塗りつぶすと、シェルピンスキーのギャスケットと呼ばれるフラクタル構造が出現します。これは \(n\) と \(k\) のビット積が偶奇に関連している性質から証明できます。
- 参考 : 高校数学の美しい物語(日本語), Wikipedia(英語)
さて、解説に入ります。
解法 1 ：\(p^k\) ずつ「ジャンプ」する解法
\(\binom{p^k}{n} \bmod{p}\) が \(n=0,p^k\) のときだけ \(1\) になる性質を使うと次の事実が言えます。
\[B_{i,j} \equiv B_{i+7^k,j} + B_{i+7^k,j+7^k} \pmod{7}\]
さて、\(i\) 段目を連長圧縮した列を \(R(i)\) と表します。このとき \(R(i+7^k)\) から \(R(i)\) は上の事実を用いると \(\mathrm{O}(|R(i+7^k)|)\) で計算できます。(以下ではこの遷移を「ジャンプ」と表現します)
そこで、値を連長圧縮した状態で管理したまま \(k\) の大きい方から \(7^k\) ずつジャンプしていきましょう。より形式的には、\(t\) を \(N-K \lt 7^t\) を満たす最小の整数として、次の疑似コードで表されるアルゴリズムを考えます。
// Calculate r = R(K)
r <- R(N)
n <- N
for i = t-1 to 0 do
while n - K >= 7^i do
r <- sequence jumping 7^i from r
n <- n - 7^i
end while
end for
計算量を解析しましょう。上のアルゴリズムの計算量は、各 while 文が終了した時点での \(r\) の長さの和の \(7\) 倍で抑えられるので、\(r\) の長さの上界を評価すればよいです。
ここで \(i = s\) のときの while 文が終了した時点での \(r\) の長さの上界について、次の 2 つのことが言えます。
- ジャンプ幅が変わらない間、連長圧縮した列のサイズは最大で \(7\) 倍にしかならないので、\(\mathrm{O}(M 7^{t-s})\) である。
- while 文が終了した時点で \(n \lt K + 7^s\) であり、\(r\) の長さはそれより小さい。よって \(\mathrm{O}(K + 7^s)\) である。
\(7^t = \mathrm{O}(N)\) なので、正の数 \(x\) について \(\min(\frac{MN}{x}, x + K)\) を評価できれば良く、これは常に \(\sqrt{MN} + K\) 以下であることが初等的に確認できます。よって上のアルゴリズムは \(\mathrm{O}((\sqrt{MN} + K) \log N)\) で動作します。
- より厳密に評価すると \(\Theta(\sqrt{MN} + K \log N)\) になって、\(M \leq 5000\) 程度の制約でもこの解法で解くことができます。
解法 2 ：リュカの定理を利用する解法
別解としてリュカの定理を用いる解法もあります。簡単に説明します。
\[B_{K,s} = \sum_{i=0}^{N-K} A_{s+i} \binom{N-K}{i}\]
を \(1 \leq s \leq K\) の範囲で列挙できればいいです。 以下では計算しやすいように \(P\) のかわりに \(Q_i = (a_{i}-a_{i+1}, \sum_{j\leq i}c_j)\) (ただし \(a_{M+1}=0\)) を満たす列 \(Q\) を使うと以下の式が成り立ちます。
\[B_{K,s} = \sum_{(a,c) \in Q} a \times \sum_{i=0}^{\min(N-K,c-s)}\binom{N-K}{i}\]
この式の
\[\sum_{i=0}^n \binom{N-K}{i}\]
の部分はリュカの定理 と (桁 DP or 再帰) を用いれば \(\mathrm{O}(\log N)\) で計算できるので、とりあえず \(\mathrm{O}(MK \log N)\) で計算できる形になりました。(このままでは TLE です)
さらに高速化します。上の式を差分更新しながら \(B_{K,s}\) を求めることを目指すと、詳細は略しますが、ある \(L,R\) に対して
\[\binom{N-K}{L}, \binom{N-K}{L+1},\dots, \binom{N-K}{R}\]
を高速に列挙する問題に帰着して、こちらもリュカの定理を使いつつ再帰を行うと \(\mathrm{O}(\log N + R - L)\) で計算できます。
結局、差分更新を用いれば全体で \(\mathrm{O}((M + \log N) K + M \log N)\) の計算量で計算できます。
posted:
last update: