BZOJ4550: 小奇的博弈（NIMK博弈& 组合数& DP）

2022-08-31 14:03:13

4550: 小奇的博弈

Time Limit: 2 Sec Memory Limit: 256 MB
Submit: 159 Solved: 104
[Submit][Status][Discuss]

Description

这个游戏是在一个1*n的棋盘上进行的，棋盘上有k个棋子，一半是黑色，一半是白色。最左边是白色棋子，最右边

是黑色棋子，相邻的棋子颜色不同。

小奇可以移动白色棋子，提比可以移动黑色的棋子，它们每次操作可以移动1到d个棋子。每当移动某一个棋子时，

这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。小奇和提比轮流操作，现在

小奇先移动，有多少种初始棋子的布局会使它有必胜策略？

Input

共一行，三个数，n，k，d。对于100%的数据，有1<=d<=k<=n<=10000, k为偶数，k<=100。

Output

输出小奇胜利的方案总数。答案对1000000007取模。

Sample Input

10 4 2

Sample Output

182

HINT

Source

By Hzwer

思路：显然为了压制对方，先手会操控白棋向右移，后手会操控黑棋向左移。那么(1,2) (3,4) (5,6)...(k-1,k)这些棋子就像取石子一样，有K/2堆石子，且每一对的石子数的黑白棋距离。由于题目是每次可以操作最多d个棋子，每次棋子每次走多次（不超过范围即可），那么就是一个nimk博弈。（我也是才遇到这么个东西）。

这个博弈先手必败态为：分别累加每堆石子的二进制每一位，分别是（d+1）的倍数。

（位了直观，下面直接把棋子间的空位当作石子。

然后，剩下的就交给背包求方案数。用F[i][j]表示二进制前i位用掉了j个石子。

因为二进制中第i位要么是0要么是1，在k/2堆石子中，假设有l个有这一位，然后背包乘组合数c[k/2][(d+1)*l]，得到如下方程：

f[i+][j]=(f[i+][j]+f[i][j-(1ll<<i)*l*(d+)]*c[k/][(d+)*l])%P;

最后，我们枚举石子数，用F乘上对应的排列数C。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll P=1e9+;

int N,K,D;

ll ans,f[][],C[][];

int main()

{

    scanf("%d%d%d",&N,&K,&D);

    for(int i=;i<=N;i++){

        C[i][]=;

        for(int j=;j<=i&&j<=K;j++)   C[i][j]=(C[i-][j-]+C[i-][j])%P;

    }

    f[][]=;

    for(int i=;i<;i++)

      for(int j=;j<=N-K;j++)

        for(int l=;(1ll<<i)*(D+)*l<=j&&(D+)*l<=K/;l++)

        f[i+][j]=(f[i+][j]+f[i][j-(1ll<<i)*l*(D+)]*C[K/][(D+)*l])%P;

    for(int i=;i<=N-K;i++)  ans=(ans+f[][i]*C[N-i-K/][K/])%P;

    printf("%lld",(C[N][K]-ans+P)%P);

    return ;

}

码农公寓