bzoj 4550: 小奇的博弈【博弈论+dp】

首先看出终止状态是全都堆在左边或者右边，然后发现黑的向左白的向右是最优策略（如果不能这样了也就该输了）

然后就不会了

参考 http://www.cnblogs.com/CQzhangyu/p/7707746.html

发现黑白之间的距离一定是不断缩小的，就相当于k堆石子，每次从1~d堆里拿走一些，根据nimk，二进制位下每一位的和都是d+1的倍数则先手必输（可以看成高配的巴什博奕）

然后设f[i][j]为前i位用了j石子，用组合数转移：f[i+1][j]=(f[i+1][j]+f[i][j-(1ll<<i)k(d+1)]c[m/2][(d+1)k])%mod

#include<iostream>

#include<cstdio>

using namespace std;

const long long N=10005,mod=1e9+7;

int n,m,d;

long long f[20][N],c[N][105],ans;

int main()

{

    scanf("%d%d%d",&n,&m,&d);

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

    {

        c[i][0]=1;

        for(int j=1;j<=i&&j<=m;j++)

			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;

    }

    f[0][0]=1;

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

		for(int j=0;j<=n-m;j++)

			for(int k=0;(1ll<<i)*(d+1)*k<=j&&(d+1)*k<=m/2;k++)

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

    for(int i=0;i<=n-m;i++)

		ans=(ans+f[16][i]*c[n-i-m/2][m/2])%mod;

    printf("%lld",(c[n][m]-ans+mod)%mod);

    return 0;

}

巴特西

bzoj 4550: 小奇的博弈【博弈论+dp】

最新文章

热门文章