解题：POI 2016 Nim z utrudnieniem

题面

出现了，神仙题！

了解一点博弈论的话可以很容易转化题面：问$B$有多少种取(diu)石子的方式使得取后剩余石子异或值为零且取出的石子堆数是$d$的倍数

首先有个暴力做法：$dp[i][j][k]$表示到第$i$个为止取出来的石子数目模$d$等于$j$且剩下的石子异或和为$k$的方案数，然后就枚举转移啊=。=

发现时空复杂度好像都不能承受，不过可以尝试分析/优化一下。首先分析一波后发现时间复杂度其实是对的......只是我们需要将石子数从小到大排个序，这样一路异或下来异或到$i$时最大值不超过$2*a[i]$，复杂度是$O(dm)$的

然后根据POI的传统我们还不能滚动数组，需要卡空间......那就抓个临时数组记录一下算了=。=

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1050000,K=11,mod=1e9+7;
int sto[N],mem[N],dp[K][N];
int n,d,ans,goal,maxx;
int main ()
{
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++)
        scanf("%d",&sto[i]),goal^=sto[i];
    sort(sto+1,sto+n+1),dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        while(maxx<=sto[i]) maxx=maxx<<1|1;
        for(int j=0;j<=maxx;j++)
            mem[j]=(dp[0][j]+dp[d-1][j^sto[i]])%mod;
        for(int j=d-1;j;j--)
            for(int k=0;k<=maxx;k++)
                dp[j][k]+=dp[j-1][k^sto[i]],dp[j][k]%=mod;
        for(int j=0;j<=maxx;j++) dp[0][j]=mem[j];
    }
    ans=(dp[0][goal]-(n%d==0)+mod)%mod;
    printf("%d",ans);
    return 0;
}