组合数可以表示为
[C^m_n = frac{n!}{m!(n-m)!}
]
假设(n!,m!,(n-m)!)含因子(2)的个数分别为(A,B,C)
则当(A=B+C)时，(C^m_n)为奇数
那么如何求出(n!)的因子个数呢？
对于一个质数(p)，
它的倍数(k*p^i)含因子(p)的个数为即为(i(k=1,2,3...))
于是只要求出(n!)中所有的(k*p^i)即可，
则(n!)含因子(p)的个数为
[lfloor frac{n}{p} + frac{n}{p^2} + frac{n}{p^3} + frac{n}{p^4} + ...
floor
]
所以(n!)含因子(2)的个数为
[f(n) = lfloor frac{n}{2} + frac{n}{2^2} + frac{n}{2^3} + frac{n}{2^4} + ...
floor
]
其中，可以将(n)表示为二进制拆分的形式：
[n = (a_1*2^0)+ (a_2*2^1)+ (a_3*2^2)+ (a_4*2^3)+...
]
则(f(n))就可以表示成
[f(n) = sum limits_{j=1}^{k} frac{(a_1*2^0)+(a_2*2^1)+...+ (a_k*2^{k-1})}{2^j}
]
将式子简化
[= sum limits_{j=1}^{k} frac{(a_{j-1}*2^j)+...+ (a_k*2^{k-1})}{2^j}
]
[= sum limits_{j=1}^{k} sum limits_{i=j+1}^{k} frac{a_{i}*2^{i-1}}{2^j}
]
[= sumlimits_{i=1}^{k} a_i sumlimits_{j=1}^{i-1} frac{2^{i-1}}{2^j}
]
[= sumlimits_{i=1}^{k} a_i sumlimits_{j=0}^{i-2} 2^j
]
[= sumlimits_{i=1}^{k} a_i * (2^{i-1} - 1)
]
[= sumlimits_{i=1}^{k} a_i * 2^{i-1} - sumlimits_{i=1}^{k} a_i
]
[= n - sumlimits_{i=1}^{k} a_i
]
观察这个式子，可以发现
[sumlimits_{i=1}^{k} a_i = n在二进制下1的个数
]
设(n,m,(n-m))在二进制下(1)的数目分别为(a,b,c)
要满足(A=B+C)，则：
[n−a=m−b+(n−m)−c
]
[a=b+c
]
要满足这个条件则有
[(n&m) == m
]