二項係数(nCk)の偶奇判定のアルゴリズム

2020年3月22日数学剰余,二項係数,Lucasの定理,素数の剰余,偶奇性

Lucasの定理を利用することで、二項係数(nCk) が偶数なのか奇数なのかを効率よく判定することができます。

アルゴリズム

Lucasの定理をそのまま利用したアルゴリズム:

  • \({}_{n_i}\mathrm{C}_{k_i}\:(\mathrm{mod}\:2)\) の計算法:
    1. \({}_{i}\mathrm{C}_{j} = {}_{i-1}\mathrm{C}_{j-1}+{}_{i-1}\mathrm{C}_{j} \) を利用して計算(動的計画法)
  • メイン:
    1. \(_{n}\mathrm{C}_{k} \equiv \prod_{i=0}^m{}_{n_i}\mathrm{C}_{k_i}\:(\mathrm{mod}\:2)\) を計算する

※ Lucasの定理を利用すると、二項係数(nCk)を素数(p)で割った余りの計算ができます。詳しくはこちらを参照

効率的なアルゴリズム:

  1. 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 の定理を利用して示します。

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 が真なら奇数・偽なら偶数になります。

練習問題