Codeforces 895C - Square Subsets 状压DP

题意:

　给了ｎ个数，要求有几个子集使子集中元素的和为一个数的平方。

题解：

　因为每个数都可以分解为质数的乘积，所有的数都小于70，所以在小于70的数中一共只有19个质数。可以使用状压DP,每一位上０表示这个质数的个数为偶数个,1表示为奇数个。这样的话，如果某个数为一个数的平方的话，那么每个质数个数都是偶数，用０可以表示。从１－７０开始状压DP，先存下每个数出现多少次，然后dp转移，dp转移时分别计算某个数出现奇数次还是偶数次的方案数.

这里有一个公式：C(n,0)+C(n,2)+……=C(n,1)+C(n,3)+……=2^(n-1);

 #include<bits/stdc++.h>

 using namespace std;

 const int MAX_N = 1e5+;

 const int MOD = 1e9+;

 int vec[],tran[],sum[MAX_N];

 int dp[][(<<)+];

 int prime[] = { , , , , , , , , , , , , , , , , , ,  };

 int main()

 {

     int N,M,T;

     while(cin>>N)

     {

         memset(vec,,sizeof(vec));

         memset(tran,,sizeof(tran));

         memset(sum,,sizeof(sum));

         memset(dp,,sizeof(dp));

         for(int i=;i<N;i++)

         {

             int temp;

             scanf("%d",&temp);

             vec[temp] ++;

         }

         for(int i=;i<=;i++)

         {

             int t = i;

             for(int j=;j<;j++)

             {

                 while(t%prime[j] == )

                 {

                     tran[i] ^= (<<j);

                     t /= prime[j];

                 }

             }

         }

         sum[] = ;

         for(int i=;i<=N;i++)

         {

             sum[i] = (sum[i-]*)%MOD;

         }

         dp[][] = ;

         for(int i=;i<=;i++)

         {

             if(vec[i] == )

             {

                 for(int j=;j<(<<);j++) dp[i][j] = dp[i-][j];

             }

             else

             {

                 for(int j=;j<(<<);j++)

                 {

                     //奇数

                     dp[i][j^tran[i]] = (dp[i][j^tran[i]] + (long long )dp[i-][j]*sum[vec[i]-])%MOD;

                     //偶数

                     dp[i][j] = (dp[i][j] + (long long )dp[i-][j]*sum[vec[i]-])%MOD;

                 }

             }

         }

         cout<<(dp[][] - )%MOD<<endl;

     }

     return ;

 }

巴特西

Codeforces 895C - Square Subsets 状压DP

最新文章

热门文章