BZOJ

分析

后手必胜当且仅当每堆石子个数异或和为 $0$。

设 $dp_{i,j,k}$ 表示前 $i$ 堆石子，扔掉的堆数模 $d$ 等于 $j$，扔掉的每堆石子个数异或和为 $k$ 的方案数。然而这样子复杂度是 $\mathcal{O}(nmd)$ 的，显然过不了。

考虑一个优化：把所有堆按石子个数从小到大排序，这样子加进第 $i$ 堆时异或和不会超过 $2^{\operatorname{highbit(i)}+1}-1$。这样子复杂度降到了 $\mathcal{O}(md)$。

现在的问题是空间太大了。容易想到将 $i$ 滚动掉，但是空间还是太大。因此我们要想办法把 $i$ 一维去掉。

这个比较简单：在每一层 $i$ 时，按照 $k$ 从大到小的转移顺序转移即可。注意 $dp_{i-1,d-1,k}$ 要存下来不然 $dp_{i,0,k}$ 无法转移。

然后答案就是 $dp_{n,0,sum}$ （$sum$ 表示 $\bigoplus_{i=1}^na_i$）。注意当 $d|n$ 时答案要减 $1$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+5;
const int mod=1e9+7;

int n,d,a[N];
int dp[11][1<<20],tmp[1<<20];

int main() {
    n=read(),d=read(); int sum=0;
    for (re int i=1;i<=n;++i) a[i]=read(),sum^=a[i];
    sort(a+1,a+n+1);
    dp[0][0]=1;
    for (re int i=1;i<=n;++i) { int lim=1;
        while (lim<=a[i]) lim<<=1;
        for (re int j=0;j<lim;++j) tmp[j]=dp[d-1][j];
        for (re int k=d-1;k;--k)
            for (re int j=0;j<lim;++j)
                dp[k][j]=(dp[k][j]+dp[k-1][j^a[i]])%mod;
        for (re int j=0;j<lim;++j) dp[0][j]=(dp[0][j]+tmp[j^a[i]])%mod;
    }
    printf("%d\n",(dp[0][sum]-(n%d==0)+mod)%mod);
    return 0;
}