分析
题意就是对于一个数组，有多少个子集中的各项乘起来为完全平方数，记录个数并取模。
首先观察数据范围，发现数的大小很小，又想到平方数可以进行质因数分解，分解后，每一组相同项的个数都应为偶数。
于是第一步就想到了，因为70内的质数只有19个，于是我们状态压缩，用19位的二进制数，每一位表示对应位置的质数在乘积分解后有偶数个还是奇数个，对于每一个读取的数，计算它的质因数分解，异或转移，这样的复杂度为 \(n*2^{19}\)。
很明显，这样超时了，我们再次注意，数的大小真的很小，于是我们可以统计1到70数的个数，那对于每一个数如何处理呢？假设某一位数有 \(k\) 个，那么从中选择偶数个时，根本不会造成影响，因为每两个乘起来就是一个平方数，这种情况就是直接由上一个同样的状态转移过来即可，而如果奇数个，则是异或状态转移，而由题目中索引不同方案不同，再加入组合数，很容易证得，每一个奇数的组合加起来为 \(2^{k-1}\)，偶数一样，转移时乘上该数即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
inline int qpow(int ds,int zs){
int x=1;
while(zs){
if(zs&1)x=(x*ds)%mod;
ds=(ds*ds)%mod;zs>>=1;
}
return x;
}
inline void read(int &res){
res=0;
char c=getchar();
while(c<‘0‘||c>‘9‘)c=getchar();
while(c>=‘0‘&&c<=‘9‘)res=(res<<1)+(res<<3)+c-48,c=getchar();
}
int n,a,p,now,d;
int cnt[75],pri[20]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};//质数
int f[2][(1<<19)+5];
signed main()
{
read(n);
f[0][0]=1;
for(int i=1;i<=n;i++)read(a),cnt[a]++;//计数
for(int i=1;i<=70;i++){
if(!cnt[i])continue;//没有该数，跳过
d^=1;//第一维为2，否则炸空间
memset(f[d],0,sizeof(f[d]));
int x=i;
p=qpow(2,cnt[i]-1);//计算转移乘数
now=0;
for(int j=1;j<=19;j++){
while((x%pri[j])==0){
now^=1<<(j-1);//每查到一次，改变一次奇偶性
x/=pri[j];
}
}
for(int j=0;j<=(1<<19)-1;j++){
f[d][j]=p*f[d^1][j]%mod+p*f[d^1][j^now]%mod;
if(f[d][j]>=mod)f[d][j]-=mod;//小优化
}
}
if(f[d][0])cout<<f[d][0]-1;//减去一个都不选的情况
else cout<<mod-1;
return 0;
}