看到 \(a_i\le 70\) 后，发现 \(n\) 啥用没有，因为只需要枚举 \(1-70\) 选几个即可。
看到求完全平方数后，想到分解质因数，由于 \(a_i\le 70\)，所以只有 \(19\) 个质数，可以进行状压 dp。
设 \(dp_{i,j}\) 表示枚举到 \(i\)，状态为 \(j\) 的方案数，便有：
\[dp_{i,j}=dp_{i-1,j}+dp_{i-1,j \oplus x} \]其中 \(x\) 为 \(i\) 分解后的状态。
当然，我们忽略了一些情况，没有考虑到我们有很多种达到标准的方式，比如你放 \(1\) 个和放 \(3\) 个效果一样，你放这 \(3\) 个和放那 \(3\) 个效果一样。
所以，放奇数个的方案数为（\(a_i\) 表示数列里有多少个 \(i\)）：
\[C_{a_i}^1+C_{a_i}^3+……+C_{a_i}^{2\lfloor\frac{a_i}{2}\rfloor}=2^{a_i-1} \]放偶数个的方案数为：
\[C_{a_i}^0+C_{a_i}^2+……+C_{a_i}^{2\lceil\frac{a_i}{2}\rceil}=2^{a_i-1} \]所以：
\[dp_{i,j}=2^{a_i}(dp_{i-1,j}+dp_{i-1,j \oplus x}) \]时间复杂度 \(O(n+70\times 2^{19})\)，空间复杂度 \(O(70\times 2^{19})\)，注意不要 \(T/MLE\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=1e9+7;
const int N=75,M=1<<19;
int n,m,pr[25],t[N];
int dp[N][M+5],a[N];
ll qpow(ll x,int y){
if(y<0) return 1;
ll re=1;
while(y){
if(y&1) re=re*x%p;
x=x*x%p;
y>>=1;
}return re;
}int main(){
cin>>n;
for(int i=1,x;i<=n;i++)
cin>>x,a[x]++;
memset(t,1,sizeof(t));
t[1]=0;dp[0][0]=1;
for(int i=2;i<=70;i++){
if(t[i]) t[i]=++m,pr[m]=i;
for(int j=1;j<=m&&pr[j]*i<=70;j++){
t[i*pr[j]]=0;
if(i%pr[j]==0) break;
}
}for(int i=1;i<=70;i++){
int x=0,z=i;
for(int j=1;pr[j]*pr[j]<=i;j++)
while(z%pr[j]==0)
x^=(1<<(j-1)),z/=pr[j];
if(z>1) x^=(1<<(t[z]-1));
int zjy=qpow(2,a[i]-1);
for(int j=0;j<M;j++){
dp[i][j]=(dp[i][j]+(ll)dp[i-1][j]*zjy%p)%p;
if(a[i]) dp[i][j^x]=(dp[i][j^x]+(ll)dp[i-1][j]*zjy%p)%p;
}
}cout<<(dp[70][0]+p-1)%p;
return 0;
}//Kaká