[SDOI2011]黑白棋

Description

小A和小B又想到了一个新的游戏。

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

最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。

小A可以移动白色棋子，小B可以移动黑色的棋子，他们每次操作可以移动1到d个棋子。

每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。

小A和小B轮流操作，现在小A先移动，有多少种初始棋子的布局会使他胜利呢？

Input

共一行，三个数，n,k,d。

Output

输出小A胜利的方案总数。答案对1000000007取模。

Sample Input

10 4 2

Sample Output

182

HINT

1<=d<=k<=n<=10000, k为偶数，k<=100。

考虑黑白棋是相间的

那么第i个白棋和第i个黑棋之间距离为dis，那么我们看做一堆石头数为

dis的堆

一次操作等价于移除不超过d堆的任意石子

这就是Nimk游戏

先手必败当且仅当所有石子数的二进制每一位为1的个数都能被(d+1)整除

用所有情况减去不合法的情况

于是DP

令$f[i][j]$表示第i位，石子数和为j的不合法方案数

$f[i+1][j+x*(d+1)*(1<<i)]+=f[i][j]$

石子数和<=n-k,堆数k/2

接下来统计答案

$ans=C_{n}^{k}-\sum_{i=0}^{n-k}f[16][i]*C_{n-k-i+k/2}^{k/2}$

后面那个组合数是分配剩下的空格在每对棋子中间

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long lol;

 lol C[][],Mod=1e9+;

 lol f[][],n,k,d,pw[],ans;

 int main()

 {lol i,j,l;

     cin>>n>>k>>d;

     pw[]=;

     for (i=;i<=;i++)

     pw[i]=pw[i-]*;

     f[][]=;

     C[][]=C[][]=;

     for (i=;i<=n;i++)

     {

         C[i][]=;

         for (j=;j<=min(i,k);j++)

         {

             C[i][j]=(C[i-][j-]+C[i-][j])%Mod;

         }

     }

     for (i=;i<;i++)

     {

         for (j=;j<=n-k;j++)

         {

             for (l=;l*(d+)<=k/&&l*(d+)*pw[i]+j<=n-k;l++)

             {

                 f[i+][j+l*(d+)*pw[i]]+=f[i][j]*C[k/][l*(d+)]%Mod;

                 f[i+][j+l*(d+)*pw[i]]%=Mod;

             }

         }

     }

     ans=C[n][k];

     for (i=;i<=n-k;i++)

     ans=(ans-f[][i]*C[n-i-k+k/][k/]%Mod+Mod)%Mod;

     cout<<ans;

 }