题意

给一些数,求能取出多少个非空子集使所有数相乘为完全平方数.
$n\le 10^5,a_i\le 70$.

题解

$70$以内的质数只有$19$个,并且一个数的平方性可以用每一个质数的奇偶性判断,不妨用一个压缩状态来代表某个数的状态是否是奇数.
我们对所有数取状态之后本题变为有多少个集合使状态的异或为0.
列出状态矩阵,进行高斯消元,可以发现答案为$2^x-1$,其中$x$为该异或方程自由元的个数.
显然自由元最多$19$个,直接在线性基中暴力判断即可,线性基中存在数的个数即为自由元的个数.

#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rel register ll
#define rec register char
#define gc getchar
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?-1:*p1++)
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
char buf[1<<23],*p1=buf,*p2=buf;
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) pc('-'),x=-x;
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int yuzu=2e5,mod=1e9+7,mulu=1e6;
typedef ll fuko[mulu|10];
fuko bit,pr={19,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67},a;// 70以内的质数表直接打出来就可以了.
ll kasumi(ll a,ll b=mod-2) {
  ll zw=1;
  for (;b;b>>=1,a=a*a%mod) if (b&1) zw=zw*a%mod;
  return zw;
}
int main() {
  int i,n,j,x;
  for (read(n),i=1;i<=n;++i) a[i]=read();
  for (i=2;i<=70;++i) 
    for (x=i,j=1;j<=*pr&&x>1;++j)
      for (;x%pr[j]==0;x/=pr[j]) bit[i]^=1ll<<j; // 求出每个数的压缩状态
  vector<ll> kg;
  for (i=1;i<=n;++i) {
    ll x=bit[a[i]];
    for (auto p:kg) x=min(x,p^x); // 线性基
    if (x) kg.push_back(x);
  }
  printf("%lld\n",(kasumi(2,n-kg.size())-1+mod)%mod);
}

谢谢大家.