题解 P5970 【[POI2016]Nim z utrudnieniem】

· · 题解

发现自己两年前做的题目洛谷上有了，开心。其实题解也是那个时候写的。

Nim游戏中，当a_1\bigoplus a_2\bigoplus a_3 \bigoplus \cdots \bigoplus a_n=0的时候，先手必输。

由此我们要在原来的局面中让后手取k\times d堆，让先手输，可以用到异或的一个性质：对于任何整数A，必然有A \bigoplus A=0，因此我们可以记录原来n堆石子的异或和s，也就是把题目的意思转换为了取k\times d堆石子，问有多少种方法让取到的石子堆中每堆石子的异或和为s

这样我们就可以转移一个DP方程。我们设f_{i,j,k}表示处理完i堆石子，取的堆数在\mod j意义下取了的石子的异或和为k的情况。

这个时候则有：f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k\bigoplus {a_i}}

这样做的话，时间复杂度为O(n \times d \times maxa)，会TLE

有一个很巧妙的想法是：因为对于任意一个正整数A，它和比它自己小的数字异或起来的结果不会超过A \times 2，由此可以得出：a_i和比a_i小的数字的异或和不会超过2\times a_i，因此我们可以直接对石子排序，这样的时间复杂度就可以减少到O(n \times d)

最后有个小细节要注意一下：当d|n的时候，结果要减去1

然后后来就在bzoj上rank1了。（现在rank3）

/**************************************************************
    Problem: 4347
    User: rourou
    Language: C++
    Result: Accepted
    Time:9516 ms
    Memory:52464 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cctype>

using namespace std;

int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

const int MOD=1e9+7;

int n,d,a[500050],f[11][1050000],g[1050000];

int main()
{
    n=read(),d=read();
    int s=0;
    for (int i=1;i<=n;i++)
        s^=(a[i]=read());
    sort(a+1,a+n+1);
    f[0][0]=1;
    int u=1;
    for (int i=1;i<=n;i++)
    {
        while (u<=a[i])
            u<<=1;
        for (int j=0;j<u;j++)
            g[j]=(f[d-1][j^a[i]]+f[0][j])%MOD;
        for (int j=d-1;j>0;j--)
            for (int k=0;k<u;k++)
                f[j][k]=(f[j][k]+f[j-1][k^a[i]])%MOD;
        for (int j=0;j<u;j++)
            f[0][j]=g[j];
    }
    if (n%d==0)
        f[0][s]--;
    if (f[0][s]<0)
        f[0][s]+=MOD;
    cout << f[0][s] << endl;
    return 0;
}