首页 > ACM题库 > HDU-杭电 > HDU 3929-Big Coefficients-DFS-[解题报告]HOJ
2015
04-14

HDU 3929-Big Coefficients-DFS-[解题报告]HOJ

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


Hint
Case #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.

参考 :(转载)http://blog.csdn.net/acdreamers/article/details/9280569

题意:F(x) = (1+x)^a1 + (1+x)^a2 + … + (1+x)^am,求系数是奇数的项的个数。

容斥原理:递归形式

  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);  

 

每个系数是一个集合,它的奇数次项的个数就是集合的个数,算法是2^(系数的二进制里1的个数).

两个集合的交是: 比如系数w1,w2,集合的交的个数是2^(w1&w2的二进制里1的个数)

由于奇数次幂相交不一定是奇数次幂,,所以所以要把偶数个集合的交的个数减掉,写一下式子,发现问题没有变复杂,只需把上面的递归式的sym由-1变为-2既可.


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 ;
}



另外  , 非递归写法TLE 。

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/u013491262/article/details/22760777


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