P2490 [SDOI2011]黑白棋
题意
一个 (1*n) 的棋盘上，A 可以移动白色棋子，B 可以移动黑色的棋子，其中白色不能往左，黑色不能往右。他们每次操作可以移动 1 到 (d) 个棋子。
每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。
思路
显然可以将题意转化为一种 K-Nim 游戏，即在 (frac k2) 堆石子中，每次可将 (d) 堆石子取任意个，令对手无路可走时获胜。
用总方案数减去先手必败的方案数即为答案，因为先手必败方案更加好算。
K-Nim 游戏
结论
设 (r_i) 为二进制第 (i) 位所有数该位为 1 的个数 (pmod {d+1}) 的值，那么只用一步即可在 “(r) 全为 0” 和 “(r) 不全为 0” 两种状态间转移。
感性证明
考虑一个大小不超过 (d) 的集合，为我们一次操作需要拿走的石子堆的集合，选 0 或 1 都是合法的。
假设我们现在已经有这样一个大小为 (d) 的集合，其中有 (x) 个 1，(y) 个 0，即 (x+y=d)。我们要让 (r) 等于零，分以下情况：
- (xge r) 则选择 (r) 个 1 变为 0 即可。
- (x<r) 则 (y+rge d+1) ，则选择 (d-r+1) 个 0 变为 1 即可。
所以一定有一种方法使这一位的 (r) 变成 0.
现在我们并没有一个可以随便转换的集合，但是当一个数的高位从 1 变为 0 之后低位就可以随便选 0 和 1.所以我们从高位向低位考虑，如果一直符合第二个情况就向下考虑，否则就是第一个情况，并且在这种情况下把 1 变成 0 是合法的，那么我们扩大集合即可。
得证。
在上述博弈中，所有 (r) 为 0 的状态是必败态。我们只需要算所有这种情况的方案就可以了。
考虑 Dp。设 (f_{ij}) 为前 (i) 位的 (r) 均为 0，总共 (j) 个石子的方案数。
新选一位，枚举在 (d+1) 堆石子中放入若干次石子。即
最后统计答案需要枚举每一堆的起点位置，即在原题中的白棋的位置，答案为所有位的
的和。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=10005,mod=1e9+7;
int n,k,d,C[maxn][205],f[18][100005];
inline void work(){
n=read(),k=read(),d=read();
C[0][0]=1;
for(int i=1;i<=n;i++){
C[i][0]=1;
for(int j=1;j<=200;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
f[0][0]=1;
for(int i=0;i<=16;i++) for(int j=0;j<=n-k;j++) for(int x=0;(1ll<<i)*x*(d+1)<=n-k and x*(d+1)<=k/2;x++)
f[i+1][j+(1ll<<i)*x*(d+1)]=(f[i+1][j+(1ll<<i)*x*(d+1)]+1ll*f[i][j]*C[k/2][x*(d+1)])%mod;
int ans=0;
for(int i=0;i<=n-k;i++) ans=(ans+1ll*f[17][i]*C[n-i-k/2][k/2])%mod;
printf("%d
",(C[n][k]-ans+mod)%mod);
}
}
signed main(){
star::work();
return 0;
}