BZOJ 2281: [Sdoi2011]黑白棋(dp+博弈论)

解题思路

　　首先发现可以把相邻的黑白棋子之间的距离看成一堆棋子，那么这个就可以抽象成\(Nim\)游戏每次可以取\(d\)堆这个游戏，而这个游戏的\(SG\)值为\(x\%(d+1)\)，那么题目其实就是求所有石子的异或和\(\%d=0\)的方案数。可以设\(f[i][j]\)表示二进制下前\(i\)位\(\%d\)都为\(0\)，一共用了\(j\)个石子，转移时可以枚举当前这一位\(/d\)为多少，然后再乘组合数更新答案，最后用总数\(-\)不合法方案即可。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=10005;

const int MOD=1e9+7;

int n,k,d,f[20][N],C[10005][205],ans,tot;

inline int min(int x,int y) {return x<y?x:y;}

inline void prework(){

	C[0][0]=1; int Min;

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

		C[i][0]=1; Min=min(i,k);

		for(int j=1;j<=Min;j++)

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

	}

}

inline int calc(int x,int y){

	if(y>x-y) y=x-y;

	return C[x][y];

}

int main(){

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

	prework(); f[0][0]=1;

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

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

			for(int l=0;l*(d+1)<=k/2 && j+l*(d+1)*(1<<i)<=n-k;l++)

				(f[i+1][j+l*(d+1)*(1<<i)]+=1ll*f[i][j]*calc(k/2,l*(d+1))%MOD)%=MOD;

	for(int i=0;i<=n-k;i++) (ans+=1ll*f[15][i]*calc(n-i-k/2,k/2)%MOD)%=MOD;

	tot=calc(n,k); ans=(tot-ans+MOD)%MOD; printf("%d\n",ans);

	return 0;

}

巴特西

BZOJ 2281: [Sdoi2011]黑白棋(dp+博弈论)

解题思路

代码

最新文章

热门文章