Skip to content →

リュカの定理 : 二項係数の偶奇

リュカの定理(Lucas’s theorem):\(A\) の \(p\) 進数表示の \(k\) 桁目を \(A^{(k)}\) とすると、$${n \choose m} = \prod {n^{(i)} \choose m^{(i)}} \pmod p$$ となる。
証明:\(p\) を素数とすると、フロベニウス写像より
$$(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)\) で偶奇が分かる。

演習問題

\({n \choose 0}, \ldots, {n \choose k}\) に何個の奇数が含まれるか、\(O(\log(n))\) で求めよ。

解答 : 桁DP

\(N\) 個の相異なる整数 \(a_1, \ldots, a_N\) からなる列がある。長さ \(k\) の整数であって、各数が \(a\) の項のいずれかであり、総和が \(s\) であるものの個数を \(O(k \max (a_i)\log N)\) で求めよ。(出典 : GP of Tokyo G)

解答 : 多変数のリュカの定理より \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}\) と合わせると、問題文の計算量になる。

\(\sum_{K=a \ \dot\cup \ b} \sum_{L=c \ \dot\cup \ d} 1 \) を \(O(1)\) で求めよ。(出典:yukicoder1531)

解答 : \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}

\(\sum_{i=0}^k { m+k-i \choose k-i}a_i\) の偶奇を \(m=0,1,\ldots,M\) について列挙せよ。(ARC137D)

解答 : リュカの定理を用いると次のようになる。\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\) は全体集合。これは、高速ゼータ変換により求まる。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA