FHJ学长的心愿
题意
给你一个数N，让你求在$$C^{0}{n} C{1}_{n} C{2}{n} dots C^{n}_{n}$$中有几个组合数是奇数。
解题思路
出题人CX学长给的题解：
本题实际上是考察的Lucas定理。
Lucas定理:(写程序的时候后半部分可以递归求)
设(P)为素数，则：
[C^{m}_{n}(\% P)=C^{m\%P}_{n\%P}∗C^{⌊m/P⌋}_{⌊n/P⌋}(\%P)
]
一句话概括，就是一个组合数可以拆成(P)进制下的乘积，如下：（与上式本质相同）
[n = n_{k}*p^{k}+n_{k-1}*p^{k-1}+...+n_{1}*p+n_0
]
[m = m_{k}*p^{k}+m_{k-1}*p^{k-1}+...+m_{1}*p+m_0
]
则（上式实际上也就是把(n,m)分解成了(P)进制的形式）：
[C^{m}_{n}(\% P)=C^{m_{k}}_{n_{k}}∗C^{m_{k-1}}_{n_{k-1}}*...*C^{m_{0}}_{n_{0}}(\%P)
]
当(P = 2)的时候，其实就只有四种情况：(，，，，，C_1^0， C_0^1， C_0^0， C_1^1)，其中只有(C_0^1 =0)，其余都是1。
那么对于这个题，我们实际上要找的就是在(C_n^0...C_n^n)中有多少个 (C_n^m)满足(C_n^m\%2=1)。
对于给定的(n)，我们去考虑(m)，如果对应(n)的二进制位为0，那么(m)对应的二进制位只能为0（因为(C_0^1 =0)），如果对应(n)的二进制位为1，那么(m)对应的二进制位可以为1也可以为0。（这样也保证了统计的(mleq n)）。
所以答案就是n的二进制中1的位置取0或1的所有可能。即(2^{cnt})，(cnt)为(n)的二进制中1的个数。
这个题有人竟然通过找规律找出来的，真强。
代码实现
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while (scanf("%d", &n) != EOF) {
int cnt = 0;
while (n) {
if (n & 1) cnt++;
n >>= 1;
}
printf("%d
", 1 << cnt);
}
return 0;
}