BZOJ4589 Hard Nim（快速沃尔什变换FWT）

这是我第一道独立做出来的FWT的题目，所以写篇随笔纪念一下。

（这还要纪念，我太弱了）

题目链接：

题目大意：两人玩nim游戏（多堆石子，每次可以从其中一堆取任意多个，不能操作就输）。$T$ 组数据，现在问如果 $n$ 堆石子，每堆石子个数都是不超过 $m$ 的素数，有多少种不同的石子序列使得先手没有必胜策略，答案对 $10^9+7$ 取模。（石子堆顺序不同也算不同）

$1\leq T\leq 80,1\leq n\leq 10^9,1\leq m\leq 5\times 10^4$。

首先肯定要把 $m$ 以内的素数筛出来。

nim游戏的SG函数大家都知道吧！就是它本身。

所以若先手没有必胜策略，那么所有石子堆的石子个数的异或和为 $0$。

考虑 $dp[i][j]$ 为前 $i$ 堆石子，异或和为 $j$ 的石子序列总数。题目要求即为 $dp[n][0]$。

另外令 $g[x]=[x\leq m \&\& x\in prime]$，即若 $x$ 为 $m$ 以内的素数则 $g[x]=1$ 否则 $g[x]=0$。

（以下 $\oplus$ 均代表异或）

那么有边界：

$dp[1][x]=[g[x]==1]$

考虑到 $j\oplus k\oplus k=j$，那么转移方程：

$dp[i][j]=\sum^m_{k=1}dp[i-1][j\oplus k]\quad [g[k]==1]$

这样暴力转移复杂度是 $O(Tm^2n)$ 的，考虑优化。

可以发现 $g[x]=[g[x]==1]$，那么边界和转移方程可以化为：

$dp[1][x]=g[x]$

$dp[i][j]=\sum^m_{k=1}dp[i-1][j\oplus k]g[k]$

发现这其实是个多项式异或卷积的形式（因为 $dp[i-1][j\oplus k]g[k]$ 会贡献到 $dp[i][j]=dp[i][(j\oplus k)\oplus k]$）

那么用 $FWT$ 优化转移。时间复杂度优化至 $O(Tm(\log m)n)$。但还是不够！

我们发现：

$dp[1][x]=g[x]$，也就是 $dp[1]$ 是 $g$ 本身，即异或卷积意义下的 $g^1$

$dp[2][x]=\sum^m_{k=1}dp[1][x\oplus k]g[k]=\sum^m_{k=1}g[x\oplus k]g[k]$，也就是 $dp[2]$ 是异或卷积意义下的 $g^2$

$\dots\dots$

至于 $dp[3]$ 我推不出来

我们科学证明一下：异或卷积是满足结合律的，所以若 $dp[i-1]$ 是 $g^{i-1}$，那么 $dp[i]$ 就是 $dp[i-1]\times g=g^{i-1}\times g=g^i$。

所以 $dp[i]=g^i$。

刚刚说了异或卷积满足结合律，所以可以快速幂加速求 $dp[n]=g^n$，那么 $dp[n][0]$ 也就求完了，问题迎刃而解。

时间复杂度 $O(Tm\log m\log n)$，还差一点点才能通过。

加一个小优化就行了：在快速幂中乘法要乘很多次，如果每乘完一次就要 $O(mlogm)$ 变换就浪费了。可以一开始 $FWT$，快速幂的过程中只有点值相乘没有变换，完了之后再 $FWT$，少了很多运算。

这样就可以用 $O(Tm(\log m+\log n))$ 通过了。

（p.s：$FWT$ 是对模数没有要求的，不要被 $10^9+7$ 吓到了。）

上代码：

#include<bits/stdc++.h>

using namespace std;

const int mod=,inv=;    //2的逆元为500000004

int n,m,limit;

int a[],ans[];

int prime[],pl;

bool vis[];

void FWT(int *c,int type){    //模板

    for(int mid=;mid<limit;mid<<=)

        for(int r=mid<<,j=;j<limit;j+=r)

            for(int k=;k<mid;k++){

                int x=c[j+k],y=c[j+k+mid];

                c[j+k]=(x+y)%mod;c[j+k+mid]=(x-y+mod)%mod;

                if(type==-){

                    c[j+k]=1ll*c[j+k]*inv%mod;c[j+k+mid]=1ll*c[j+k+mid]*inv%mod;

                }

            }

}

void mult(int *a,int *b,int *c){    //点值相乘（为何这里面没有FWT？上面说过这会浪费时间）

    for(int i=;i<limit;i++) c[i]=1ll*a[i]*b[i]%mod;

}

void quickpow(int *a,int b){

    memset(ans,,sizeof(ans));

    ans[]=;    //初始化

    FWT(a,);FWT(ans,);    //一开始就变换

    while(b){    //快速幂

        if(b&) mult(ans,a,ans);

        mult(a,a,a);

        b>>=;

    }    //中间不变换

    FWT(a,-);FWT(ans,-);    //这时才变换回去

}

void init(){    //筛素数，作为转移数组

    vis[]=true;

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

        if(!vis[i]) prime[++pl]=i;

        for(int j=;j<=pl && i*prime[j]<=;j++){

            vis[i*prime[j]]=true;

            if(i%prime[j]==) break;

        }

    }

}

int main(){

    init();

    while(~scanf("%d%d",&n,&m)){

        memset(a,,sizeof(a));

        for(limit=;limit<=m;limit<<=);

        for(int i=;i<=pl && prime[i]<=m;i++) a[prime[i]]=;    //转移数组

        quickpow(a,n);

        printf("%d\n",ans[]);

    }

}

FWT

巴特西

BZOJ4589 Hard Nim（快速沃尔什变换FWT）

最新文章

热门文章