【BZOJ2281】【博弈论+DP】 [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。

HINT

Source

stage 2 day1

【分析】

很经典的题目，很不错。

我们将相邻的棋子看成一对，显然，在最后的情况下，每对棋子都是紧贴在一起的。

对于每对棋子，白棋在左边，黑棋在右边，那么白棋就只能往右边走，黑棋也只能往左边走，否则若白棋往左边，黑棋也可以往左边，情况不会有改变。

那么若将每对棋子之间的距离看成一堆石子的数量，就变成经典的nim游戏。

然后用nimk的理论做就行了。

DP有点难想...看代码就看得懂了

 1 /*
 2 唐代白居易
 3 《问刘十九》
 4 绿蚁新醅酒，红泥小火炉。
 5 晚来天欲雪，能饮一杯无。*/
 6 
 7 #include <set>
 8 #include <map>
 9 #include <cmath>
10 #include <cstdio>
11 #include <vector>
12 #include <cstring>
13 #include <cstdlib>
14 #include <iostream>
15 #include <algorithm>
16 #define LOCAL
17 const int MAXL = 20;
18 const long long MOD = 1000000007;
19 const int MAXK = 10000 + 10;
20 const int MAXN = 10000 + 10;
21 using namespace std;
22 typedef long long ll;
23 ll f[100][MAXN * 2];
24 ll c[MAXK][1000], n, K, d; 
25 
26 ll C(ll a, ll b){
27    if (a == b) return 1ll;
28    //if (b > a - b) b = a - b;
29    return c[a][b] % MOD;
30 }
31 void prepare(){//预处理组合数
32      memset(c, 0, sizeof(c));
33      c[0][0] = 1; 
34      for (ll i = 1; i <= 10005ll; i++){
35          c[i][0] = 1ll;
36          //if (i <= 210) c[i][i] = 1;
37          for (ll j = 1; j < min(i, 250ll); j++)
38          c[i][j] = (C(i - 1, j) + C(i - 1, j - 1)) % MOD;
39      }
40      //for (ll i = 1; i <= 50; i++)
41      //for (ll j = 0; j <= i; j++) printf("%d %d:%d
", i, j, C[i][j]);
42      //printf("%d
", C[10][2]);
43 }
44 void dp(){
45      K /= 2;
46      memset(f, 0, sizeof(f));
47      f[0][0] = 1;//第0位 
48      for (ll i = 1; i <= 15; i++){
49          for (ll j = 0; j <= n - 2 * K; j++)//注意这一层不需要枚举到n了，因为只有这么多的空位 
50          for (ll k = 0; (k * (d + 1) <= K) && (k * (d + 1) * (1ll<<(i - 1)) <= j); k++){
51              f[i][j] = (f[i][j] + (f[i - 1][j - k * (d + 1) * (1ll<<(i - 1))] * C(K, k * (d + 1))) % MOD) % MOD;
52              
53          }
54      }
55      ll Ans = 0;
56      for (ll i = 0; i <= n - 2 * K; i++) Ans = (Ans + (f[15][i] * C(n - i - K * 2 + K, K)) % MOD) % MOD;
57      printf("%lld
", (C(n, 2 * K) - Ans + MOD) % MOD);
58 }
59 
60 int main(){
61     
62     prepare();
63     scanf("%lld%lld%lld", &n, &K, &d);
64     dp();
65     //n的距离,k个石头，1~d次移动 
66     return 0;
67 }

View Code