网络预选赛的题目……比赛的时候没有做上，确实是没啥思路，只知道肯定是整数分解，然后乘起来素数的幂肯定是偶数，然后就不知道该怎么办了…
最后题目要求输出方案数，首先根据题目应该能写出如下齐次方程（从别人那里盗的……）：
a11*x1 ^ a12*x2 ^ ... ^ a1n*xn=0
a21*x1 ^ a22*x2 ^ ... ^ a2n*xn=0
...
an1*x1 ^ an2*x2 ^ ... ^ ann*xn=0，Aij表示选的第j个数的第i个质数（可能有些人跟我有一样的疑问，为什么不是第i个数的第j个质数呢，这是为了方便消元计算），xi为1或者0，代表数选和不选。
所以这个问题就化成了该方程有几个解的问题，该方程的特征矩阵有303行，n列，因为1-2000之间一共有303个素数，实际可以省略用不到的那些。
然后，学过线性代数的童鞋都知道，当它的特征矩阵的秩是n的时候，该方程有唯一解，就是0解，所以当时我们求出秩来以后，如果秩是r且r < n,也就意味着有n-r个0行，同时意味着，它与其它行线性相关，也就是这一行不影响答案，有选和不选两种情况，一共就有2的（n-r）次方 种情况，求秩的方法用高斯消元的模板，类比成异或就可以了，当时我还自己写了一个消元的函数，发现不对……还是贴的人家的模板。
代码及注释如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
#define N 305
#define mod 1000000007
LL a[N];
int prime[N],tot,n,m;
int fenjie[N][N],zhuan[N][N];
bool yes(int x)
{
for(int i = ; i*i <= x; i++)
{
if(x%i == ) return false;
}
return true;
}
void Make_P()///暴力版素数表，实在懒得改……
{
tot = ;
for(int i = ; i <= ; i++)
{
if(yes(i)) prime[tot++] = i;
}
}
void FenJie()///质因数分解
{
memset(fenjie,,sizeof(fenjie));
m = -;
for(int i = ; i < n; i++)
{
LL tmp = a[i];
for(int j = ; j < tot; j++)
{
while(tmp % prime[j]==)
{
fenjie[j][i]++;
tmp /= prime[j];
m = max(m,j);///取一个最大的j值即可
}
fenjie[j][i] %= ;
if(tmp == ) break;
}
}
m++;
}
int Rank()///高斯消元求秩[j][i]的形式派上了用场
{
int i=,j=,k,r,u;
while(i < m && j < n)
{
r = i;
for(k=i; k<m; k++)
{
if(fenjie[k][j])
{
r=k;
break;
}
}
if(fenjie[r][j])
{
if(r != i)
for(k=; k <= n; k++)swap(fenjie[r][k],fenjie[i][k]);
for(u=i+; u<m; u++)
if(fenjie[u][j])
for(k=i; k<=n; k++)
fenjie[u][k]^=fenjie[i][k];
i++;
}
j++;
}
return i;
} int mypow(int x,int y)
{
int res = ;
for(int i = ; i <= y; i++)
{
res = ((x%mod)*(res%mod)) % mod;
}
return res;
}
int Slove()
{
int mi = n-Rank();
return (mypow(,mi) - ) % mod;
}
int main()
{
// freopen("in1.cpp","r",stdin);
int t,ca=;
Make_P();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i = ; i < n; i++)
{
cin>>a[i];
}
FenJie();
printf("Case #%d:\n",++ca);
cout<<Slove()<<endl;
}
return ;
}