[CF895C]Square Subsets

题意简述

给定$n$个数$(n\le10^5 )$，每个数$\le70$，在其中选择一个子集，求使其乘积为完全平方数的方法有多少种。

题解

一道状压$dp$好题。

注意到此题$a_i\leq70$，
并且一个数是否为完全平方数只与它的质因子奇偶性有关，~~所以$n\leq10^5$ 是废话~~，我们只需要用一个桶统计每个数出现的个数就好了。

另外，打表发现$70$以内质数只有$19$个，所以想到状压$dp$。

令$dp_{i,mask}$ 表示考虑到$1-70$中的第i个数。并且因为一个数是否为完全平方数只与它的质因子奇偶性有关，$mask$ 表示这$19$ 个数的奇偶性，若第$j$个质数的因数个数为奇数则$mask$ 第j 位为1。

考虑$dp$方程的转移。

先从$1-70$ 枚举$i$，若$cnt_i$ (即数$i$在数组中出现次数)不为零，则枚举$mask$

显然，当选奇数个数$i$ 时，$mask$ 会发生改变，我们将$i$分解质因数，$mask$ 变为$mask1$ , $dp_{i,mask1}$ 可以从$dp_{i-1,mask}$转移。

当选偶数个$i$时,$mask$不会改变, $dp_{i,mask}$ 可以从 $dp_{i-1,mask}$ 转移。

让我们令当前的$cnt_i= k$，选奇数个的情况 $C_k^1+C_k^3+C_k^5+\cdot\cdot\cdot=\sum\limits_{i\leq k,i\equiv1(mod2)}^iC_k^i=2^{k-1}$ 种

选偶数个的情况有 $C_k^0+C_k^2+C_k^4+\cdot\cdot\cdot=\sum\limits_{i\leq k,i\equiv0(mod2)}^iC_k^i=2^{k-1}$ 种

这两个式子可以用二项式定理证明。

所以$dp_{i,mask1}+=dp_{i-1,mask}*2^{k-1}$

$dp_{i,mask}+=dp_{i-1,mask}*2^{k-1}$

如果$cnt_i==0$ 我们就将$dp_{i-1}$赋值给$dp_{i}$

我们可以看到，任$dp_{i,mask}$ 只需从$dp_{i-1}$ 中的数转移，我们可以用滚动数组滚掉一维。

这样我们就做完了。

注意开$long long $

code:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back

#define y0 pmt
#define y1 pmtpmt
#define x0 pmtQAQ
#define x1 pmtQwQ

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int > vi;
typedef pair<int ,int > pii;
typedef vector<pii> vii;
const int inf=0x3f3f3f3f, maxn=100007, mod=1e9+7;
const ll linf=0x3f3f3f3f3f3f3f3fLL;
const ll P=19260817;
const int p[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};//质数表
int n;
ll dp[2][1<<19];
ll cnt[75];
int I=0;
ll h[maxn];//2^k的表
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int rt;
		scanf("%d",&rt);
		cnt[rt]++;
	}
	h[0]=1;
	dp[0][0]=1; 
	for(int i=1;i<=n;i++)h[i]=(h[i-1]<<1)%mod;
	for(int i=1;i<=70;i++){
		if(cnt[i]==0)continue;
		I^=1;//滚动数组
		memset(dp[I],0,sizeof(dp[I]));//注意初始化
		for(int mask=0 ; mask< (1<<19) ; mask++){
			int mask1=mask;
			int x=i;
			for(int j=0;j<19&&x>=p[j];j++){
				while(x%p[j]==0)x/=p[j],mask1^=(1<<j);
			}
			(dp[I][mask1]+=1LL*dp[I^1][mask]*h[cnt[i]-1]%mod)%=mod;
			(dp[I][mask]+=1LL*dp[I^1][mask]*h[cnt[i]-1]%mod)%=mod;
		}
	}
	printf("%I64d\n",(dp[I][0]-1+mod)%mod);
    return 0;
}