自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:16:06，当前版本为作者最后更新于2020-06-01 17:13:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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;
}