bzoj 2281 [Sdoi2011]黑白棋(博弈+组合计数)

黑白棋(game

【问题描述】

小A和小B又想到了一个新的游戏。

这个游戏是在一个1*n的棋盘上进行的,棋盘上有k个棋子,一半是黑色,一半是白色。

最左边是白色棋子,最右边是黑色棋子,相邻的棋子颜色不同。

小A可以移动白色棋子,小B可以移动黑色的棋子,他们每次操作可以移动1到d个棋子。

每当移动某一个棋子时,这个棋子不能跨越两边的棋子,当然也不可以出界。当谁不可以操作时,谁就失败了。

小A和小B轮流操作,现在小A先移动,有多少种初始棋子的布局会使他胜利呢?

【输入格式】

共一行,三个数,n,k,d。

【输出格式】

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

【样例输入】

10 4 2

【样例输出】

182

【数据规模和约定】

对于30%的数据,有 k=2。

对于100%的数据,有1<=d<=k<=n<=10000, k为偶数,k<=100。

【思路】

博弈+组合计数

将相邻黑白点看作是一堆石子,则问题转化为Nimk游戏,即有n堆石子每次可以在1~d堆中拿出任意不为0个数的石子,什么时候局面必胜。

结论:当且仅当nim和中1的个数为d+1的倍数,有局面必败。每次最多只能使d个为0,先手不能转移到必败态 ,则后手可以通过操作获胜。

补集转化,求先手必败的局面数。

设f[i][j]表示nim和前i位中有j个的先手必败的方案数,枚举 d+1 的倍数转移:

f[i][j+k*(d+1)*(1<<i)]+=f[i][j]*C(K/2,k*(d+1))

则最后答案为C(n,K)-sigma{ f[15][i]*C(n-i-K/2,K/2) }

【代码】

 #include<cstdio>
#include<iostream>
using namespace std; typedef long long LL;
const int N = *1e4+;
const int M = *1e2+;
const int MOD = 1e9+; LL c[N][M],f[M][N]; void get_c() {
for(int i=;i<N;i++) c[i][]=;
for(int i=;i<N;i++) {
for(int j=;j<=min(i,M-);j++)
c[i][j]=(c[i-][j-]+c[i-][j])%MOD;
}
}
LL C(int n,int k) {
if(k>n-k) k=n-k; return c[n][k];
} int n,K,D; int main() {
get_c();
scanf("%d%d%d",&n,&K,&D);
K>>=;
f[][]=;
for(int i=;i<;i++)
for(int j=;j<=n-*K;j++)
for(int k=;k*(D+)<=K && j+k*(D+)*(<<i)<=n-*K;k++)
f[i+][j+k*(D+)*(<<i)]=(f[i+][j+k*(D+)*(<<i)]+f[i][j]*C(K,k*(D+))%MOD)%MOD;
LL ans=;
for(int i=;i<=n-*K;i++)
ans=(ans+f[][i]*C(n-i-K,K)%MOD)%MOD;
printf("%lld",(C(n,*K)-ans+MOD)%MOD);
return ;
}
上一篇:PHP求解一个值是否为质数


下一篇:【[SDOI2014]数表】