题目链接：见这里 题意：有n堆石子，每个人只能从某一堆至少拿走一个，不能拿者败。问事先拿走某些堆的石子，使得先手必败。 解法：简单的高斯消元的应用，要求的就是给定n个数中选k个数异或为0的方法数。将n个数用二进制写成n列，之后就很明显了，未知数x1–xn非1即0，表示第i个数取不取。 用高斯消元计算出有多少不确定的变元，这些变元要么是1，要么是0，所以答案即为2的变元数次方。
//HDU 3951#include <bits/stdc++.h>using namespace std;int A[105][105];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 T, n, ks = 0; scanf("%d", &T); while(T--){ scanf("%d", &n); int maxp = 0; memset(A, 0, sizeof(A)); for(int i = 0; i < n; i++){ int x; scanf("%d", &x); int cnt = 0; while(x != 0){ A[cnt++][i] = x&1; x >>= 1; } maxp = max(maxp, cnt); } for(int i = 0; i < maxp; i++) A[i][n] = 0; int cc = xor_guass(maxp, n); int ans = 1; for(int i = 0; i < n - cc; i++) ans = ans * 2 % 1000007; PRintf("%d/n", ans); } return 0;}新闻热点
疑难解答
