首页 > 其他 > 详细

【BZOJ4550】小奇的博弈 博弈论

时间:2017-10-22 10:25:58      阅读:228      评论:0      收藏:0      [点我收藏+]

【BZOJ4550】小奇的博弈

Description

这个游戏是在一个1*n的棋盘上进行的,棋盘上有k个棋子,一半是黑色,一半是白色。最左边是白色棋子,最右边是黑色棋子,相邻的棋子颜色不同。
 技术分享
小奇可以移动白色棋子,提比可以移动黑色的棋子,它们每次操作可以移动1到d个棋子。每当移动某一个棋子时,这个棋子不能跨越两边的棋子,当然也不可以出界。当谁不可以操作时,谁就失败了。小奇和提比轮流操作,现在小奇先移动,有多少种初始棋子的布局会使它有必胜策略?

Input

共一行,三个数,n,k,d。对于100%的数据,有1<=d<=k<=n<=10000, k为偶数,k<=100。

Output

输出小奇胜利的方案总数。答案对1000000007取模。

Sample Input

10 4 2

Sample Output

182

题解:首先思考K=2的情况,显然白棋可以直接往右移到黑棋左边,然后黑棋只能被动往右移,然后白棋又可以不断向右将黑棋逼死,所以如果一开始中间的间隔不为0则先手必胜,反之先手必输。

K>2的情况同理,白棋是一定不会主动往左移的,黑棋也一定不会主动往右移,所以黑白之间的间隔一定会不断变小,这变成了什么?我们将间隔视为石子,那么这就相当于k堆石子,没人可以从1-d堆中取出若干个石子。这是一个经典的Nimk问题。结论:我们将石子数二进制拆分,对所有石子的每一位都进行不进位的加法,先手必输当且仅当每一位的和%(d+1)都=0,否则先手必胜。

显然是先手必输的情况比较好处理。然后DP。我们用f[i][j]表示统计到二进制的前i位,已经用了j枚石子,先手必输的情况数。转移时用组合数搞一搞即可。总方案数显然是$ C_n^k $。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll P=1000000007;
int n,k,d;
ll ans;
ll f[20][10010],c[10010][110];
int main()
{
	scanf("%d%d%d",&n,&k,&d);
	int i,j,l;
	for(i=0;i<=n;i++)
	{
		c[i][0]=1;
		for(j=1;j<=i&&j<=k;j++)	c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
	}
	f[0][0]=1;
	for(i=0;i<16;i++)	for(j=0;j<=n-k;j++)	for(l=0;(1ll<<i)*(d+1)*l<=j&&(d+1)*l<=k/2;l++)
	{
		f[i+1][j]=(f[i+1][j]+f[i][j-(1ll<<i)*l*(d+1)]*c[k/2][(d+1)*l])%P;
	}
	for(i=0;i<=n-k;i++)	ans=(ans+f[16][i]*c[n-i-k/2][k/2])%P;
	printf("%lld",(c[n][k]-ans+P)%P);
	return 0;
}

 

【BZOJ4550】小奇的博弈 博弈论

原文:http://www.cnblogs.com/CQzhangyu/p/7707746.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!