Codeforces 895C Square Subsets：状压dp【组合数结论】

题目链接：http://codeforces.com/problemset/problem/895/C

题意：

　　给你n个数a[i]。(n <= 10^5, 1 <= a[i] <= 70)

　　问你有多少非空子集s，使得 ∏(s[i])为完全平方数。

题解：

　　由于a[i] <= 70，而70以内的质数只有19个，显然可以状压。

 

　　由于一个数是完全平方数的条件是：它的每种质因子的指数为偶数

　　所以先处理出对于每个a[i]，它的所有质因子指数的奇偶性f[i]。

　　对于f[i]的每一位，0表示它的质因子prime[i]的指数为偶，1代表为奇数。

　　另外由于n比较大，所以dp中状态不能是“当前考虑到a[i]”，而应该是“当前考虑到数字i”。

　　所以之前要统计一下为数字i的a[j]的个数cnt[i]。(x <= 70)

　　然后开始状压。

　　表示状态：

　　　　dp[i][state]表示当前考虑到数字i，子集和的质因子指数的奇偶性为state，此时的子集方案数

　　找出答案：

　　　　由于1到70的所有数都会考虑一遍，且最终的子集和的质因子的指数都应该为偶数

　　　　另外由于要求是非空子集，最终答案要-1

　　　　所以ans = dp[71][0] - 1

　　如何转移：

　　　　对于数字i来说，如果cnt[i] == 0，则直接将所有dp[i][state]复制到dp[i+1][state]即可。

　　　　否则分两种情况：数字i选偶数个 or 奇数个。选偶数个i不会影响子集和质因子指数的奇偶性，而奇数个会影响。

　　　　（1）偶数个：dp[i+1][state] += dp[i][state] * C(n,m)，其中m = 0,2,4,6,8...

　　　　（2）奇数个：dp[i+1][state^f[i]] += dp[i][state] * C(n,m)，其中m = 1,3,5,7,9...

　　　　有一个结论：∑ C(n,{0,2,4,6,8...}) = ∑ C(n,{1,3,5,7,9...}) = 2^(n-1)

　　　　之前预处理所有p[i] = 2^i % MOD即可。

　　边界条件：

　　　　dp[1][0] = 1

　　　　others = 0

AC Code:

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 100005
#define MAX_A 75
#define MAX_S 550000
#define MOD 1000000007

using namespace std;

const int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};

int n;
int p[MAX_N];
int f[MAX_A];
int cnt[MAX_A];
int dp[MAX_A][MAX_S];

void read()
{
    cin>>n;
    memset(cnt,0,sizeof(cnt));
    int a;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        cnt[a]++;
    }
}

void cal_f()
{
    memset(f,0,sizeof(f));
    for(int i=1;i<=70;i++)
    {
        int t=i;
        for(int j=0;j<19;j++)
        {
            while(t%prime[j]==0)
            {
                f[i]^=(1<<j);
                t/=prime[j];
            }
        }
    }
}

void cal_p()
{
    p[0]=1;
    for(int i=1;i<MAX_N;i++) p[i]=(p[i-1]<<1)%MOD;
}

void cal_dp()
{
    memset(dp,0,sizeof(dp));
    dp[1][0]=1;
    for(int i=1;i<=70;i++)
    {
        if(!cnt[i])
        {
            for(int state=0;state<(1<<19);state++)
            {
                dp[i+1][state]=dp[i][state];
            }
        }
        else
        {
            for(int state=0;state<(1<<19);state++)
            {
                if(dp[i][state])
                {
                    dp[i+1][state]=(dp[i+1][state]+(long long)dp[i][state]*p[cnt[i]-1])%MOD;
                    dp[i+1][state^f[i]]=(dp[i+1][state^f[i]]+(long long)dp[i][state]*p[cnt[i]-1])%MOD;
                }
            }
        }
    }
}

void work()
{
    cal_f();
    cal_p();
    cal_dp();
    cout<<dp[71][0]-1<<endl;
}

int main()
{
    read();
    work();
}