给一个集合S，问S有多少个子集满足子集中的数乘积是完全平方组。

　　一个数是完全平方数当且仅当它所有的质因数都有偶数个，所以只要看这个集合中所有数的质因数是否是偶数个即可。和开灯方案数问题类似，矩阵中X[i][j]=1表示第j个数的第i个质因数(2,3,5,7...)有奇数个，等于0表示有偶数个。然后列出XOR方程组然后算有几个自由基即可。

　

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 typedef long long LL; 6 int cas, n; 7 LL nx; 8 int isp[505], prs, pri[505]; 9 int x[505][505];10 void init(){11     for (int i = 2; i < 501; i++) if(!isp[i])12         for (int j = i*2; j < 501; j += i) isp[j] = 1;13     for (int i = 2; i < 501; i++) if(!isp[i]) pri[prs++] = i;14 }15 int gauss(int totr, int totc) {16     int r = 0, c = 0;17     while (r < totr && c < totc) {18         int maxr = r;19         for (int i = r+1; i < totr; i++)20             if (x[i][c]) maxr = i;21         if (x[maxr][c] != 0) {22             if (maxr != r)23                 for (int i = 0; i <= totc; i++) swap(x[maxr][i], x[r][i]);24             for (int i = r+1; i < totr; i++) if(x[i][c]){25                 for (int j = c; j <= totc; j++) x[i][j] ^= x[r][j];26             }27             r++;28         }29         c++;30     }31     return totc - r;32 }33 int main(){34     //freopen("test.in","r",stdin);35     init();36     scanf("%d", &cas);37     while (cas--) {38         scanf("%d", &n);39         memset(x, 0, sizeof x);40         for (int i = 0; i < n; i++) {41             scanf("%lld", &nx);42             for (int j = 0; j < prs; j++) {43                 while (nx % pri[j] == 0)44                     nx /= pri[j], x[j][i] ^= 1;45             }46         }47         int l = gauss(prs, n);48         printf("%lld\n", (1LL<