【BZOJ2281】【博弈论+DP】 [Sdoi2011]黑白棋

2022-10-28 15:41:46

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有点难想...看代码就看得懂了

 /*

 唐代白居易

 《问刘十九》

 绿蚁新醅酒，红泥小火炉。

 晚来天欲雪，能饮一杯无。*/

 #include <set>

 #include <map>

 #include <cmath>

 #include <cstdio>

 #include <vector>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 #define LOCAL

 const int MAXL = ;

 const long long MOD = ;

 const int MAXK =  + ;

 const int MAXN =  + ;

 using namespace std;

 typedef long long ll;

 ll f[][MAXN * ];

 ll c[MAXK][], n, K, d; 

 ll C(ll a, ll b){

    if (a == b) return 1ll;

    //if (b > a - b) b = a - b;

    return c[a][b] % MOD;

 }

 void prepare(){//预处理组合数

      memset(c, , sizeof(c));

      c[][] = ;

      for (ll i = ; i <= 10005ll; i++){

          c[i][] = 1ll;

          //if (i <= 210) c[i][i] = 1;

          for (ll j = ; j < min(i, 250ll); j++)

          c[i][j] = (C(i - , j) + C(i - , j - )) % MOD;

      }

      //for (ll i = 1; i <= 50; i++)

      //for (ll j = 0; j <= i; j++) printf("%d %d:%d\n", i, j, C[i][j]);

      //printf("%d\n", C[10][2]);

 }

 void dp(){

      K /= ;

      memset(f, , sizeof(f));

      f[][] = ;//第0位

      for (ll i = ; i <= ; i++){

          for (ll j = ; j <= n -  * K; j++)//注意这一层不需要枚举到n了，因为只有这么多的空位

          for (ll k = ; (k * (d + ) <= K) && (k * (d + ) * (1ll<<(i - )) <= j); k++){

              f[i][j] = (f[i][j] + (f[i - ][j - k * (d + ) * (1ll<<(i - ))] * C(K, k * (d + ))) % MOD) % MOD;

          }

      }

      ll Ans = ;

      for (ll i = ; i <= n -  * K; i++) Ans = (Ans + (f[][i] * C(n - i - K *  + K, K)) % MOD) % MOD;

      printf("%lld\n", (C(n,  * K) - Ans + MOD) % MOD);

 }

 int main(){

     prepare();

     scanf("%lld%lld%lld", &n, &K, &d);

     dp();

     //n的距离,k个石头，1~d次移动

     return ;

 }

码农公寓