题目链接：https://codeforces.com/contest/895/problem/C
题目大意：给你n个数。问有多少个子集的乘积为平方数。mod （1e9+7）。

思路一：
如果一个数的质因数都为偶数个，那么这个数就是平方数。
因为a[i]<=70。我们用状压来表示每个数的质因数的奇偶状态。奇为1.偶为0。

我们用dp[i][s]表示前i个数组成乘积为状态s的方案数。
然后我们枚举i-1的状态s转移。

如果i选择偶数个,那么i自己的集合为0， 那么i-1的状态必须为s。

如果i选择奇数个，那么i自己的集合为s0^s， 那么i-1的状态为s。

然后用滚动数组。

思路二：

法一：
#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL a[100005];
LL cut[75];
const LL p[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};//19
LL c2[100005]={1};
LL f[2][1<<21];

const int mod = 1e9+7;
int main()
{
    int n;
    scanf("%d", &n);
    for(LL i=1; i<=n; i++){
        scanf("%lld", &a[i]);
        cut[a[i]]++;
    }
    for(LL i=1; i<=n; i++){
        c2[i]=c2[i-1]*2%mod;
    }

    f[0][0]=1;//初始化
    int I=0;
    for(LL i=1; i<=70; i++){
        if(cut[i]==0){
            continue;
        }
        I^=1;
        int s0=0;//i本身的状态
        int SI=i;
        for(int k=0; k<19; k++){
            while(SI%p[k]==0){
                s0^=(1<<k);
                SI/=p[k];
            }
        }
        memset(f[I], 0, sizeof(f[I]));
        for(LL s=0; s<(1<<19); s++){//枚举i-1的状态s
            f[I][s]+=f[I^1][s]*c2[cut[i]-1]%mod;//如果i选择偶数个新状态为0^s
            f[I][s^s0]+=f[I^1][s]*c2[cut[i]-1]%mod;//如果i选择奇数个新状态为s^s0
        }
    }
    printf("%lld\n", (f[I][0]-1+mod)%mod);//f[0][0]为空集。不满足-1

    return 0;
}

发二：
#include<bits/stdc++.h>
#define reg register
#define LL long long
using namespace std;
typedef long long ll;
const int MN=60;
ll a[61],tmp[61];
const LL p[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};//19
LL c2[100005]={1};
const int mod = 1e9+7;

bool flag;
void ins(ll x){//构造
    for(reg int i=MN;~i;i--)
        if(x&(1ll<<i))
            if(!a[i]){a[i]=x;return;}
            else x^=a[i];
    flag=true;
}

bool check(ll x){//是否能够插入 判断是否能够异或出一个数
    for(reg int i=MN;~i;i--)
        if(x&(1ll<<i))
            if(!a[i])return false;
            else x^=a[i];
    return true;
}

ll qmax(ll res=0){//最大值
    for(reg int i=MN;~i;i--)
        res=max(res,res^a[i]);
    return res;
}

ll qmin(){//最小值
    if(flag)return 0;
    for(reg int i=0;i<=MN;i++)
        if(a[i])return a[i];
}

ll query(ll k){//第k小
    reg ll res=0;reg int cnt=0;
    k-=flag;if(!k)return 0;
    for(reg int i=0;i<=MN;i++){
        for(int j=i-1;~j;j--)
            if(a[i]&(1ll<<j))a[i]^=a[j];
        if(a[i])tmp[cnt++]=a[i];
    }
    if(k>=(1ll<<cnt))return -1;
    for(reg int i=0;i<cnt;i++)
        if(k&(1ll<<i))res^=tmp[i];
    return res;
}

int getnum(int x){
    int ans=0;
    for(int k=0; k<19; k++){
        while(x%p[k]==0){
            ans^=(1<<k);
            x/=p[k];
        }
    }

    return ans;
}

int main(){

    int n, x;scanf("%d",&n);
    for(LL i=1; i<=n; i++){
        c2[i]=c2[i-1]*2%mod;
    }

    for(int i=1; i<=n; i++){
        scanf("%d", &x);
        ins(getnum(x));
    }

    for(reg int i=MN;~i;i--){
        if(a[i]){
            n--;
        }
    }
    printf("%lld\n",c2[n]-1);

    return 0;
}