题目描述：

这个游戏是在一个1*n的棋盘上进行的，棋盘上有k个棋子，一半是黑色，一半是白色。最左边是白色棋子，最右边

是黑色棋子，相邻的棋子颜色不同。

小奇可以移动白色棋子，提比可以移动黑色的棋子，它们每次操作可以移动1到d个棋子。每当移动某一个棋子时，

这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。小奇和提比轮流操作，现在

小奇先移动，有多少种初始棋子的布局会使它有必胜策略？

算法标签：dp,博弈

总觉得所有博弈问题的转化都很神奇，可能（肯定）是因为我是菜鸡。

思路：

对于每一对黑子与白子，向中间靠拢最优，相当于是有(k/2)堆石子，每次一个人可以选择不超过d堆取走若干个石子，是经典的NIM算法。

关于Nim算法：

基本：

n堆石子一人每次在一堆中取若干个，谁先取不到输，石子每堆个数异或值，为0为先手必败，其余为先手必胜。

本题稍拓展：

n堆石子每人挑至多d堆取若干个，将石子进行二进制拆分，拆分后每一位相加（不进位），若每一位%(d+1)都等于0，则为先手必败，其余为先手必胜。

于是考虑本题，对于方案数，显然考虑先手必败的情况更容易，于是我们用总方案数-先手必败方案数，即为答案。

令f[i][j]，i表示前i个二进制位，用了j个单位的方案数。

转移：枚举每次在当前位加了多少个（d+1）。由于还要列举这些加一放在哪个数字上，以及每个棋子的初始位置等等，有一些地方要灵活运用组合数。

以下代码：

#include
        
         #define il inline#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=1e4+5,p=1e9+7;int n,k,d,c[N][105],f[20][N],ans;il int read(){
      int x;char ch;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x;}il int mu(int x,int y){
      if(x+y>=p)return x+y-p;return x+y;}int main(){    n=read();k=read();d=read();    for(int i=0;i<=n;i++){        c[i][0]=1;for(int j=1;j<=k&&j<=i;j++)c[i][j]=mu(c[i-1][j-1],c[i-1][j]);    }    f[0][0]=1;    for(int i=0;i<16;i++)for(int j=0;j<=n-k;j++)        for(int z=0;(1<
         
          <=j&&(d+1)*z<=(k>>1);z++){            f[i+1][j]=mu(f[i+1][j],1ll*f[i][j-(1<
          
           >1][(d+1)*z]%p);        }    for(int i=0;i<=n-k;i++)ans=mu(ans,1ll*f[16][i]*c[n-i-(k>>1)][k>>1]%p);    ans=mu((c[n][k]-ans)%p,p);printf("%d\n",ans);    return 0;}