题解 P2490【[SDOI2011]黑白棋】

· · 题解

\text{Link}

## 题意 在一个 $1\times n$ 的棋盘上有 $k$ 个棋子，其中有 $\frac k 2$ 个黑棋和 $\frac k 2$ 个白旗。黑棋只能向左，白棋只能向右。每次可以动自己的 $1$ 至 $d$ 颗棋子，每颗棋子可以移动任意格，但是不能跨过任意一方的棋子。 问有多少种布局方案使得白方必胜，要求棋局满足： - 最左边的棋子是白色； - 最右边的棋子是黑色； - 相邻棋子颜色相异。 其中 $1\le k\le 100,1\le d\le k\le n\le 10^4,2|k

思路

搞了好久终于搞懂了...

前置知识：k-\text{Nim} 游戏

描述

有 n 堆棋子，其中第 i 堆有 a_i 颗，每次可以取走 1 至 k 堆棋子中任意颗棋子，不能操作者输。

解法

记数 x 二进制下的第 i 位表示为 (x)_i。

先写出结论：若 \displaystyle\forall s,\left(\sum_{i=1}^n(a_i)_s\right)\bmod(k+1)=0，则先手必败，否则先手必胜。

证明

有向无环图博弈满足一下几点：

所有堆都为 0 颗棋子，显然满足 \text{P} 态。

对于一次操作，必定会取走一些棋子，使得某一位上的数值发生改变，改变的范围只有 1 至 k，不存在一种方案使得操作前后 \displaystyle\forall s,\left(\sum_{i=1}^n(a_i)_s\right)\bmod(k+1) 都是 0。

记 b_s=\displaystyle\left(\sum_{i=1}^n(a_i)_s\right)\bmod(k+1)，对于所有的 b_s\ne0，我们找到 b_s 堆棋子，从中取走 2^s 颗棋子即可转换至 \text{N} 态。

证毕。

回到本题，我们发现棋子不能跨越另外一颗棋子，则最后 \frac k 2 对相邻的黑白棋子必定会被放置在相邻两个格子中，我们可以将相邻的 2 颗棋子之间的距离看做一堆棋子的颗数，问题转化为了 d-\text{Nim} 游戏先手必胜局面数。

考虑一个 \text{dp}，正着不好想，于是反着做，设 dp_{i,j} 表示 0 至 i-1 位中 b_i 都为 0 的方案数，用 \displaystyle\binom{n}{k} 减去即得答案。

考虑在新的一位中选出 x(d+1) 堆为 1 的，方案数即为 \displaystyle\binom{\frac k 2}{x(d+1)}，可有转移

dp_{i+1,j+2^ix(d+1)}\gets dp_{i+1,j+2^ix(d+1)}+\binom{\frac k 2}{x(d+1)}dp_{i,j}

方案即

\sum_{i=1}^{n-k}dp_{mx+1,i}\binom{n-i-\frac k 2}{\frac k 2}

其中 mx 为最高的二进制位

注意要记得转换回原方案。

时间复杂度 O(nk\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff

}
const int mod=1e9+7,N=1e4+10;
int n,k,d,dp[14][N];
int C[N][205];
inline void init(){
    C[0][0]=1;
    for(int i=1;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<=min(i,k);j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
}
int main(){
    n=read(),k=read(),d=read();
    init();
    dp[0][0]=1;
    for(int i=0,p=1;i<=12;i++,p<<=1)
        for(int j=0;j<=n-k;j++)
            for(int x=0;j+p*x*(d+1)<=n-k&&x*(d+1)<=k/2;x++)
                dp[i+1][j+p*x*(d+1)]=(dp[i+1][j+p*x*(d+1)]+1ll*dp[i][j]*C[k/2][x*(d+1)])%mod;
    int ans=0;
    for(int i=0;i<=n-k;i++)
        ans=(ans+1ll*dp[13][i]*C[n-i-k/2][k/2])%mod;
    printf("%d",(C[n][k]+mod-ans)%mod);
    flush();
    return 0;
}

再见 qwq~