BZOJ4347 POI2016Nim z utrudnieniem（博弈+动态规划）

　　由nim游戏的结论，显然等价于去掉一些数使剩下的数异或和为0。

　　暴力的dp比较显然，设f[i][j][k]为前i堆移走j堆（模意义下）后异或和为k的方案数。注意到总石子数量不超过1e7，按a_i从小到大排序，这样k的枚举范围就不会超过2a_i，于是复杂度O(md)。

　　注意空间卡的非常紧，连滚动都开不下，改为留下的有j堆（模意义下）可能比较方便，存一下j=d-1时的数组，对j=1~d-1倒序转移完后再特判j=0即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 500010

#define P 1000000007

int n,m,a[N],u[N<<],f[][<<],tmp[<<];

inline void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4347.in","r",stdin);

    freopen("bzoj4347.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    for (int i=;i<=n;i++) a[i]=read();

    sort(a+,a+n+);

    int t=;

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

    {

        if (t<i) t=t<<|;

        u[i]=t;

    }

    f[][]=;

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

    {

        memcpy(tmp,f[m-],u[a[i]]+<<);

        for (int j=m-;j>=;j--)

            for (int k=;k<=u[a[i]];k++)

            inc(f[j][k],f[j-][k^a[i]]);

        for (int k=;k<=u[a[i]];k++)

        inc(f[][k],tmp[k^a[i]]);

    }

    cout<<(f[n%m][]-(n%m==)+P)%P;

    return ;

}

巴特西

BZOJ4347 POI2016Nim z utrudnieniem（博弈+动态规划）

最新文章

热门文章