BZOJ 4589 Hard Nim 博弈论+FWT

https://www.lydsy.com/JudgeOnline/problem.php?id=4589

思路： N i m Nim Nim博弈先手必败的条件是 n n n堆石子的异或和为 0 0 0，所以本题就是求 n n n个 < = m <=m <=m的异或和为 0 0 0的质数的方案数。显然可以 d p dp dp，设 d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i堆石子异或和为 j j j的方案数，则 d p [ i ] [ j ] = ∑ d p [ i − 1 ] [ j   x o r   p ] dp[i][j]=∑dp[i-1][j\ xor\ p] dp[i][j]=∑dp[i−1][j xor p]，其中 p p p为质数。如果我们有一个数组 v [ i ] v[i] v[i]表示 i i i是否是小于等于 m m m的质数(若 i i i是质数则 v [ i ] = 1 v[i]=1 v[i]=1)，则这个转移可以看作是 d p [ i − 1 ] dp[i-1] dp[i−1]和 v v v进行的特殊卷积，再依据 N i m Nim Nim博弈的特点，不难联想到 F W T FWT FWT ，又因为 d p [ 0 ] = v dp[0]=v dp[0]=v，所以对于两堆式子其实就是： F [ i ] = ∑ j   x o r   k = i v [ j ] ∗ v [ k ] F[i]=\sum_{j\ xor\ k=i}v[j]*v[k] F[i]=j xor k=i∑​v[j]∗v[k]

a n s = F [ 0 ] ans=F[0] ans=F[0]

然而现在有 n n n堆石子，暴力做吗？肯定会 T T T。做一次 F W T FWT FWT后取 n n n次方，然后做一次 I F W T IFWT IFWT就可以了。

#include<bits/stdc++.h>
using namespace std;        //FWT
typedef long long ll;

const int maxn=5e4+5;
const int MOD=1e9+7;

int n,m,limit,k;
bool vis[maxn];
int prime[maxn];
ll a[maxn<<2];

void euler()
{
    vis[1]=1;
    int MAX=5e4;
    for(int i=2;i<=MAX;i++)
    {
        if(!vis[i])
            prime[++k]=i;
        for(int j=1;j<=k&&prime[j]*i<=MAX;j++)
        {
            vis[prime[j]*i]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}

inline ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ans;
}

inline void FWT_xor(ll *A,int inv)
{
    ll x,y;
    ll inv2=MOD+1>>1; //因为MOD是一个质数 所以(MOD+1)/2 就是2模MOD的乘法逆元
    for(int mid=1;mid<limit;mid<<=1)
    {
        for(int i=0;i<limit;i+=mid<<1)
        {
            for(int j=0;j<mid;j++)
            {
                x=A[i+j],y=A[mid+i+j];
                A[i+j]=(x+y)%MOD;
                A[mid+i+j]=(x-y+MOD)%MOD;
                if(inv==-1)
                {
                    A[i+j]=A[i+j]*inv2%MOD; // 2模MOD的乘法逆元 如果题目不是在模意义下的 除2即可
                    A[mid+i+j]=A[mid+i+j]*inv2%MOD;
                }
            }
        }
    }
}

int main()
{
    euler();
    while(~scanf("%d %d",&n,&m))
    {
        limit=1;
        while(limit<=m)
            limit<<=1;
        memset(a,0,sizeof(ll)*limit);
        for(int i=1;i<=k&&prime[i]<=m;i++)
            a[prime[i]]=1;
        FWT_xor(a,1);
        for(int i=0;i<limit;i++)
            a[i]=qpow(a[i],n);
        FWT_xor(a,-1);
        printf("%lld\n",a[0]);
    }
    return 0;
}