题意：给你一个n，求C _(n,0),C _(n,1),C _(n,2)...C _{(n,n)，奇数的个数。}

_分析：

_{Lucas定理：}

A、B是非负整数，p是质数。AB写成p进制：A=a[n]a[n-1]...a[0]，B=b[n]b[n-1]...b[0]。
则组合数C(A,B)与C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0]) modp同余

即：Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)

来看这一题，求奇数，那么我们就用二进制，这样一想思路就打开了，C(n,m)=C(a[nk1],b[mk1])*C(a[nk2][mk2])****(mod 2)，我们知道C(0,1)是0，所以只要n的二进制位上为0的位置，如果m在该位的二进制是1，则C(n,m)模2就等于0，即为偶数，否则为奇数；而C(1,0)，C(1,1)都为1，所以n的二进制位上为1的位置，m在对应位置可以填0也可以填1，这就变成了一个组合问题了，设n的二进制位共有k个1，那么使C(n,m)为奇数的m共有2^k种。

有些题不会做打表找规律也是个好方法

代码：

?

#include
  
   
#include
   
     #include
    
      using namespace std; int n; int main() { while(scanf(%d,&n)!=EOF){ int tot=0; int j=n; int tmp=n&1; while(j){ if(tmp) tot++; j>>=1; tmp=j&1; } int ans=pow(2,tot); printf(%d ,ans); } }
    
   
  

?