BUPT2017 wintertraining(15) #8H
题意
求组合数C(n,i)，i从0到n，里面有几个奇数。
题解
直接打表的话可能就直接发现规律了。
规律是n的二进制里有几个1，答案就是2的几次方。
证明：
lucas定理有：C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p
然后取p为2。
所以展开后是C(0,0),C(0,1),C(1,0),C(1,1)的乘积。其中只有C(0,1)=0。
那么C(n,i)%2==1的条件就是n对应位为0，则i对应位必须是0，n对应位为1，则i对应位可以是1，也可以是0。
所以答案就是2的(1的个数)次方。
代码
#include <cstdio>
int main(){
int n;
while(~scanf("%d",&n)){
int cnt=0;
while(n){
cnt+=(n&1);
n>>=1;
}
printf("%lld\n", 1LL<<cnt);
}
return 0;
}