2015
04-14

# Big Coefficients

F(x) is a polynomial in x with integer coefficients, here F(x) = (1+x)^a1 + (1+x)^a2 + … + (1+x)^am. Given a1, a2, … , am, find number of odd coefficients of F(x).

The first line contains a single positive integer T( T <= 10000 ), indicates the number of test cases.
For each test case:
First line contains an integer N(1 <= N <= 15).
Second line contains N integers a1, a2, …, am ( 0 <= ai <= 2^45 )

The first line contains a single positive integer T( T <= 10000 ), indicates the number of test cases.
For each test case:
First line contains an integer N(1 <= N <= 15).
Second line contains N integers a1, a2, …, am ( 0 <= ai <= 2^45 )

4
1
1
1
3
2
1 3
3
1 2 3

Case #1: 2
Case #2: 4
Case #3: 2
Case #4: 2

HintCase #3: (1+x) + (1+x)^3 = 2 + 4x + 3x^2 + x^3. it contains 2 odd coefficients.
Case #4: (1+x) + (1+x)^2 + (1+x)^3 = 3 + 6x + 4x^2 + x^3. it contains 2 odd coefficients. 

1. dfs(int beg,set S,int sym)
2. {
3.      ans+=num(S)*sym;
4.      for(int i=beg;i<=n;i++)
5.          dfs(i,S∩A[i],sym*-1);
6. }
7.
8. for(int i=1;i<=n;i++)
9.      dfs(i,A[i],1);

const  int Max_N = 18 ;

LL  GetBit(LL x){
LL ans = 0 ;
while(x){
x = x&(x-1) ;
ans++ ;
}
return ans ;
}

int  N  ;
LL   x[Max_N]  , ans ;

void dfs(int id , LL  n , LL f){
ans += ((LL)1<<GetBit(n)) * f ;
for(int i = id+1 ; i < N ; i++)
dfs(i , n&x[i] , -2*f) ;
}

int  main(){
int T , i ;
scanf("%d" ,&T) ;
for(int ca = 1 ; ca <= T ;  ca++){
scanf("%d" ,&N) ;
for(i = 0 ; i < N ; i++)
scanf("%I64d" ,&x[i]) ;
ans = 0 ;
for(i = 0 ; i < N ; i++)
dfs(i , x[i] , 1) ;
printf("Case #%d: %I64d\n" ,ca  , ans) ;
}
return 0 ;
}


1. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n