黑白棋（game）
【问题描述】
小A和小B又想到了一个新的游戏。
这个游戏是在一个1*n的棋盘上进行的，棋盘上有k个棋子，一半是黑色，一半是白色。
最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。
小A可以移动白色棋子，小B可以移动黑色的棋子，他们每次操作可以移动1到d个棋子。
每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。
小A和小B轮流操作，现在小A先移动，有多少种初始棋子的布局会使他胜利呢？
【输入格式】
共一行，三个数，n,k,d。
【输出格式】
输出小A胜利的方案总数。答案对1000000007取模。
【样例输入】
10 4 2
【样例输出】
182
【数据规模和约定】
对于30%的数据，有 k=2。
对于100%的数据，有1<=d<=k<=n<=10000, k为偶数，k<=100。
【思路】
博弈+组合计数
将相邻黑白点看作是一堆石子，则问题转化为Nimk游戏，即有n堆石子每次可以在1~d堆中拿出任意不为0个数的石子，什么时候局面必胜。
结论：当且仅当nim和中1的个数为d+1的倍数，有局面必败。每次最多只能使d个为0，先手不能转移到必败态 ，则后手可以通过操作获胜。
补集转化，求先手必败的局面数。
设f[i][j]表示nim和前i位中有j个的先手必败的方案数，枚举 d+1 的倍数转移：
f[i][j+k*(d+1)*(1<<i)]+=f[i][j]*C(K/2,k*(d+1))
则最后答案为C(n,K)-sigma{ f[15][i]*C(n-i-K/2,K/2) }
【代码】
#include<cstdio>
#include<iostream>
using namespace std; typedef long long LL;
const int N = *1e4+;
const int M = *1e2+;
const int MOD = 1e9+; LL c[N][M],f[M][N]; void get_c() {
for(int i=;i<N;i++) c[i][]=;
for(int i=;i<N;i++) {
for(int j=;j<=min(i,M-);j++)
c[i][j]=(c[i-][j-]+c[i-][j])%MOD;
}
}
LL C(int n,int k) {
if(k>n-k) k=n-k; return c[n][k];
} int n,K,D; int main() {
get_c();
scanf("%d%d%d",&n,&K,&D);
K>>=;
f[][]=;
for(int i=;i<;i++)
for(int j=;j<=n-*K;j++)
for(int k=;k*(D+)<=K && j+k*(D+)*(<<i)<=n-*K;k++)
f[i+][j+k*(D+)*(<<i)]=(f[i+][j+k*(D+)*(<<i)]+f[i][j]*C(K,k*(D+))%MOD)%MOD;
LL ans=;
for(int i=;i<=n-*K;i++)
ans=(ans+f[][i]*C(n-i-K,K)%MOD)%MOD;
printf("%lld",(C(n,*K)-ans+MOD)%MOD);
return ;
}