BZOJ4550 小奇的博弈 【Nimk游戏 + dp + 组合数】

题目

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

是黑色棋子,相邻的棋子颜色不同。

BZOJ4550 小奇的博弈  【Nimk游戏 + dp + 组合数】

小奇可以移动白色棋子,提比可以移动黑色的棋子,它们每次操作可以移动1到d个棋子。每当移动某一个棋子时,

这个棋子不能跨越两边的棋子,当然也不可以出界。当谁不可以操作时,谁就失败了。小奇和提比轮流操作,现在

小奇先移动,有多少种初始棋子的布局会使它有必胜策略?

输入格式

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

输出格式

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

输入样例

10 4 2

输出样例

182

题解

面对各种数学轰炸。。跪了。

前置知识:

Nimk游戏

Nim游戏基础上,每次可以取之多d堆

先手必败条件:每堆石子转成二进制,各个位的和都为(d + 1)的倍数

例如可以取2次,石子数:111、101、110、011【二进制】

每一位都有2+1=3个1,所以先手必败

本题

黑白棋子相间分布,白棋右移,黑棋左移,每对棋子的间隔长就相当于石子数,而每次可以操作d次,就相当于Nimk游戏

求方案数

一共有K/2堆石子,总数不超过N - K个

首先,总的方案数为C(N,K),我们尝试求出必败的方案数,作差

令f[i][j]表示每堆石子的二进制表示中最高位为i位【从0开始算】,总共有j和石子的方案数

那么有

f[i+1][j+x∗(d+1)∗2i]+=f[i][j]∗C(K/2,x∗(D+1))

原理:最高第i+1位的方案由最高第i位转移而来,每次同时加上(D+1)个1,可枚举x,表示加上x个(D+1)来进行转移,而每次加入x∗(D+1)组石子,又有C(K/2,x∗(D+1))种方法

【模型的转化,dp的应用,组合数的使用】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)
using namespace std;
const int maxn = 10005,maxm = 105,INF = 1000000000,P = 1000000007;
LL C[maxn][maxm],f[20][maxn];
int main(){
LL N,K,D;
cin>>N>>K>>D;
for (int i = 0; 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]) % P;
}
f[0][0] = 1;
for (LL i = 0; i <= 16; i++)
for (LL j = 0; j <= N - K; j++)
for (LL x = 0; x * (D + 1) <= K / 2 && x * (D + 1) * (1ll << i) + j <= N - K; x++)
f[i + 1][j + x * (D + 1) * (1ll << i)] =
(f[i + 1][j + x * (D + 1) * (1ll << i)] + f[i][j] * C[K/2][x * (D + 1)]) % P;
LL ans = C[N][K];
for (int i = 0; i <= N - K; i++)
ans = (ans - f[16][i] * C[N - K - i + K / 2][K / 2] % P) % P;
cout<<(ans + P) % P<<endl;
return 0;
}
上一篇:Servlet 学习总结


下一篇:Fiddler无所不能——之测试开发攻城狮必备利器