二項係数(nCk)の偶奇判定のアルゴリズム
Lucasの定理を利用することで、二項係数(nCk) が偶数なのか奇数なのかを効率よく判定することができます。
アルゴリズム
Lucasの定理をそのまま利用したアルゴリズム：
- \({}_{n_i}\mathrm{C}_{k_i}\:(\mathrm{mod}\:2)\) の計算法：
- \({}_{i}\mathrm{C}_{j} = {}_{i-1}\mathrm{C}_{j-1}+{}_{i-1}\mathrm{C}_{j} \) を利用して計算（動的計画法）
- メイン：
- \(_{n}\mathrm{C}_{k} \equiv \prod_{i=0}^m{}_{n_i}\mathrm{C}_{k_i}\:(\mathrm{mod}\:2)\) を計算する
※ Lucasの定理を利用すると、二項係数(nCk)を素数(p)で割った余りの計算ができます。詳しくはこちらを参照
効率的なアルゴリズム：
- n と k の論理積が、k と一致すれば奇数、一致しなければ偶数となる。
つまり(n&k)==kが真なら奇数・偽なら偶数になる。
※ 後述しますが、Lucasの定理からこのアルゴリズムで良いことが分かります。
計算量
- Lucasの定理をそのまま利用したアルゴリズム：
- \(O(\log n)\)
- 効率的なアルゴリズム：
- \(O(1)\)
Lucas の定理をそのまま適用する場合は、\(n\) の桁数だけ計算が必要です。
C++ での実装例
Lucasの定理をそのまま利用
詳しくは、二項係数(nCk)を素数(p)で割った余りの計算（Lucas の定理） を見てください。
効率的なアルゴリズム
非常に簡潔に書くことができます。
bool is_nCk_odd(int n, int k){
return (n&k)==k;
}
アルゴリズムの正当性（ (n&k)==k で奇数となる理由）
Lucas の定理を利用して示します。
任意の素数 \(p\) と、非負整数 \(n, k\) について
$$ _{n}\mathrm{C}_{k} \equiv \prod_{i=0}^m{}_{n_i}\mathrm{C}_{k_i} \:(\mathrm{mod}\:p)$$
が成立する。ただし、
\begin{align}
n &= n_m p^m+ n_{m-1} p^{m-1} + n_{m-2} p^{m-2} + \cdots + n_1 p^1 + n_0 \\
k&= k_m p^m + k_{m-1} p^{m-1} + k_{m-2} p^{m-2} + \cdots + k_1 p^1 + k_0
\end{align}
である。（それぞれ \(p\) 進数で表した時の数。）
偶数か奇数かを判定したいので、\(p = 2 \) として考えれば良いです。
この時、以下のようになります。
- \(_{n_i}\mathrm{C}_{k_i}\) の値は以下の4通りのどれか
- \(_{1}\mathrm{C}_{0} = 1\)
- \(_{1}\mathrm{C}_{1} = 1\)
- \(_{0}\mathrm{C}_{0} = 1\)
- \(_{0}\mathrm{C}_{1} = 0\)
\(_{n_i}\mathrm{C}_{k_i}\) の値は 0 か 1 のみです。よって、Lucas の定理から、
- \(_{n}\mathrm{C}_{k} \equiv 0 \:(\mathrm{mod}\:2)\)：\(_{n_i}\mathrm{C}_{k_i}\) に1つでも 0 が含まれる
- \(_{n}\mathrm{C}_{k} \equiv 1 \:(\mathrm{mod}\:2)\) ：\(_{n_i}\mathrm{C}_{k_i}\) が全て 1
が成り立つことがわかります。
以上を合わせると、以下が全て同値です。
- \(_{n}\mathrm{C}_{k} \equiv 1 \:(\mathrm{mod}\:2)\)
- \(_{n_i}\mathrm{C}_{k_i}\) が全て 1
- \(n_i = 0\) かつ \(k_i=1\) となるような \(i\) が存在しない
- n と k の論理積が、k と一致する（もし違う桁が一つでもあれば、\(n_i = 0\) かつ \(k_i=1\) となってしまう）
ゆえに、 (n&k)==k が真なら奇数・偽なら偶数になります。
練習問題
- [AtCoder] AGC043 B – 123 Triangle：偶奇性に着目します