$$(1+x)^{p} = 1+x^p \pmod p$$である。これを繰り返すと、$$(1+x)^{p^e} = 1+x^{p^e} \pmod p$$である。従って、\(A\) の \(p\) 進数表示の \(k\) 桁目を \(A^{(k)}\) とすると、
$$(1+x)^{n} = \prod(1+x^{p^i})^{n^{(i)}} \pmod p$$となり、二項展開することで、$${n \choose m} = \prod {n^{(i)} \choose m^{(i)}} \pmod p$$ となる。
\(p=2\) のときの別証明：\(n\) を \(2\) で割り切れる回数 \(v_2(n)\) は
\begin{align}
v_2(n) &= \sum_{i=1}^\infty \left\lfloor \frac{n}{2^i} \right\rfloor\\
&= -|n|+\sum_{i=1}^\infty \frac{n}{2^i}\\
&= -|n| + n
\end{align}である（\(|\cdot|\)はbitCount）。従って、
\begin{align}
{n \choose k} \text{ is odd} & \Leftrightarrow v_2\left({n \choose k}\right)=0 \\
&\Leftrightarrow n-|n|-k+|k|-(n-k)+|n-k|=0 \\
&\Leftrightarrow |n|=|k|+|n-k| \\
&\Leftrightarrow n = (n-k) \ \dot\cup \ k
\end{align} となる（別証明終わり）。
リュカの定理は多変数の場合に一般化できて、
$$(x_1+x_2+\ldots+x_e)^{n} = \prod(x_1^{p^i}+x_2^{p^i}+\ldots+x_e^{p^i})^{n^{(i)}} \pmod p$$より、二項展開することで、$${n \choose {m_1, \ldots, m_e}} = \prod {n^{(i)} \choose m_1^{(i)}, \ldots, m_e^{(i)}} \pmod p$$ となる。p = 2 のときは
$${ n \choose m_1, m_2, \ldots, m_e} \text{ is odd} \Leftrightarrow n = m_1\ \dot\cup\ m_2\ \dot\cup\ \cdots\ \dot\cup\ m_e$$となる。特に、\(e=2\) のときは、\(n = m \ \dot\cup\ (n-m) \Leftrightarrow m \subset n\) だから n&m==m により \(O(1)\) で偶奇が分かる。
演習問題
解答 : 桁DP
解答 : 多変数のリュカの定理より \begin{align}
&\sum_{s=\sum m_ia_i} {k \choose m_1, m_2, \ldots, m_e} \\
=&\left|\left\{(m_i):s=\sum m_ia_i, k=m_1 \ \dot\cup\ m_2\ \dot\cup\ \cdots \ \dot\cup\ m_e \right\}\right|
\end{align}である。kのbitが立っている部分をどの \(a_i\) に割り振るかで dp する。i bit 目まで決めたとする。残り足されるのは \(2^{i+1}\) の倍数のみだから、この時点で \(\bmod 2^{i+1}\) が \(s\) と一致していなければならない。\(1+2+\cdots+2^i<2^{i+1}\) と合わせると、問題文の計算量になる。
解答 : \begin{align}
\sum_{K=a \ \dot\cup \ b} \sum_{L=c \ \dot\cup \ d} 1 & = \sum_i {K \choose i} \bmod 2 \sum_j {L \choose j} \bmod 2\\
& = \sum_i \left({{K+L} \choose i } \bmod 2\right)\\
& = \sum_{K+L = a \ \dot\cup \ b} 1 \\
&= 2^{|K+L|}
\end{align}
解答 : リュカの定理を用いると次のようになる。\begin{align}
{ m+k-i \choose k-i} \text{ is odd} &\Leftrightarrow m+k-i=m \ \dot\cup\ (k-i) \\
& \Leftrightarrow m \cap\ (k-i) = \emptyset
\end{align}最後の同値変形は下の桁から決定すれば分かる。これを用いると、求める式は
\begin{align}
\sum_{i=0}^k { m+k-i \choose k-i}a_i &= \sum_{m \cap\ (k-i) = \emptyset}a_i \\
&= \sum_{m \cap\ i = \emptyset}a_{k-i}\\
&= \sum_{(U-m) \supset\ i}a_{k-i}
\end{align}となる。ただし、\(U\) は全体集合。これは、高速ゼータ変換により求まる。
フロベニウス写像
リュカの定理はフロベニウス写像が本質であった。他にも計算を効率的にする場合を見ていく。
二項係数の和
\(A\) の \(p\) 進数表示の \(k\) 桁目を \(A^{(k)}\) とする。
次の計算
\begin{align}
&[x^{q_1p+r_1}](1+x)^{q_2p+r_2} \frac{1}{1-x} \\
=&[x^{q_1p}](1+x)^{q_2p}\left(\sum_{i=0}^{r_1} {r_2 \choose i} + \frac{2^{r_2}x^p}{1-x^p} \right)
\end{align}
により \(O(p^2)\) の前計算により \(\sum_{i=0}^m {n \choose i}\) が \(O(\log n / \log p)\) で求まる。kyopro_friendsさんは \(O(\sqrt{n}+p)\) の前計算、クエリ \(O(1)\) で求めている。
XOR ピラミッド
（dwacon2018-final-c）\(f(x) = 1 + x + x^2\) と置く。\(\bmod 2\) の下、
\begin{align}
&[x^m]f(x)^{2n+1} \frac{1}{1-x} \\
=&[x^m]f(x)^{2n} \frac{1+x+x^2}{1-x} \\
=&[x^m]f(x)^{2n} \frac{1+x^3}{1-x^2} \\
=&\left([x^{m/2}]+[x^{(m-3)/2}]\right)f(x^2)^{n} \frac{1}{1-x} \\
\end{align}
である。同様に、
\begin{align}
&[x^m]f(x)^{2n} \frac{1}{1-x} \\
=&[x^m]f(x^2)^{n} \frac{1+x}{1-x^2} \\
=&\left([x^{m/2}]+[x^{(m-1)/2}]\right)f(x)^{n} \frac{1}{1-x} \\
\end{align}である。\(x\) と \(x-1, x-3\) の偶奇は異なるので、\(O(\log n)\) で求まる。
Comments