Sam的完全平方数 题解

核心思路

注意到，一个完全平方数的所有质因子的次数都是偶数。因此，我们只需要关心每个质因子次数的奇偶性，而不需要关心具体次数。

由于 $a_i \leq 70$，而 $70$ 以内的质数只有 $19$ 个：$2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67$。所以我们可以用一个长度为 $19$ 的 $01$ 串（状态压缩）来表示一个数所有质因子次数的奇偶性。

状态设计

设 $dp[mask]$ 表示选出若干个数，使得这些数的质因子奇偶性状态异或起来等于 $mask$ 的方案数。

• 初始状态：$dp[0] = 1$，表示什么都不选，状态为 $0$。
• 对于每个数 $a_i$，计算它的状态 $mk$（每个质因子次数模 $2$ 的结果组成的二进制数）。
• 转移：$dp_{new}[mask] = dp_{old}[mask] + dp_{old}[mask \oplus mk]$。即要么不选 $a_i$，要么选 $a_i$ 并将状态异或上 $mk$。

为什么这样是对的？

因为异或运算满足交换律和结合律，且两个数相乘时，对应质因子的次数是相加的。而我们只关心奇偶性，所以加法在模 $2$ 意义下就是异或。

同时，一个若最终凑出的01串为 $s$，不论是否是通过加入 $a_i$ 而来的，都满足是合法的方案，对后续答案没有影响，也就是无后效性，可以使用滚动数组优化。

所以最终答案为 $dp[0] - 1$（减去什么都不选的那一种方案）。

关键注意

若当前出现的所有数的质因子中都没有某一个质因子，那么这个质因子在转移时可以不跑，见代码里的 $mxp$ 变量。

在此基础上，将 $a_i$ 从小到大排序，可以在 $a_i$ 均为质因子时，跑的飞快。

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=350,MOD=1e9+7;
int n,a[N],dp[1<<19],ndp[1<<19],mxp=0,pri[19]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};

int main(){
	freopen("square.in","r",stdin);
    freopen("square.out","w",stdout);
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		for(int i=0;i<(1<<19);i++){
			ndp[i]=dp[i]=0;
		}
		cin>>n;
		dp[0]=ndp[0]=1;
		mxp=0;
		for(int x=1;x<=n;x++){
			cin>>a[x];
		}
		sort(a+1,a+n+1);
		for(int x=1;x<=n;x++){
			int mk=0;
			for(int i=0;i<19 && pri[i]<=a[x];i++){
				if(a[x]%pri[i]!=0){
					continue;
				}
				mxp=max(mxp,i+1);
				int cnt=0,p=pri[i];
				while(a[x]%p==0){
					a[x]/=p;
					cnt++;
				}
				if(cnt%2==1){
					mk|=(1<<i);
				}
			}
			for(int mask=0;mask<(1<<mxp);mask++){
				ndp[mask]=(ndp[mask]+dp[mask^mk])%MOD;
			}
			for(int mask=0;mask<(1<<mxp);mask++){
				dp[mask]=ndp[mask];
			}
		}
		cout<<(dp[0]+MOD-1)%MOD<<endl;
	}
	return 0;
}

复杂度分析

• 时间复杂度：$O(n \cdot 2^{19})$，其中 $19$ 是 $70$ 以内的质数个数。
• 空间复杂度：$O(2^{19})$。

样例验证

• 第一组：3 3 8，只有选 3,3 得到 $9=3^2$，答案为 $1$。
• 第二组：2 4 8 16，有 $7$ 种方案，答案为 $7$。
• 第三组：3 3 3，可以选任意两个 $3$，也可以三个都选（$27$ 不是平方数，但 $3 \times 3 = 9$ 是），实际上选两个 $3$ 有 $3$ 种方案，答案为 $3$。