【bzoj2281】[Sdoi2011]黑白棋

2014年12月22日2,7152

Description

黑白棋(game
【问题描述】
小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
【数据规模和约定】
对于100%的数据,有1<=d<=k<=n<=10000, k为偶数,k<=100。

题解

题解:

K=2的情况,显然是A胜利

A第一步将其棋子紧靠B,则接下来B只能右移,若B移动,A下一步也能靠着它,除非A一开始就无法移动

这样答案显然是C(n,2) – (n-1)

其实从K=2的情况我们可以看出,B的右移是没有意义的

因为A可以模仿B,同理A的左移是没有意义的,那么就能转换为一个nim游戏

第i个白子,匹配第i个黑子,把他们中间的格子看成石子堆,变成一个每次可以取d堆的nim游戏

结论:必败态是把每堆石子转换为二进制后,其中每一位上为1的石子堆数都能被(d+1)整除

(详解=> http://blog.csdn.net/weixinding/article/details/7321139

用f[i][j]表示考虑二进制前i位,放置了j个石头的方案数

枚举每一位

有q*(d+1)堆是1,即放了q*(d+1)*(1<<i)个,用排列组合计算这q*(d+1)堆是K堆中的那些

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

然后用总方案-必败局面数,总方案显然是C(N,K)

2015-11-22

其实转成nim游戏是有误的

这个游戏往左移,是可以加石子的,虽然后手可以模仿,但是要消耗下次可操作的堆数,并非没有意义

反例:d = 2

[ ]OX[ ]O[ ]XO[ ]XO[ ]X          0 1 1 1

前两个白棋往两边移动

O[ ]X[ ][ ]OXO[ ]XO[ ]X          1 0 1 1

必败能转移成必败!

所以题目中要增加限制:先手不能左移,后手不能右移

 

  • 2015年11月23日 下午3:21 回复

    for(int i=0;i<=n-2*K;i++)
    add(ans,f[15][i]*C(n-i-K,K));
    为什么f的第二维的范围是n-2K

    #1  
    • hzwer2015年11月23日 下午10:35 回复
      admin

      因为要放2K个棋子,n-2K是剩余的格子数

      #11