「BZOJ2281」[SDOI2011] 黑白棋
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。
「数据规模和约定」
对于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
必败能转移成必败！
所以题目中要增加限制：先手不能左移，后手不能右移
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #define ll long long #define mod 1000000007 #define inf 1000000000 using namespace std; int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } ll tot,ans; int n,K,d,p; ll bin[25]; ll c[10005][205],f[25][10005]; void cal(ll &x,ll y) { x=(x+y)%mod; } void pre() { for(int i=0;i<=n;i++)c[i][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=min(2*K,i);j++) 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]; } void add(ll &x,ll y) { x=(x+y)%mod; } int main() { bin[0]=1;for(int i=1;i<=15;i++)bin[i]=bin[i-1]<<1; n=read();K=read();d=read();K/=2; pre(); f[0][0]=1; for(int i=0;i<15;i++) for(int j=0;j<=n-2*K;j++) 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))); } for(int i=0;i<=n-2*K;i++) add(ans,f[15][i]*C(n-i-K,K)); tot=C(n,K*2); cout<<(tot-ans+mod)%mod; return 0; } |
计数器 9785981
OI 课件=>
OI 课件=>
for(int i=0;i<=n-2*K;i++)
add(ans,f[15][i]*C(n-i-K,K));
为什么f的第二维的范围是n-2K
因为要放2K个棋子，n-2K是剩余的格子数