bzoj4589 Hard Nim 题解【FWT】【博弈】【快速幂】

点击量：217

我们需要理解变换的本质从而不会像个煞笔一样给自己增添不必要的复杂度。

目录

Description

Claris 和 NanoApe 在玩石子游戏，他们有 $n$ 堆石子，规则如下：

1. Claris 和 NanoApe 两个人轮流拿石子，Claris 先拿。

2. 每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后 $1$ 颗石子的人获胜。

不同的初始局面，决定了最终的获胜者，有些局面下先拿的 Claris 会赢，其余的局面 Claris 会负。

Claris 很好奇，如果这 $n$ 堆石子满足每堆石子的初始数量是不超过 $m$ 的质数，而且他们都会按照最优策略玩游戏，那么 NanoApe 能获胜的局面有多少种。

由于答案可能很大，你只需要给出答案对 $10^9+7$ 取模的值。

Input

输入文件包含多组数据，以 EOF 为结尾。

对于每组数据：

共一行两个正整数 $n$ 和 $m$。

每组数据有 $1\le n\le 10^9, 2\le m\le 50000$。

不超过 $80$ 组数据。

Output

输出答案对 $10^9+7$ 取模的结果。

Sample Input

3 7
4 13

Sample Output

6
120

Source

Topcoder SRM 518 Div1 Hard Nim By Tangjz

题解：

由 NIM 博弈的性质，我们知道当且仅当
$$
\bigoplus_{i=1}^na_i=0
$$
时（其中 $\oplus$ 表示异或），先手必败。

因此我们要求出使得 $\bigoplus_{i=1}^na_i=0$ 的方案数。

令 $b_i=\left\{\begin{aligned}0&,i\text{ 不是质数}\\1&,i\text{ 是质数}\end{aligned}\right.,i\le m$。

当 $n=2$ 时，答案就是 $(b*b)_0$。其中 $*$ 表示异或卷积。容易联想到，当 $n\ge 2$ 时，答案是
$$
\underbrace{b*b*\cdots*b}_{n\text{ 个 }b}
$$
由于每个 $b$ 都是一样的，所以我们想到了 倍增/快速幂，这样就可以在 $O(m\log nm)$ 的时间内解决单个问题。但是有 $T=80$ 组数据，算下来就是 $50000\times 30\times 16\times 80\ge 10^9$，无法在规定时间内跑出来。

但是沃尔什变换是干什么用的干什么用的干什么用的

它是先通过正变换，然后相乘，就出现了另一个正变换。再通过逆变换把它变回来。

定义 ${b}^k=\underbrace{b*b*\cdots*b}_{k\text{ 个 }b},\ b^k={b_0^k,b_1^k,\cdots,b_m^k}$。

我们在对 ${b}$ 做正变换后得到 $b’$ 再相乘得到 $b’^2$，就是 ${b}^2$ 的正变换了。

那么我们如果每次都变换回去，就会很麻烦，而且每次都相当于进行了一次 FWT。

此时我们只需要在 $O(m\log n)$ 的时间复杂度内把 $b’$ 变成 $b’^n$，然后再逆变换回去就可以了。

最终的答案存在 $b_0$ 中，表示 $\bigoplus_{i=1}^na_i=0$。

时间复杂度 $O(Tm\log n)$。

Code：

#include<cstdio>
#include<cstring>
#define p 1000000007
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int read()
{
    int x=0;
    char ch=gc();
    while(ch<'0'||ch>'9')
    {
        if(ch==EOF)
            return -1;
        ch=gc();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+(ch&15);
        ch=gc();
    }
    return x;
}
int f[1<<16];
int pri[10000],cnt;
bool is[51000];
int qpow(int x,int y)
{
    int ans=1;
    while(y)
    {
        if(y&1)
            ans=(long long)ans*x%p;
        x=(long long)x*x%p;
        y>>=1;
    }
    return ans;
}
int main()
{
    #ifdef wjyyy
        freopen("a.in","r",stdin);
    #endif 
    is[0]=is[1]=1;
    for(int i=2;i<=50500;++i)
    {
        if(!is[i])
            pri[++cnt]=i;
        for(int j=1;j<=cnt&&i*pri[j]<=50500;++j)
        {
            is[i*pri[j]]=1;
            if(i%pri[j]==0)
                break;
        }
    }
    int n=read(),m;
    while(~n)
    {
        memset(f,0,sizeof(f));
        m=read();
        int tot=1,N=0;
        while(tot<=m)
            tot<<=1,++N;
        for(int i=1;pri[i]<=m;++i)
            f[pri[i]]=1;
        for(int bs=2;bs<=tot;bs<<=1)
        {
            int g=bs>>1;
            for(int i=0;i<tot;i+=bs)
                for(int j=0;j<g;++j)
                {
                    int t0=(f[i+j]+f[i+j+g])%p,t1=(f[i+j]+p-f[i+j+g])%p;
                    f[i+j]=t0;
                    f[i+j+g]=t1;
                }
        }
        for(int i=0;i<tot;++i)
            f[i]=qpow(f[i],n);
        for(int bs=tot;bs>=2;bs>>=1)
        {
            int g=bs>>1;
            for(int i=0;i<tot;i+=bs)
                for(int j=0;j<g;++j)
                {
                    int t0=(f[i+j]+f[i+j+g])%p,t1=(f[i+j]+p-f[i+j+g])%p;
                    f[i+j]=t0;
                    f[i+j+g]=t1;
                }
        }
        printf("%lld\n",(long long)f[0]*qpow(500000004,N)%p);
        n=read();
    }
    return 0;
}