[bzoj4589]Hard Nim

首先这道题我们通过一个nim游戏的模型可以得到答案是要用在一堆数组成一个n个数且异或和为0的排列的方案数。

可以得到一个 O(nm^2) 的DP。

f(i,j) 表示i个数异或和为j的方案数。我们发现可以把第二维作为多项式来进行运算，这个运算可以使用FWT进行优化。

进一步思考，设 f(1) 的第二维状态为多项式 G(x) ，我们要求的其实就是：

\otimes_{i=1}^{n}G(x)

如果我们按照这个式子进行FWT优化，可以优化到 O(nmlgm) ，但是事实上我们发现每次我们FWT之后不需要再用逆FWT变换回去，可以直接与下一次要运算的多项式FWT之后的东西按每一位直接相乘。最后再逆FWT回去。

那么其实我们只需要把第一次FWT之后的每一项变成原先的n次方然后再逆FWT回去即可。这个直接一个快速幂就好了。

所以我们现在的时间复杂度是 O(mlgn)

另一种方法是倍增DP，但是这个时间复杂度是

O(mlgnlgm)

的，在这题会TLE。

\#include<cstdio>
typedef long long ll;
const int MAX_N=1<<17|5,MOD=1e9+7,INV2=MOD+1>>1;
int a[MAX_N];
inline int mod(const int& x){ return x>=MOD?x-MOD:x; }
inline void FWT(int* a,int n,int t){
    for(register int step=1;step<n;step<<=1)
        for(register int i=0;i<n;++i)
            if(i&step){
                register int x=a[i-step],y=a[i];
                if(t==1){
                    a[i-step]=mod(x+y);
                    a[i]=mod(x+MOD-y);
                }else{
                    a[i-step]=(ll)(x+y)*INV2%MOD;
                    a[i]=(ll)(x+MOD-y)*INV2%MOD;
                }
            }
}
inline int fast_pow(int x,int n){
    int ret=1;
    for(;n;n>>=1){
        n&1?ret=(ll)ret*x%MOD:0;
        x=(ll)x*x%MOD;
    }
    return ret;
}
int prime[MAX_N],top_prime=0;
bool vis[MAX_N];
void Euler(int n){
    for(int i=2;i<=n;++i) vis[i]=true;
    top_prime=0;
    for(int i=2;i<=n;++i){
        vis[i]?prime[++top_prime]=i:0;
        for(int j=1;j<=top_prime&&i*prime[j]<=n;++j){
            vis[i*prime[j]]=false;
            if(i%prime[j]==0) break;
        }
    }
}
int main(){
    Euler(5e4);
    int n,m,top; 
    while(scanf("%d%d",&n,&m)!=EOF){
        for(top=1;top<m+1;top<<=1);
        for(int i=0;i<=top;++i) a[i]=i<=m?vis[i]:0;
        FWT(a,top,1);
        for(int i=0;i<=top;++i) a[i]=fast_pow(a[i],n);
        FWT(a,top,-1);
        printf("%d\n",a[0]);
    }
}