【HDU】3915 Game

题意：有n堆石子，每个人只能从某一堆至少拿走一个，不能拿者败。问事先拿走某些堆的石子，使得先手必败。

由结论可知，石子数异或等于0时，先手必败。

将石子拆成二进制，未知数为1表示保留该堆石子，为0表示事先拿走该堆石子。最后2^(自由元的个数)%MOD就是答案。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define MAXN 110
 4 #define MOD 1000007
 5 using namespace std;
 6 int a[MAXN], g[MAXN][MAXN];
 7 int Gauss(int n) {
 8     int i, j, r, c, cnt;
 9     for (c = cnt = 0; c < n; c++) {
10         for (r = cnt; r < 31; r++) {
11             if (g[r][c])
12                 break;
13         }
14         if (r < 31) {
15             if (r != cnt) {
16                 for (i = 0; i < n; i++)
17                     swap(g[r][i], g[cnt][i]);
18             }
19             for (i = cnt + 1; i < 31; i++) {
20                 if (g[i][c]) {
21                     for (j = 0; j < n; j++)
22                         g[i][j] ^= g[cnt][j];
23                 }
24             }
25             cnt++;
26         }
27     }
28     return n - cnt;
29 }
30 int main() {
31     int c;
32     int n, i, j;
33     int ans, vary;
34     scanf("%d", &c);
35     while (c--) {
36         scanf("%d", &n);
37         for (i = 0; i < n; i++)
38             scanf("%d", &a[i]);
39         for (i = 0; i < 31; i++) {
40             for (j = 0; j < n; j++)
41                 g[i][j] = (a[j] >> i) & 1;
42         }
43         vary = Gauss(n);
44         for (ans = 1; vary--;) {
45             ans <<= 1;
46             ans %= MOD;
47         }
48         printf("%d\n", ans);
49     }
50     return 0;
51 }