[关闭]
@ysner 2018-08-03T07:21:12.000000Z 字数 1570 阅读 2069

[SDOI2011]黑白棋

DP 博弈论


题面

这个游戏是在一个的棋盘上进行的,棋盘上有个棋子,一半是黑色,一半是白色。
最左边是白色棋子,最右边是黑色棋子,相邻的棋子颜色不同
可以移动白色棋子,可以移动黑色的棋子,他们每次操作可以移动个棋子。
每当移动某一个棋子时,这个棋子不能跨越两边的棋子,当然也不可以出界。当谁不可以操作时,谁就失败了。
先手,有多少种初始棋子的布局会使他胜利呢?

解析

题面显然有误,如果允许白往左、黑往右,这游戏玩不完。

毕竟我是在博弈论的题单里发现这道题的
很快就反应过来:把各对相邻黑白棋子之间的距离视作一堆石子即可
于是问题转化为一个 一次限制取个 的游戏。
这种类型问题有个结论:
即题目本质是要 各堆石子个数异或和

怎么统计方案?(注意下状态)
显然异或和模这种情况很方便设计状态。于是先统计后者胜利的情况,再用方案总数减去它得到答案。
表示确定异或和二进制第位均为、现有个石子的方案数。
枚举该位需要个石子。
此时,该位对石子数的贡献取决于各堆石子该位是否为
于是要从个堆选出个,把这些堆石子数 该位置为,贡献种方案
同时,我们要选出各堆的位置,相当于在个位置被终点占)个位置中选出个起点,贡献种方案。
综上得方程式:


  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int mod=1e9+7;
  14. int n,k,d,C[10005][205],dp[18][100005];
  15. ll ans;
  16. il ll gi()
  17. {
  18. re ll x=0,t=1;
  19. re char ch=getchar();
  20. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  21. if(ch=='-') t=-1,ch=getchar();
  22. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  23. return x*t;
  24. }
  25. int main()
  26. {
  27. n=gi();k=gi();d=gi();
  28. C[0][0]=1;
  29. fp(i,1,n)
  30. {
  31. C[i][0]=1;
  32. fp(j,1,200) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
  33. }
  34. dp[0][0]=1;
  35. fp(i,0,16)
  36. fp(j,0,n-k)
  37. for(re int x=0;(1ll<<i)*x*(d+1)<=n-k&&x*(d+1)<=k/2;++x)
  38. (dp[i+1][j+(1ll<<i)*x*(d+1)]+=1ll*dp[i][j]*C[k/2][x*(d+1)]%mod)%=mod;
  39. fp(i,0,n-k) ans=(ans+1ll*dp[17][i]*C[n-i-k/2][k/2]%mod+mod)%mod;
  40. printf("%lld\n",(C[n][k]-ans+mod)%mod);
  41. return 0;
  42. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注