石子游戏

Time Limit: 10 Sec Memory Limit: 256 MB

Description

img

Input

img

Output

输出T行，表示每组的答案。

Sample Input

3
　　1
　　1
　　2
　　1
　　0 0
　　3
　　1 2 2
　　4 4 4 4

Sample Output

1
　　0
　　6

HINT

img

Solution

这显然是一道博弈论的题目。我们发现这是一个树结构，仔细看了一下，发现这显然是一个阶梯Nim的模型。

我们将所有和同n奇偶的值XOR起来就可以得到SG。我们先判断一下，若SG=0则显然必败，否则必胜。

然后我们开始计算方案，枚举每一个节点，目标显然就是要让SG=0。

由于XOR的消去率，根据题意，可以分 2 种情况分别讨论：（根据SG异或值判断是加入还是取出。）

1. 从父亲那加入值，显然就是需要 ( SG^a[这个点] ) - a[这个点的父亲] <= a[这个点]，这样才可以通过加入若干个值使得SG=0；
　　2. 把值给儿子，显然需要 (SG^a[这个点]) <= a[这个点]，这样才可以通过拿走若干的值使得SG=0。

然后我们讨论一下是否为叶子节点：

1. 非叶节点，若从父亲那加入值只有1的贡献，把值给儿子（由于有两个儿子）所以贡献为2；
　　2. 叶子节点，从父亲那加入值或者彻底删去都显然只有1的贡献。

这样就可以求出方案数了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;

const int ONE = 10001;
const int INF = 214783640;
const int MOD = 1e9+7;

int T;
int n;
int x,num;
int a[17][65537];
int SG,Ans;

int get()
{
    int res=1,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Solve()
{
    n=get();
    SG=Ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=(1<<(i-1));j++)
        {
            a[i][j]=get();
            if(i%2==n%2)    SG ^= a[i][j];
        }
    if(!SG) {printf("0"); return;}

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=(1<<(i-1));j++)
            if(i%2==n%2)
            {
                if(i!=n)
                {
                    if( (SG^a[i][j]) <= a[i][j]) Ans+=2;
                    if( (SG^a[i][j]) > a[i][j] && (SG^a[i][j]) - a[i-1][(j-1)/2+1] <= a[i][j]) Ans+=1;
                }
                if(i==n)
                {
                    if( (SG^a[i][j]) <= a[i][j] ) Ans++;
                    if( (SG^a[i][j]) > a[i][j] && (SG^a[i][j]) - a[i-1][(j-1)/2+1] <= a[i][j] ) Ans++;
                }
            }
    }

    printf("%d",Ans);
}

int main()
{
    T=get();
    while(T--)
        Solve(),printf("\n");
}