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$。

都说状压DP是显然的

我们把每个数变成一个 0~2^19-1 的状态。

定义：

dp[x]

表示当前处理的数中，选一些数，使它们异或结果为 x 的方案数。

初始：

dp[0]=1;

表示一个数都不选，异或和为 0。

处理一个新的状态 s 时：

• 不选它：异或还是 x
• 选它：异或变成 x^s

所以：

ndp[x]+=dp[x];
ndp[x^s]+=dp[x];

最后 dp[0] 就是异或为 0 的方案数，再减去空集。

小数据直接 $O(2^n)$ 暴力搜索即可。

考虑大数据，无法暴力枚举方案，显然是需要我们直接统计方案数的，观察到 $a_i \leq 70$。

很明显是希望我们从因子的角度去考虑，对于一个完全平方数而言，质因数分解后的所有质因子个数必然是偶数

那么对于两个数字相乘，实际上就是将所有质因子的个数相加。

那么如果我们可以将所有数字进行质因数分解，就可以发现可行方案就是选几个数的质因子数量依次相加，如果所有质因子的个数均为偶数，则就是一种方案。

因为我们只关心质因子的个数是奇数还是偶数，并且 $a_i$ 最大只有 $70$，而 $70$ 以内的质因子个数只有 $19$ 个。

我们完全可以直接将质因子进行状态压缩，只保留奇偶性。

那么对于一个数字 $a[i]$ 状压后得到质因子奇偶性的状态 $b[i]$，那我们需要找到的就是 $b[i_1]+b[i_2]+b[i_3] \dots$ 在不进位的情况下结果为 $0$ 的方案数。

不进位加法那就可以直接异或，也就是我们只需要找到所有 $b[i_1] \oplus b[i_2] \oplus \dots = 0$ 的方案数。

显然可以直接进行 $dp$。

设 $f[i][j]$ 表示前 $i$ 个数字得到质因子状态 $j$ 的方案数。

那么转移即为 $f[i-1][j] \to f[i][j], f[i][j \oplus a[i]]$，直接求和即可。

这里建议使用 “到哪去” 的方向去求解，这样可以减少计算的次数，且保证正确性。

那么可以发现总体复杂度就是 $O(T * n * 2^{19})$，结合数据范围中当 $n=300$ 时 $T = 2$ 可以反向验证此做法就是出题者希望的解法。

在考虑到复杂度以后要注意，前面的特殊情况（测试点 $4$）无法使用此做法通过，需要进行特判。

这部分实际上就是每个质数可以选偶数个（包含 $0$) ，在 $x$ 个数字里选偶数个数字的方案数就是 $2^{x-1}$，总方案数的一半。

那么把所有质因子个数的 $2^{x-1}$ 做乘积，最后 $-1$ 即可（去掉全不选的情况）。

T2

状压 DP 是简单的，对于质数，我们必须直接多开一个数组 $p$ 表示 $p_i$ 是质数。不能判断 $state_i$ 是否为 $2^k$ 数。（参考 $x^2$）。