nCkの偶奇

nCkの偶奇はlucasの定理から(n&k)==kで判定できるというのをTLで見かけたので調べた。

mathtrain.jp

C(0,0) = 1, C(0,1) = 0, C(1,0) = 1, C(1,1) = 1 となるので n_i = 0 で k_i = 1となるiがあれば偶数、なければ奇数となる。

n k n&k
0 0  0
0 1  0
1 0  0
1 1  1

より (n&k) != kのときのみ n_i = 0 で k_i = 1となるiが存在する。

よって、(n&k) == k であれば nCkは奇数、(n&k) != k であれば nCkは偶数となる。