组合数奇偶的判定

众所周知，根据组合数的定义，\(C^m_n=\frac{n!}{m!(n-m)!}\)

设\(n!,m!,(n-m)!\)的\(2\)的因子个数为\(x,y,z\)，显然当且仅当\(x=y+z\)时，组合数为奇数。

对于一个质数\(p\)，它在\(n!\)中的因子个数为：

\(\lfloor\frac{n}{p}\rfloor+\lfloor\frac{n}{p^2}\rfloor+\lfloor\frac{n}{p^3}\rfloor+\lfloor\frac{n}{p^4}\rfloor+...\)

设对于\(n!\)来说它的\(2\)的因子个数是\(f(n)\)，则

\(f(n)=\)\(\lfloor\frac{n}{2}\rfloor+\lfloor\frac{n}{2^2}\rfloor+\lfloor\frac{n}{2^3}\rfloor+\lfloor\frac{n}{2^4}\rfloor+...\)

又因为\(n=(a_0\times2^0)+(a_1\times 2^1)+(a_2\times 2^2)+...+(a_k\times 2^k)\)

因此可以化简\(f(n)\)的表达式为：

\[f(n)=\sum_{i=0}^{k}\lfloor \frac{(a_0\times2^0)+(a_1\times 2^1)+(a_2\times 2^2)+...+(a_k\times 2^k)}{2^i}\rfloor\]

\[=\sum_{i=0}^{k}\lfloor \frac{(a_i\times2^i)+...+(a_k\times 2^k)}{2^i}\rfloor\]

\[=\sum_{i=0}^k\sum_{j=i+1}^k\frac{a_j\times 2^j}{2^i}\]

\[=\sum_{i=0}^ka_i\sum^{i-2}_{j=0}2^j\]

\[=\sum^k_{i=0}a_i \times(2^i-1)\]

\[=\sum_{i=0}^{k}a_i\times 2^i-\sum_{i=0}^k a_i\]

\[=n-\sum_{i=0}^k a_i\]

如何快速求出\(\sum_{i=0}^k a_i\)？显然它等于\(n\)在2进制下1的个数。

所以，\(f(n)=n-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\)。