把模数写成了1e9+9,气死我了
/* 1-70里只有19个质数，首先考虑状压dp 第i个质数出现奇数次，那么第i位为1，反之为0 每个数在质因子分解后都可以得到一个对应的mask dp[i][s]表示当前选的数是i，且其状态为s时的方案数 那么选择偶数个i对s的状态无影响，有C(cnti,0)+C(cnti,2)..=2^(cnti-1)（二项式定理） 种方案 选择偶数个i对s的影响是s^mask[i],也有 2^(cnti-1)种方案 转移方程 dp[i][s]+=dp[i-1][s^mask[i]] * p2[cnt[i]-1] 选奇数个i dp[i][s]+=dp[i-1][s] * p2[cnt[i]-1] */ #include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000007 ll primes[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67}; ll n,cnt[72],a[200005],dp[2][1<<20]; ll mask[72],p2[200005]; int getmask(int x){ int res=0; for(int i=0;i<=18;i++){ int flag=0; while(x%primes[i]==0) x/=primes[i],flag^=1; if(flag)res|=(1<<i); } return res; } int main(){ cin>>n; p2[0]=1; for(int i=1;i<=200000;i++)p2[i]=p2[i-1]*2%mod; for(int i=1;i<=n;i++)scanf("%lld",&a[i]),cnt[a[i]]++; for(int i=1;i<=70;i++)mask[i]=getmask(i); dp[0][0]=1; int cur=0; for(int i=1;i<=70;i++){ if(cnt[i]==0)continue; cur^=1; memset(dp[cur],0,sizeof dp[cur]); for(int s=0;s<(1<<19);s++){ dp[cur][s]=(dp[cur][s]+dp[cur^1][s^mask[i]]*p2[cnt[i]-1]%mod)%mod; dp[cur][s]=(dp[cur][s]+dp[cur^1][s]*p2[cnt[i]-1]%mod)%mod; } } cout<<(dp[cur][0]-1+mod)%mod<<' '; }