在 \(\text{dp}\) 专题的本题( Future Failure )中需要到了此结论,所以写一下
首先我们知道 \(\dbinom{m}{n}=\dfrac{n!}{m!(n-m)!}\)
假设 \(n!,m!,(n-m)!\) 的2因子个数均为 \(\text{A,B,C}\)
显然组合数为奇数时当且仅当 \(\text{A=B+C}\)
考虑 \(\text A\) 和 \(n!\) 的关系,对于一个质数 \(p\) 其在 \(n!\) 内的因数个数为
\[\sum_{p^i\le n}\lfloor\frac{n}{p^i}\rfloor \]这个是很明显的,我和 wang54321
一小会儿就推出来了,因此其因子 \(2\) 的个数为
对于 \(n\) 其可以表示为
\[n=\sum 2^{i-1}a_{i} \]那么我们可以把上面的式子进行化简
\[\begin{align} \sum_{p^i\le n}\lfloor\frac{n}{2^i}\rfloor &=\sum_{y=1}^k\lfloor\frac{(a_1\times 2^0)+(a_2\times 2^1)+...+(a_k\times 2^{k-1})}{2^y}\rfloor\\ &=\sum_{y=1}^k\frac{(a_{y+1}\times 2^{y})+...+(a_k\times 2^{k-1})}{2^y}\\ &=\sum_{y=1}^k\sum_{x=y+1}^k\frac{a_x\times 2^{x-1}}{2^y}\\ &=\sum_{x=1}^ka_x\sum_{y=0}^{x-2}{2^y}\\ &=\sum_{x=1}^k(2^{x-1}-1)a_x\\ &=\sum_{x=1}^k{a_x*2^{x-1}}-\sum_{x=1}^k{a_x}\\ &=n-\sum_{x=1}^k{a_x} \end{align} \]我们观察可以发现 \(n\) 在二进制下 \(1\) 的个数为 \(\sum\limits_{x=1}^k{a_x}\)
因此 \(n!\)在二进制下 \(2\) 因子的个数等于 \(n\) 减去其二进制下 \(1\) 的个数。
而组合数为奇数当且仅当 \(\text{A=B+C}\)
假设 \(n,m,(n-m)\) 在二进制下 \(1\) 的数目分别为 \(a,b,c\)
\[n-a=m-b+(n-m)-c \]\[a=b+c \]因此很明显我们可以发现当 \(n\&m=m\) 时 \(\dbinom{m}{n}\) 为奇数
标签:lfloor,奇偶,frac,组合,text,sum,个数,笔记,times From: https://www.cnblogs.com/Vsinger-LuoTianYi/p/18104205