题目

题目大意

在一个1*n的棋盘上，有黑棋和白棋交错分布，每次，一个人可以移动自己的ddd颗旗子。

问先手必胜的方案数。

思考历程

在一开始，我就有点要放弃的念头。

因为这题是一道博弈问题。

我是非常不擅长博弈类问题的。

但是其他的题有想不出来，于是只能硬是想了好久。

最终那了个部分分。

正解

这题正解当然跟博弈有一些关系。

首先，对于这题有一个隐藏的限制。

白棋不能向左移，黑棋不能向右移。

这是为什么？

我们可以感性理解一下（证明什么的我当然不会）：

如果白棋左移，那么在它右边的黑棋可以模仿它的操作，也跟着左移。

同理，如果黑棋右移，那么在它左边的白棋也可以模仿他的动作，也跟着右移。

那么我们就可以发现，这样走是没有意义的。

然后我们就可以转换问题的模型：

可以将对应（相邻）的两个白棋和黑棋中间的距离当作石子。

那么就有K2\frac{K}{2}2K堆石子，然后每次可以在至多ddd堆石子，至少111堆石子中各自拿走一颗石子。

这个问题叫Nimk问题。

这又是个什么东西啊？

对于Nimk问题，我们有一个神奇的结论：将所有堆石子的个数化成二进制，每一位统计一下111的个数，如果个数都是d+1d+1d+1的倍数，那么这就是必败态。

如何证明？

我们可以感性理解一下：怎么又是感性理解……

先手只能拿走111到ddd堆中的石子，那么，后手可以故意的模仿，然后将两人取得的石子的总数固定在d+1d+1d+1。那么如果一直这么下去，后手必定会赢。

为什么要转成二进制呢？

我觉得，其实只要转成了二进制，那么后手就能保证每次能够取得这么多的石子，使得两个人取石子的总数为d+1d+1d+1。具体怎样解释，我觉得我还要好好理解一下，暂且感性感性吧（感性理解真是一个好东西）。

模型转换成了Nimk问题，让我们求先手必胜的方案数。

先手必胜的方案数等于总方案数减去先手必败的方案数。

如何求先手必败的方案数呢？

当然是DP。

设fi,jf_{i,j}fi,j表示在二进制的前iii位中，一共用了jjj颗石子的先手必败的方案数。

仔细想想这个状态没有任何问题，因为我们只需要保证在每一个二进制位上都满足它必败就好了。这样设状态之后转移就方便多了。

我们再枚举一个kkk（小写的kkk，不要混淆），表示一共有k∗(d+1)k*(d+1)k∗(d+1)堆石子下一个二进制位上为111。

转移？

fi+1,j+k∗(d+1)∗2i←fi,j∗CK2k∗(d+1)f_{i+1,j+k*(d+1)*2^i}\leftarrow f_{i,j}*C_{\frac{K}{2}}^{k*(d+1)}fi+1,j+k∗(d+1)∗2i←fi,j∗C2Kk∗(d+1)

注意：为了程序实现方便，在这个方程中，前iii位的最高位实际上是i−1i-1i−1位。这样的DP中，初始化直接是f0,0=1f_{0,0}=1f0,0=1

在一波DP之后，我们就可以统计答案了。

其实我们可以将其视为，在n−j−Kn-j-Kn−j−K个空中插入K/2K/2K/2个东西。

这个东西可以用组合数来搞一搞，那么就是Cn−j−K2K2C_{n-j-\frac{K}{2}}^{\frac{K}{2}}Cn−j−2K2K种方案，用它来乘上fMAXBIT,jf_{MAXBIT,j}fMAXBIT,j就好了。

然后这题就愉快地解决了。

复杂度表示懒得分析。

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#define mo 1000000007

int n,K,d;

int C[10001][101];

int f[17][10001];

int main(){

	scanf("%d%d%d",&n,&K,&d);

	C[0][0]=1;

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

		C[i][0]=1;

		for (int j=1;j<=i && j<=K;++j)

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

	}

	f[0][0]=1;

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

		for (int j=0;j<=n-K;++j)

			if (f[i][j])

				for (int k=0;k*(d+1)<=K>>1 && j+k*(d+1)*(1<<i)<=n-K;++k)

					(f[i+1][j+k*(d+1)*(1<<i)]+=(long long)f[i][j]*C[K>>1][k*(d+1)]%mo)%=mo;

	int ans=0;

	for (int j=0;j<=n-K;++j)

		ans=(ans+(long long)f[15][j]*C[n-j-(K>>1)][K>>1]%mo)%mo;

	printf("%d\n",(C[n][K]-ans+mo)%mo);

	return 0;

}

我认为这个程序实现不用注释。

总结

博弈类问题，可真是一个神奇东西啊！

然而，好多的我都不会严谨证明。

感性理解就好……

我觉得以后要多做一些博弈类问题。

巴特西

JZOJ2368 【SDOI2011】黑白棋

题目

题目大意

思考历程

正解

代码

总结

最新文章

热门文章