题解 P2490 【[SDOI2011]黑白棋】

· · 题解

感觉大家的题解的dp部分挺不错的了，但是k-nim部分还是不太好。这篇题解会主要讲解k-nim。

k-nim游戏是这样的：

有N堆石子，每次可以从不超过k堆中各取一些石子，不能操作者败。

这题的转化就是将相邻的白左黑右的棋子看作一堆石子，石子个数为两颗棋子之间的空格数。这样两个人移动一颗棋子都相当于从对应的堆中取出一些石子。

k-nim的解法是这样的：

首先将各堆石子数用二进制表示。

令r_i表示每堆石子二进制表示的第i位上数字之和\bmod (k+1)的值。

如果有任意一个r_i \ne 0，先手必胜；否则先手必败。

k-nim的解法证明：

敲黑板划重点啦！

如果所有的r_i都为0，则一次操作肯定会使得某些数位上的值改变。又因为一堆石子每位上都是0或1，所以变动的绝对值不会超过k。因此操作结束后该位置上的r_i必不能为0。

如果有一些r_i不为0。则肯定有r_i堆石子的数量二进制表示该位上为1。此时我们只要从高到低扫每一个二进制位，选择r_i堆该位上为1的石子，再使每堆石子的个数\mathrm{xor} 2^i，此时这些堆的石子个数会变少，而r_i会变为0。

但是有一个问题：如果这样选出来的石子堆数超过了k怎么办？

此时我们知道：如果一个数的高位从1变成0，则其低位无论怎么变化，这个数还是变小。

于是我们每次只要尽量优先选择有高位变为0的数，再选择该位上为1的数，这样由于每个位置要选的数不到k+1（r_i < k+1）个，所以总共要选的堆数不会超过k堆。

又因为无法操作的状态各个r_i均为0。所以我们得到了解法。

接着的dp可以参见神仙们的题解，在此不予赘述。

Code:

#include<cstdio>
const int o=1e9+7;
int n,k,d,ans;
int frc[10007],inv[10007];
int dp[17][17007];
inline int qpw(int x,int v)
{
    int r=1;
    while(v)
    {
        (v&1)&&(r=1ll*r*x%o),x=1ll*x*x%o,v>>=1;
    }
    return r;
}
inline int C(int N,int M)
{
    return 1ll*frc[N]*inv[M]%o*inv[N-M]%o;
}
int main()
{
    scanf(" %d %d %d",&n,&k,&d);
    frc[0]=1;
    for(int i=1;i<=n;++i)
    {
        frc[i]=1ll*frc[i-1]*i%o;
    }
    inv[n]=qpw(frc[n],o-2);
    for(int i=n;i;--i)
    {
        inv[i-1]=1ll*inv[i]*i%o;
    }
    dp[0][0]=1;
    for(int i=0;i<=13;++i)
    {
        for(int j=0;j<=n-k;++j)
        {
            for(int x=0;k+(x<<i)<=n&&x<<1<=k;x+=d+1)
            {
                dp[i+1][j+(x<<i)]=(dp[i+1][j+(x<<i)]+1ll*dp[i][j]*C(k>>1,x))%o;
            }
        }
    }
    for(int i=0;i<=n-k;++i)
    {
        ans=(ans+1ll*dp[14][i]*C(n-i-(k>>1),k>>1))%o;
    }
    printf("%d\n",(C(n,k)-ans+o)%o);
    return 0;
}