. . 题意：给出n个数，问有多少种取法使得取的数的积为完全平方数。 . . 解法：高斯消元的例题，质数不超过2000只有303个，每个数分解质因数并且模2就成了一个01矩阵，转换成多条式子形如 (k1+k2+k3+…)%2=0，然后对这个矩阵高斯消元，消元后每一行第一个1都是被后面的01所控制，最后结果为2^（n-矩阵不全为0的行数）-1。 . . 代码因为当时时间紧迫有点乱 可以对拍但不太建议参考
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std; const int maxn = 500; const long long mo = 1000000007; bool flag[3000] = {0}, fuck[3000]; int d[3000] = {0}, a[3000], n; long long x, tt; long long f[maxn][2]; int map[500][500], mapp[500][500]; void swap(int x, int y) { for (int i = 1; i <= n; i++) { int temp = map[x][i]; map[x][i] = map[y][i]; map[y][i] = temp; } } void cheng(int x, int y) { for (int i = 1; i <= n; i++) { map[y][i] = map[x][i]^map[y][i]; } } int main() { freopen("in.txt","r",stdin); freopen("ans.txt","w",stdout); d[0] = 2; d[1] = 2; d[2] = 3; for (int i = 4; i <= 2000; i++) { bool temp = true; for (int j = 1; j <= d[0]; j++) if (i%d[j] == 0) { temp = false; break; } if (temp) { d[++d[0]] = i; } } scanf("%d", &tt); for (int cases = 1; cases <= tt; cases++) { memset(a, 0, sizeof(a)); memset(map, 0, sizeof(map)); memset(mapp, 0, sizeof(mapp)); memset(fuck, 0, sizeof(fuck)); scanf("%d", &n); int sum = 0; for (int i = 1; i <= n; i++) { cin >> x; for (int j = 1; j <= d[0]; j++) { while (x%d[j] == 0) { if (!fuck[j]) { fuck[j] = true; sum++; } mapp[i][j] = mapp[i][j]^1; x = x/d[j]; } if (x == 1) break; } } sum = n; for (int i = 1; i <= 303; i++) for (int j = 1; j <= 303; j++) map[i][j] = mapp[j][i]; int t = 1; for (int i = 1; i <= 303; i++) { while (1) { if (t > n) break; bool flag = false; int j; for (j = i; j <= 303; j++) if (map[j][t] == 1) { flag = true; break; } if (flag) { swap(i, j); for (int j = i+1; j <= 303; j++)if (map[j][t] == 1) cheng(i, j); break; } else { t++; continue; } } } for (int i = 1; i <= 303; i++) { bool temp = false; for (int j = 1; j <= n; j++) if (map[i][j] == 1) { temp = true; break; } if (temp) sum--;else break; } int ans = 1; for (int i = 1; i <= sum; i++) ans = (ans*2)%mo; ans = ( ans+mo-1)%mo; printf("Case #%d:\n", cases); printf("%lld\n", ans); } }