组合数奇偶的判定

众所周知，根据组合数的定义，$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$。