BZOJ2281:[SDOI2011]黑白棋(博弈论,组合数学,DP)

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。

Solution

我组合计数和$DP$真的是菜的真实……

首先这个题必须加一个限制条件：先手只能向右，后手只能向左，不然下面的做法会被黄学长找出来反例……？QAQ 不过还是能过的我也不知道为什么

首先比较容易发现，因为每个人操作的方向是一定的，所以可以把一对相邻的黑白棋中间的格子数看成一堆石子，那么这个就变成了一个有$k/2$堆的$Nim$游戏。只不过这个$Nim$游戏一次可以取$1 \sim d$堆，也就是$k-Nim$游戏。

$k-Nim$游戏的先手必败态是把每堆石子转换为二进制后，其中每一位上为1的个数和都能被$(d+1)$整除。

感性理解还是挺正确的……具体证明戳这里吧。

然后就可以开始$DP$了。设$f[i][j]$表示$DP$到了二进制的第$i$位，用了$j$个棋子的必败态方案数。

$f[i][j]= \sum f[i-1][j-l \times (d+1) \times 2^i]*C_{k/2}^{l \times (d+1)}$

（这一次用了$l \times (d+1) \times 2^i$个石子，乘组合数是因为从$k/2$堆石子里选出$k \times (d+1)$堆。）

最后答案为$C_n^k-\sum_{i=0}^{n-k}f[15][i] \times C_{n-k/2-i}^{k/2}$

（乘组合数是因为每对棋子在棋盘上的距离确定了，就差每对棋子的排列方式了。）

Code

 #include<iostream>

 #include<cstdio>

 #define N (10009)

 #define LL long long

 #define MOD (1000000007)

 using namespace std;

 LL n,k,d,p[],C[N][],f[][N];

 void Init()

 {

     p[]=;

     for (int i=; i<=; ++i) p[i]=p[i-]<<;

     C[][]=;

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

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

         {

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

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

         }

 }

 int main()

 {

     scanf("%lld%lld%lld",&n,&k,&d);

     Init();

     f[][]=;

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

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

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

                 (f[i][j]+=f[i-][j-l*(d+)*p[i-]]*C[k/][l*(d+)]%MOD)%=MOD;

     LL ans=;

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

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

     ans=(C[n][k]-ans+MOD)%MOD;

     printf("%lld\n",ans);

 }

巴特西