首页 > 代码库 > 【bzoj2281】 Sdoi2011—黑白棋

【bzoj2281】 Sdoi2011—黑白棋

2024-08-29 06:27:13   220人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=2281 (题目链接)

题意

　　一个1*n的棋盘，棋盘上一个隔一个的放着个黑棋和白棋，最左端是白棋，最右端是黑棋每次可以向左或向右移动<=d颗棋子，移动不能跨越棋子，也不能越出边界，问先手必胜的初始状态有多少。

Solution

　　Knim。

　　右转介绍：http://blog.csdn.net/weixinding/article/details/7321139

　　左转题解：http://blog.csdn.net/lych_cys/article/details/50184249

细节

　　直接预处理10000的组合数会炸空间，所以我们采用公式${C^m_n=C^{n-m}_n}$进行转换。

代码

// bzoj2281#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf 2147483640#define MOD 1000000007#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=10010;LL C[maxn][200],f[20][maxn],bin[20];int n,K,d;LL c(LL n,LL m) {	if (m>n-m) return C[n][n-m];	else return C[n][m];}int main() {	bin[0]=1;for (int i=1;i<=15;i++) bin[i]=bin[i-1]<<1;	scanf("%d%d%d",&n,&K,&d);	for (int i=0;i<=n;i++) C[i][0]=1;	for (int i=1;i<=n;i++)		for (int j=1;j<=min(K,i);j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;   //预处理	f[0][0]=1;	for (int i=0;i<15;i++)		for (int j=0;j<=n-K;j++)			for (int k=0;k*(d+1)<=K/2 && j+k*(d+1)*bin[i]<=n-K;k++)				f[i+1][j+k*(d+1)*bin[i]]=(f[i+1][j+k*(d+1)*bin[i]]+f[i][j]*c(K/2,k*(d+1)))%MOD;   //dp求解f[i][j]，表示二进制前i位放j个石子	LL ans=0;	for (int i=0;i<=n-K;i++)   //枚举左右端点之间的长度(也就是放几个石子)		ans=(ans+f[15][i]*c(n-i-K/2,K/2))%MOD;   //石子的总排列数*每一堆石子放置的位置数	printf("%lld",(c(n,K)-ans+MOD)%MOD);	return 0;}

　　

　　

【bzoj2281】 Sdoi2011—黑白棋


联系
我们