2018 Multi-University Nowcoder Round 8 - H Playing games（FWT,博弈）

发表于 | 分类于 ，

H-Playing games
Nim博弈模型，在所给的n堆中选择使后手必胜的最大堆数

题意

在$n$堆石子中选择最大数量的堆数，使得对于取出的$n$堆石子，在进行Nim游戏时后手必胜。

这样例膜得也太暴力了吧，苟利苟利苟利.jpg

解法

对于Nim游戏的局面，当且仅当$a_1⊕ a_2⊕ a_3…⊕ a_n=0$时，它是P-position（后手必胜），其中⊕ 表示异或(XOR)运算。

此题可以转化为，在$n$个数中寻找最多的数，使SUM_XOR=0.

我们再将题意转化为，在$n$个数中寻找最少的数，使SUM_XOR=C，其中，$C=a_1⊕ a_2⊕ ……⊕ a_n$

此处引入Fast Walsh-Hadamard Transform(FWT,快速沃尔什变换)求解。

Fast Walsh-Hadamard Transform

FWT的详解参考：

快速沃尔什转换 - 维基百科
Fast Walsh-Hadamard Transform
FWT快速沃尔什变换学习笔记

FWT是用于解决多项式位运算卷积的一类方法，如下：

$$C_k=\sum_{i⊕j=k}A_i*B_j$$

对于数组A，我们设其在经过快速沃尔什变换后记作$FWT[A]$

我们需要一个新序列C，由序列A和序列B经过某运算规则得到，即$C=A⊕B$

我们先正向得到$FWT[A],FWT[B]$，然后根据$FWT[C]=FWT[A]*FWT[B]$求出$FWT[C]$，然后逆向运算得到原序列C，复杂度为$O(nlog(n))$

对于异或（XOR）卷积有：

$$tf(A)=(tf(A_0)+tf(A_1)),tf(A_0)-tf(A_1)) $$
$$utf(A)=(utf(\frac{A_0+A_1}{2}),utf(\frac{A_0-A_1}{2}))$$

1
2
3
4
5
6
7
8
9
10
11
void FWT_xor(int *a,int opt)
{
    for(int i=1;i<N;i<<=1)
        for(int p=i<<1,j=0;j<N;j+=p)
            for(int k=0;k<i;++k)
            {
                int X=a[j+k],Y=a[i+j+k];
                a[j+k]=(X+Y)%MOD;a[i+j+k]=(X+MOD-Y)%MOD;
                if(opt==-1)a[j+k]=1ll*a[j+k]*inv2%MOD,a[i+j+k]=1ll*a[i+j+k]*inv2%MOD;
            }
}

对于本题，我们考虑将$a_i$的每一维拆开，看作一个$d$维向量，由于$a_i<2^{19}$，取$d=19$

二分答案，取其在异或卷积意义下的$k$次幂，判断能否合成C即可。

代码

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
#include <cstdio>

using namespace std;
typedef long long ll;

const int maxn=1<<19,mod=1e9+7;
int a[maxn],b[maxn];
int l,r,mid;

void FWT(int *a,int n)
{
    for(int i=1;i<n;i<<=1)
        for(int p=i<<1,j=0;j<n;j+=p)
            for(int k=0;k<i;k++)
            {
                int x=a[j+k],y=a[i+j+k];
                a[j+k]=(x+y)%mod;a[i+j+k]=(x+mod-y)%mod;
            }
}

int main()
{
    int n,x,aim=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++) 
    {
        scanf("%d",&x);
        aim^=x;
        a[x]++;
    }
    if(!aim) return 0*printf("%d\n",n);
    int l=0,r=19,mid;
    a[0]++;
    FWT(a,1<<19);
    while(r-l>1)
    {
        mid=(l+r)/2;
        for(int i=0;i<(1<<19);i++)
        {
            b[i]=1;
            for(int j=0;j<mid;j++)
                b[i]=1ll*b[i]*a[i]%mod;
        }
        FWT(b,1<<19);
        if(b[aim]) r=mid; 
        else l=mid;
    }
    printf("%d\n",n-r);
    return 0;
}