相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4347
神犇题解Ⅰ：http://www.cnblogs.com/clrs97/p/5006924.html
神犇题解Ⅱ：http://blog.csdn.net/lych_cys/article/details/50788730
解题报告
这题暴力$DP$的复杂度是$O(nd \cdot \max \{a_i\})$的，显然不能通过此题
但我们注意到，对于一个数$a_i$来讲，小于等于它的数的NIM和不会超过$2 \cdot a_i$
于是我们将$a_i$排序之后再$DP$，每一次枚举异或值只枚举到$2 \cdot a_i$
又因为$\sum\limits_{i=1}^n{a_i} \le 10^7$ 所以公共的更新次数不会超过$2 \cdot 10^7$
于是总时间复杂度就是$O(md)$的了
虽然$md$可以到$10^8$，而且感觉这个上界非常紧的样子
给人一种严重的跑不过的感觉
但却跑得飞快？ 可能是数据比较水吧？
哦，对了，这题还卡内存
连滚动数组都给卡掉了
于是我们学习Claris的技巧，$f[k][j]$和$f[k \ xor \ a_i][j]$一起更新就可以啦！
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int M = 500009;
const int N = 1100000;
const int MOD = 1000000007;
int n,D,XOR,f[N][10],g[2][10],arr[M];
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
int main() {
n = read(); D = read();
for (int i=1;i<=n;i++) XOR ^= (arr[i] = read());
sort(arr+1, arr+1+n);
f[0][0] = 1;
for (int i=1,LIM=1;i<=n;i++) {
while (LIM <= arr[i]) LIM <<= 1;
for (int v=1,nv;v<LIM;v++) {
if ((nv=(arr[i]^v)) <= v) {
for (int d=0,t=1%D;d<D;++d,(++t)%=D) {
g[1][t] = (f[nv][t] + f[v][d]) % MOD;
g[0][t] = (f[nv][d] + f[v][t]) % MOD;
}
for (int d=0;d<D;d++) {
f[nv][d] = g[1][d];
f[v][d] = g[0][d];
}
}
}
}
if (n % D == 0) f[XOR][0]--;
printf("%d\n",(f[XOR][0]+MOD)%MOD);
return 0;
}
