题意分析
发现一个神奇的东西：$a_i\leq70$。值域如此之小，一定可以利用。因此考虑与值域有关的做法。
寻找完全平方数，则其所有质因子的指数均为偶数。
可以发现，$[1,70]$ 中的质数有且仅有 $19$ 个，可以考虑从此方面入手。
考虑影响是否为完全平方数的仅仅是质因子的指数的奇偶性，因此可以考虑状压 DP。
记第 $i$ 个质数为 $p_i,p_1=2$，设 $\textit{dp}{i,S}$ 表示选择完了 $a$ 中的 $1\sim i$，乘积的 $p_j$ 因子质数的奇偶性为 $S_j$ 时的方案数。则答案即 $\textit{dp}{n,\langle0,0,\cdots,0\rangle}$。注意到 $\vert S\vert\leq19$，显然可以压缩成一个二进制整数。
考虑如何递推。
设 $\textit{cnt}_i$ 为 $i$ 在 $a$ 中的出现次数，先考虑 $\textit{cnt}_i=1$ 的情况。
- 若不选择 $i$，那么方案数为 $\textit{dp}_{i-1,S}$。
- 否则，方案数为 $\textit{dp}_{i-1,S\oplus s}$。其中，$s$ 表示 $i$ 的状态。即对 $i$ 质因数分解，同时存储 $i$ 的质因子指数奇偶性。
则有：
\[\textit{dp}_{i,S}=\textit{dp}_{i-1,S}+\textit{dp}_{i-1,S\oplus s}\]考虑 $\textit{cnt}_i\neq 1$ 的情况。
其实是一样的。$\textit{cnt}_i$ 个 $i$，选择的总方案数为 $2^{\textit{cnt}_i-1}$。
则有：
\[\textit{dp}_{i,S}=2^{\textit{cnt}_i-1}\left(\textit{dp}_{i-1,S}+\textit{dp}_{i-1,S\oplus s}\right)\]注意到此时选择多少个 $i$ 对于奇偶性造成的影响并不需要考虑，因为那样仅仅是交换了一下 $\textit{dp}{i-1,S},\textit{dp}{i-1,S\oplus s}$ 而已。
注意到这样会 MLE，因此使用滚动数组优化掉前一维即可。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1e5,Vprime=19,V=70,P=1e9+7;
constexpr const int prime[Vprime]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
int n,a[N+1],dp[2][1<<Vprime|1],cnt[V+1];
int qpow(int base,int n){
int ans=1;
while(n){
if(n&1){
ans=(ll)ans*base%P;
}
base=(ll)base*base%P;
n>>=1;
}
return ans;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
cnt[a[i]]++;
}
bool mode;
dp[mode][0]=1;
for(int i=1;i<=V;i++){
if(!cnt[i]){
continue;
}
mode=!mode;
int s=0;
for(int x=i,j=0;j<Vprime;j++){
while(x%prime[j]==0){
s^=1<<j;
x/=prime[j];
}
}
int pl=qpow(2,cnt[i]-1);
for(int j=0;j<(1<<Vprime);j++){
dp[mode][j]=(ll)pl*(dp[!mode][j]+dp[!mode][j^s])%P;
}
}
int ans=dp[mode][0]-1;
if(ans<0){
ans+=P;
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
