比赛的时候愣是往dp方向想了。。。 多做题多做题
#include <cstdio> #include <bitset> using namespace std; const int mod=1e9+7; int p[305],cnt,v[2000],t; int main() { for(int i=2;i<2000;i++) { if(v[i])continue; p[cnt++]=i; for(int j=i;j<2000;j+=i) v[j]=1; } scanf("%d",&t); for(int cas=1;cas<=t;cas++) { bitset<305> A[305]; int n; scanf("%d",&n); for(int i=0;i<n;i++) { long long x;scanf("%lld",&x); for(int j=0;j<cnt;j++) if(x%p[j]==0) { int tt=0; while(x%p[j]==0) { x/=p[j]; tt^=1; } A[j][i]=tt; } } int i=0,j=0; for(i=0;i<n;i++) { int id=-1; for(int k=j;k<cnt;k++)if(A[k][i]){id=k;break;} if(id==-1)continue; swap(A[j],A[id]); for(int k=j+1;k<cnt;k++) if(A[k][i]) A[k]^=A[j]; j++; } int ans=1; for(int i=0;i<n-j;i++) ans=ans*2%mod; printf("Case #%d:\n%d\n",cas,ans-1); } }