2015
04-14

# Game

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 730    Accepted Submission(s): 288

Problem Description
Mr.Frost is a child who is too simple, sometimes naive, always plays some simple but interesting games with his friends. Today，he invents a new game again:
At the beginning of the game they pick N (1<=N<=100) piles of stones, Mr.Frost and his friend move the stones in turn. At each step of the game, the player chooses a pile, removes at least one stone from the pile, the first player can’t make a move, and loses.
So smart is the friends of Mr.Frost that Mr.Frost always loses. Having been a loser for too many times, he wants to play a trick. His plan is to remove some piles, and then he can find a way to make sure that he would be the winner after his friends remove
stones first.

Now, he wants to know how many ways to remove piles which are able to achieve his purpose. If it’s impossible to find any way, please print “-1”.

Input
The first line contains a single integer t (1<=t<=20), that indicates the number of test cases. Then follow the t cases. Each test case begins with a line contains an integer N (1 <= N <= 100), representing the number of the piles. The next n lines, each of
which has a positive integer Ai(1<=Ai<=2^31 – 1) represent the number of stones in this pile.

Output
For each case, output a line contains the number of the way mod 1000007, If it’s impossible to find any way, please print “-1”.

Sample Input
2 2 1 1 3 1 2 3

Sample Output
2 2

Source

这道题目是和博弈论挂钩的高斯消元。本题涉及的博弈是nim博弈，结论是：当先手处于奇异局势时（几堆石子数相互异或为0），其必败。

那么我们就可以把题目转化成求n堆石子中的k堆石子数异或为0的情况数。使用x1—xn表示最终第i堆石子到底取不取（1取，0不取），将每堆石子数画成2进制的形式，列成31个方程来求自由变元数，最后由于自由变元能取1、0两种状态，所以，最终答案是2^k。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int a[33][110];
int equ,var;

int Gauss()
{
int k,col,max_r;

for(k=0,col=0; k<equ&&col<var; k++,col++)
{
if(a[k][col]==0)
{
max_r=k;
for(int i=k+1; i<equ; i++)
if(a[i][col]>a[max_r][col])
{
max_r=i;break;
}

if(max_r!=k)
for(int i=0; i<=var; i++)
{
swap(a[max_r][i],a[k][i]);
}
}

if(a[k][col]==0)
{
k--;
continue;
}

for(int i=k+1; i<equ; i++)
{
if(a[i][col])
for(int j=col; j<=var; j++)
{
a[i][j]=a[i][j]^a[k][j];
}
}
}

return k;
}

int main()
{
equ=31;
int cas,n,X,mod=1000007;
scanf("%d",&cas);
while(cas--)
{
memset(a,0,sizeof(a));
scanf("%d",&n);
var=n;
for(int i=0;i<n;i++)
{
scanf("%d",&X);
int t=0;
while(X)
{
a[t++][i]=X&1;
X>>=1;
}
}
int k=Gauss(),ans=1;
k=n-k;
for(int i=0;i<k;i++)
{
ans=(ans*2)%mod;
}
printf("%d\n",ans);
}
return 0;
}

1. 我给你模拟一个例子好了。某型飞机空重12吨，最大起飞重量20吨。最大载重5吨。最大载油5吨。假设满载弹药5吨，最多可以载油3吨这个很好理解。那么载油只有1吨，是不是可以载7吨弹药呢？ 答案是不行。

2. 我给你模拟一个例子好了。某型飞机空重12吨，最大起飞重量20吨。最大载重5吨。最大载油5吨。假设满载弹药5吨，最多可以载油3吨这个很好理解。那么载油只有1吨，是不是可以载7吨弹药呢？ 答案是不行。

3. 我给你模拟一个例子好了。某型飞机空重12吨，最大起飞重量20吨。最大载重5吨。最大载油5吨。假设满载弹药5吨，最多可以载油3吨这个很好理解。那么载油只有1吨，是不是可以载7吨弹药呢？ 答案是不行。

4. 我给你模拟一个例子好了。某型飞机空重12吨，最大起飞重量20吨。最大载重5吨。最大载油5吨。假设满载弹药5吨，最多可以载油3吨这个很好理解。那么载油只有1吨，是不是可以载7吨弹药呢？ 答案是不行。

5. 我给你模拟一个例子好了。某型飞机空重12吨，最大起飞重量20吨。最大载重5吨。最大载油5吨。假设满载弹药5吨，最多可以载油3吨这个很好理解。那么载油只有1吨，是不是可以载7吨弹药呢？ 答案是不行。

6. 我给你模拟一个例子好了。某型飞机空重12吨，最大起飞重量20吨。最大载重5吨。最大载油5吨。假设满载弹药5吨，最多可以载油3吨这个很好理解。那么载油只有1吨，是不是可以载7吨弹药呢？ 答案是不行。

7. 我给你模拟一个例子好了。某型飞机空重12吨，最大起飞重量20吨。最大载重5吨。最大载油5吨。假设满载弹药5吨，最多可以载油3吨这个很好理解。那么载油只有1吨，是不是可以载7吨弹药呢？ 答案是不行。

8. 我给你模拟一个例子好了。某型飞机空重12吨，最大起飞重量20吨。最大载重5吨。最大载油5吨。假设满载弹药5吨，最多可以载油3吨这个很好理解。那么载油只有1吨，是不是可以载7吨弹药呢？ 答案是不行。

9. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

10. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}