HDU 5833 Zhu and 772002 高斯消元解异或方程组，求*元个数，bitset压位

Zhu and 772002 Time Limit: 2000/1000 MS (java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1799 Accepted Submission(s): 624

PRoblem Description Zhu and 772002 are both good at math. One day, Zhu wants to test the ability of 772002, so he asks 772002 to solve a math problem.

But 772002 has a appointment with his girl friend. So 772002 gives this problem to you.

There are n numbers a1,a2,…,an. The value of the prime factors of each number does not exceed 2000, you can choose at least one number and multiply them, then you can get a number b.

How many different ways of choices can make b is a perfect square number. The answer maybe too large, so you should output the answer modulo by 1000000007.

Input First line is a positive integer T , represents there are T test cases.

For each test case:

First line includes a number n(1≤n≤300)，next line there are n numbers a1,a2,…,an,(1≤ai≤1018).

Output For the i-th test case , first output Case #i: in a single line.

Then output the answer of i-th test case modulo by 1000000007.

Sample Input

2 3 3 3 4 3 2 2 2

Sample Output

Case #1: 3 Case #2: 3

解题方法： 白书原题，看这位小哥的吧。见这里

//HDU 5833 XOR GUASS #include <bits/stdc++.h> using namespace std; const int maxn = 2010; typedef long long LL; typedef int Matrix[maxn][maxn]; const int mod = 1000000007; Matrix A; //A[i][j]就表示第j个数的这个i素数是奇数还是偶数 int n, vis[2010], prime[2010]; int pre_deal(int m){ memset(vis, 0, sizeof(vis)); int cnt = 0; for(int i = 2; i < m; i++){ if(!vis[i]){ prime[cnt++] = i; for(int j = i*i; j < m; j += i){ vis[j] = 1; } } } return cnt; } LL powmod(LL a, LL n){ LL res = 1; while(n){ if(n&1) res = res*a%mod; a = a*a%mod; n >>= 1; } return res; } int xor_guass(int m, int n) //A是异或方程组系数矩阵 返回秩 { int i = 0, j = 0, k, r, u; while(i < m && j < n){//当前正在处理第i个方程,第j个变量 r = i; for(int k = i; k < m; k++) if(A[k][j]){r = k; break;} if(A[r][j]){ if(r != i) for(k = 0; k <= n; k++) swap(A[r][k], A[i][k]); //消元完成之后第i行的第一个非0列是第j列,且第u>i行的第j列全是0 for(u = i + 1; u < m; u++) if(A[u][j]) for(k = i; k <= n; k++) A[u][k] ^= A[i][k]; i++; } j++; } return i; } int main() { int tot = pre_deal(maxn); int T, ks = 0; scanf("%d", &T); while(T--){ memset(A, 0, sizeof(A)); scanf("%d", &n); int maxp = 0; for(int i = 0; i < n; i++){ LL x; scanf("%lld", &x); for(int j = 0; j < tot; j++){ while(x % prime[j] == 0){ maxp = max(maxp, j); x /= prime[j]; A[j][i] ^= 1; } } } int rr = xor_guass(maxp + 1, n);//秩 printf("Case #%d:\n", ++ks); printf("%lld\n", powmod(2, n - rr) - 1); } return 0; }

当然我们不能这样A了就算了，在大白树上提到了一种bitset优化的方法，即是bitset压位优化。即是把32列合并到一个无符号32位整数中，然后只需要用一次逐位异或xor就可以处理32列了，所以复杂度可以降到O(n*n*n/32)，扣扣常数还是非常支持的。

//HDU 5833 XOR GUASS bitset #include <bits/stdc++.h> using namespace std; const int maxn = 2005; const int mod = 1e9+7; int n, vis[maxn], prime[maxn], cnt; void pre_deal(){ for(int i = 2; i < maxn; i++){ if(vis[i]) continue; prime[cnt++] = i; for(int j = i; j < maxn; j += i) vis[j] = 1; } } bitset <330> A[305]; //A[i][j]就表示第j个数的这个i素数是奇数还是偶数 int main() { pre_deal(); int T, ks = 0; scanf("%d", &T); while(T--){ printf("Case #%d:\n", ++ks); for(int i = 0; i < 305; i++) A[i].reset(); 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%prime[j] == 0){ int flag = 0; while(x%prime[j] == 0){ x /= prime[j]; flag ^= 1; } A[j][i] = flag; } } } int i = 0, j = 0; //xor消元之后j就是秩 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; ans--; printf("%d\n", ans); } return 0; }

所以一下午只写了2个高斯消元？？效率需要挺高啦。