[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]); } }