首页 > 代码库 > 【bzoj2281】[Sdoi2011]黑白棋
【bzoj2281】[Sdoi2011]黑白棋
博弈论---Nimk问题。 dp再搞搞。
很容易看出,该游戏的终态是每两个棋子都紧靠着。当一颗棋子移动,另一方与该棋子对应的那一刻可以立即追上,使得仍旧紧靠,最终棋子动弹不得,游戏结束。
还能看出,对于白色棋子(先手),往左走没有意义。因为黑子(后手)可以紧随其上使得两者距离不变。同理黑子只往左走。(黄学长貌似提出了反例?)
所以,问题可以抽象为Nim,与传统Nim只能选1堆不同,你可以选1-d堆。
这个拓展问题叫做Nimk问题。对于这种问题,我们可以证明:当将n堆棋子化为二进制,每一位上如果1的个数mod(k+1)==0 则为必败态。
详细证明,大传送术!http://blog.csdn.net/weixinding/article/details/7321139
最后只需要计算方案数。使用dp,dp[i][j]表示当前在二进制第i位上,总计用了j石头的方案。转移方程为:
dp[i+1][j+a*(k+1)*bin[i]]+=dp[i][j]*C(n,a*(k+1));
注意组合数处理,取%等细节即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mo 1000000007 4 #define N 10005 5 #define LL long long 6 LL c[N][205],dp[20][N],ans; 7 int n,k,d,K,bin[20]; 8 void pre(){ 9 bin[0]=1; for(int i=1;i<=15;i++) bin[i]=bin[i-1]<<1;10 for(int i=0;i<=n;i++) c[i][0]=1;11 for(int i=1;i<=n;i++)12 for(int j=1;j<=min(i,K);j++)13 c[i][j]=(c[i-1][j]+c[i-1][j-1])%mo;14 }15 LL C(int n,int m){16 if(n-m<m) m=n-m;17 return c[n][m];18 }19 LL cal(LL& x,LL y){20 x=(x+y)%mo;21 }22 int main(){23 scanf("%d%d%d",&n,&K,&d); pre(); dp[0][0]=1;24 for(int i=0;i<15;i++)25 for(int j=0;j<=n-K;j++)26 for(int k=0;k*(d+1)<=K/2 && j+k*(d+1)*bin[i]<=n-K;k++)27 cal(dp[i+1][j+k*(d+1)*bin[i]],dp[i][j]*C(K/2,k*(d+1)));28 for(int i=0;i<=n-K;i++)29 cal(ans,dp[15][i]*C(n-i-K/2,K/2));30 LL tot=C(n,K);31 cout<<(tot-ans+mo)%mo;32 return 0;33 }
【bzoj2281】[Sdoi2011]黑白棋
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。