【BZOJ2281】【Sdoi2011】黑白棋

Description

小A和小B又想到了一个新的游戏。

这个游戏是在一个\(1\)*\(n\)的棋盘上进行的，棋盘上有\(k\)个棋子，一半是黑色，一半是白色。

最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。

小A可以移动白色棋子，小B可以移动黑色的棋子，他们每次操作可以移动\(1\)到\(d\)个棋子。

每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。

小A和小B轮流操作，现在小A先移动，有多少种初始棋子的布局会使他胜利呢？

先手不能左移，后手不能右移

Input

共一行，三个数，\(n,k,d\)。

Output

输出小A胜利的方案总数。答案对\(1000000007\)取模。

HINT

\(1<=d<=k<=n<=10000\), \(k\)为偶数，\(k<=100\)。

越发的觉得自己是个低能儿了...

注意原题是没有“先手不能左移，后手不能右移”这个条件的，不过被黄学长hack了，于是部分oj加上了

然后发现先手有个必败局面是所有对应的黑白棋相邻。

然后我们发现移动会造成对应的相邻黑白棋的距离缩小

于是可以发现是个\(k-nim\)游戏

关于这个东西有个结论，若子游戏\(SG\)每一位的\(1\)的总个数都可以被\((d+1)\)整除，当前局面是必败局面。

然后问题转换成，在序列上选取若干个不相交区间，保证区间的长度满足一些要求。

因为要求是按位的，所以做数位\(dp\)

\(dp_{i,j}\)代表前\(i\)位满足条件且选取的区间总长度是\(j\)的方案数。

\(dp_{0,0}=1\)是初始状态，表示区间长度为\(0\)

然后推出去会比较好些，我们先不讨论每个区间的位置，只讨论区间的长度的方案。

于是有\(dp_{i,j+len*x*(d+1)}+=dp_{i,j}*\binom{k/2}{x(d+1)}\)

\(len\)当前位数对应的长度，\(x\)枚举是几倍，然后组合数选那几个区间

最后确定位置每个状态乘上\(\binom{n-j-k/2}{k/2}\)就可以了

Code:

#include <cstdio>

#define ll long long

const ll mod=1e9+7;

const int N=1e4+10;

ll inv[N<<3],fac[N<<3],dp[16][N];

ll qp(ll d,ll k)

{

    ll f=1;

    while(k)

    {

        if(k&1) f=f*d%mod;

        d=d*d%mod;

        k>>=1;

    }

    return f;

}

ll C(int m,int n)

{

    if(n<0||m<n) return 0;

    return fac[m]*inv[m-n]%mod*inv[n]%mod;

}

int main()

{

    int n,k,d;

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

    fac[0]=1;int le=1<<15;

    for(int i=1;i<=le;i++) fac[i]=fac[i-1]*i%mod;

    inv[le]=qp(fac[le],mod-2);

    for(int i=le-1;~i;i--) inv[i]=inv[i+1]*(i+1)%mod;

    dp[0][0]=1;

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

    {

        int len=1<<i;

        for(int x=0;x*len*(d+1)<=n;x++)

            for(int j=0;j+x*len*(d+1)<=n;j++)

                (dp[i+1][j+x*len*(d+1)]+=dp[i][j]*C(k/2,x*(d+1)))%=mod;

    }

    ll ans=0;

    for(int i=0;i<=n;i++) (ans+=dp[15][i]*C(n-i-k/2,k/2))%=mod;

    printf("%lld\n",(C(n,k)-ans+mod)%mod);

    return 0;

}

2018.12.18

黑白棋