300个最大质因数小于2000的数，选若干个它们的乘积为完全平方数有多少种方案。
合法方案的每个数的质因数的个数的奇偶值异或起来为0。
比如12=2^2*3，对应的奇偶值为01（2的个数是偶数为0，3的个数是奇数为1），3的对应奇偶值为01，于是12*3是完全平方数。
然后异或方程组就是：
a11x1 a12x2 ... a1nxn=0
a21x1 a22x2 ... a2nxn=0
...
an1x1 an2x2 ... annxn=0
aij：第i个质数（2000内有303个质数）在第j个数里是奇数个则为1，否则为0。
xi：第i个数（最多300个数）被选则为1，否则为0。
求出有多少种解即可。（异或方程组高斯消元求秩，然后解就有2^(n-rank)种，减去全为0的解）
代码语言：javascript复制#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
#define mod 1000000007
using namespace std;
const int N=2000;
const int M=310;
int prime[N 1],cnt;
int n,t,mat[M][M],two[M]={1};
ll a[M];
void getPrime(){
for(int i=2;i<=N;i ){
if(!prime[i])prime[ cnt]=i;
for(int j=1;j<=cnt&&prime[j]<=N/i;j ){
prime[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
}
int Rank(int c[][M]){//异或版的高斯消元求秩
int i=0,j=0,k,r,u;
while(i<=cnt&&j<=n){
r=i;
while(c[r][j]==0&&r<=cnt)r ;
if(c[r][j]){
swap(c[i],c[r]);
for(u=i 1;u<=cnt;u )if(c[u][j])
for(k=i;k<=n;k )c[u][k]^=c[i][k];
i ;
}
j ;
}
return i;
}
int solve(){
memset(mat,0,sizeof mat);
for(int i=1;i<=n;i )
for(int j=1;j<=cnt;j ){
ll tmp=a[i];
while(tmp%prime[j]==0){
tmp/=prime[j];
mat[j][i]^=1;
}
}
int b=n-Rank(mat);//b个自由元
return two[b]-1;//减去全为0的解
}
int main() {
getPrime();
for(int i=1;i<M;i )two[i]=two[i-1]*2%mod;
scanf("%d",&t);
for(int cas=1;cas<=t;cas ){
scanf("%d",&n);
for(int i=1;i<=n;i )
scanf("%lld",&a[i]);
printf("Case #%d:n%dn",cas,solve());
}
return 0;
}原来是白书上的题（160页）I good vagetable a！
