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[19],C[N][209],f[19][N];

void Init()
{
    p[0]=1;
    for (int i=1; i<=16; ++i) p[i]=p[i-1]<<1;
    C[0][0]=1;
    for (int i=1; i<=n; ++i)
        for (int j=0; j<=min(2*k,(LL)i); ++j)
        {
            (C[i][j]+=C[i-1][j])%=MOD;
            if (j) (C[i][j]+=C[i-1][j-1])%=MOD;
        }
}

int main()
{
    scanf("%lld%lld%lld",&n,&k,&d);
    Init();
    f[0][0]=1;
    for (int i=1; i<=15; ++i)
        for (int j=0; j<=n-k; ++j)
            for (int l=0; l*(d+1)<=k/2&&l*(d+1)*p[i-1]<=j; ++l)
                (f[i][j]+=f[i-1][j-l*(d+1)*p[i-1]]*C[k/2][l*(d+1)]%MOD)%=MOD;
    LL ans=0;
    for (int i=0; i<=n-k; ++i)
        (ans+=f[15][i]*C[n-k/2-i][k/2]%MOD)%=MOD;
    ans=(C[n][k]-ans+MOD)%MOD;
    printf("%lld\n",ans);
}