2281: [Sdoi2011] 黑白棋
- Time Limit: 3 Sec Memory Limit: 512 MB
- Submit: 626 Solved: 390
- [Submit][Status][Discuss]
- Description
小 A 和小 B 又想到了一个新的游戏
这个游戏是在一个 1*n 的棋盘上进行的, 棋盘上有 k 个棋子, 一半是黑色, 一半是白色
最左边是白色棋子, 最右边是黑色棋子, 相邻的棋子颜色不同
小 A 可以移动白色棋子, 小 B 可以移动黑色的棋子, 他们每次操作可以移动 1 到 d 个棋子
每当移动某一个棋子时, 这个棋子不能跨越两边的棋子, 当然也不可以出界当谁不可以操作时, 谁就失败了
小 A 和小 B 轮流操作, 现在小 A 先移动, 有多少种初始棋子的布局会使他胜利呢?
Input
共一行, 三个数, n,k,d
Output
输出小 A 胜利的方案总数答案对 1000000007 取模
- Sample Input
- 10 4 2
- Sample Output
- 182
- HINT
1<=d<=k<=n<=10000, k 为偶数, k<=100
- Source
- stage 2 day1
很有意思的一道博弈题, 可惜 HZWER 学长给出了反例
对于一道博弈论的题目, 一般有这几种技巧:
1. 手玩游戏并努力找到其中的规律, 或者写一个记忆化搜索模拟回合制博弈过程求得最优解并打表找规律
2. 寻找游戏的末状态, 找到玩家尽快达到状态的方法
3. 多考虑模仿的技巧, 即对手做什么我就相应的做什么 (或做相反操作)
4. 根据 Nim 博弈, SG 函数等猜结论
那么这一题通过手玩可以发现, 最终状态必定是所有棋子全部扎堆在棋盘左端或右端, 棋子之间没有间隙不过仔细观察可以发现, 可能在游戏状态中会出现所有棋子扎堆但不在棋盘一端的情况, 其实那个时候就已经决定了最终的胜负因为只要一方朝自己来的方向走了, 则另一方必定能也往那边走一步, 最终会步步紧逼直到走到棋盘一端
根据这一点, 感性理解一下, 这个游戏就是一个把对方棋子怼过去的过程, 谁怼赢了就是胜者所以从一开始双方都一定拼尽全力往对面怼, 所以有一个结论: 先手不可能往左走, 后手不可能往右走
这样这个问题就变成了一个取石子游戏, 每对相邻的白子和黑子之间的格子数是石子数 (显然共有 K/2 堆石子), 每人每次选不超过 k 堆取一个石子
这个问题叫 K-Nim, 结论是: 将所有石子数转成二进制, 如果对于每一位二进制, 这一位上为 1 的石子堆数都能被 k+1 整除则为必败态, 否则为必胜态
证明主要思路是: 1. 最终态二进制每一位都为 0 必为必败态 2. 只要有某位的 1 的个数不被 k+1 整除, 则必然有一种走法使每一位都被整除 3. 如果每一位都被 k+1 整除, 则无论怎么走都不可能使得每一位都仍然能被整除
这三点分别保证了: 最终态是必败态必胜态必定能走到必败态必败态只能走到必胜态
详细证明: http://blog.csdn.net/weixinding/article/details/7321139
这样, 我们分别用了寻找最终态和模仿的技巧将问题转化为了 K-Nim 问题回到这一题, 最终答案 = 总方案数 - 必败态的方案数
设 $f_{i,j}$ 表示前 $i$ 个二进制位共放了 $j$ 个石子的方案数, 则 $$ans=C_n^K-\sum_{i=0}^{n-K} f_{s,i}*C_{n-i-K/2}^{K/2}$$s 为最高位的 1, 这里取 15 就够了
考虑 $f$ 的转移方程即可:$$f_{i+1,j+k*(d+1)*(1<<i)}\ \ +=\ \ f_{i,j}*C_{K/2}^{k*(d+1)}$$
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #define rep(i,l,r) for (int i=l; i<=r; i++)
- typedef long long ll;
- using namespace std;
- const ll N=10010,mod=1000000007;
- ll tot,ans,bin[25],c[N][205],f[25][N];
- int n,K,d,p;
- void add(ll &x,ll y){ x=(x+y)%mod; }
- void pre(){
- rep(i,0,n) c[i][0]=1;
- rep(i,1,n) rep(j,1,min(2*K,i)) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
- }
- int C(int n,int m){ if (m>n-m) m=n-m; return c[n][m]; }
- int main(){
- freopen("bzoj2281.in","r",stdin);
- freopen("bzoj2281.out","w",stdout);
- bin[0]=1; rep(i,1,15) bin[i]=bin[i-1]<<1;
- scanf("%d%d%d",&n,&K,&d); K>>=1;
- pre(); f[0][0]=1;
- rep(i,0,14) rep(j,0,n-2*K)
- for (int k=0; k*(d+1)<=K && j+k*(d+1)*bin[i]<=n-2*K; k++)
- add(f[i+1][j+k*(d+1)*bin[i]],f[i][j]*C(K,k*(d+1)));
- rep(i,0,n-2*K) add(ans,f[15][i]*C(n-i-K,K));
- tot=C(n,K*2); printf("%lld\n",(tot-ans+mod)%mod);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2529204.html