題意：給你一個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); } }
