題目鏈接：
51nod1773
首先可以很簡單的寫出每一天的DP轉移式：
\(f[i][x]=\sum f[i-1][x\ xor\ k](k=0\ or\ k=2^j,0\le j<n)\)
其中\(f[i][x]\)表示第\(i\)天\(x\)國貨物數量\((0\le x<2^n)\)。
那么因為\(k\)有固定的取值，設數組\(A\)表示當前每個國家的貨物量，數組\(B\)滿足\(B_k=1\)（\(k\)為轉移式中符合條件的\(k\)，否則\(B_k\)=0）
那么每一次的轉移（\((A*B)_k=\sum_{i\ xor\ j=k}A_iB_j\)）就可以用\(FWT\)加速。
最后用快速冪加速\(T\)次乘法即可。
時間復雜度 \(O(2^nlog_22^n=n2^n)\)
代碼：
#include <cstdio>
#include <cctype>
typedef long long ll;char In[1<<20],*p1=In,*p2=In;
#define Getchar (p1==p2&&(p2=(p1=In)+fread(In,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int Getint()
{register int x=0,c;while(!isdigit(c=Getchar));for(;isdigit(c);c=Getchar)x=x*10+(c^48);return x;
}char Out[12000005],*p3=Out;
char St[15],*Tp=St;
inline void Putint(int x,const char c)
{do *Tp++=x%10^48;while(x/=10);do *p3++=*--Tp;while(Tp!=St);*p3++=c;
}int n,t;
int a[1<<20],b[1<<20];
const int Mod=1000000007,Inv2=(Mod+1)>>1;inline int Pow(ll a,ll b)
{ll Res=1;for(;b;b>>=1,a=a*a%Mod)if(b&1)Res=Res*a%Mod;return Res%Mod;
}void FWT(int *A,int t)
{for(register int i=2;i<=n;i<<=1)for(register int j=0,h=i>>1;j<n;j+=i)for(register int k=0,x,y;k<h;++k){x=A[j+k],y=A[j+h+k];A[j+k]=(ll)(x+y)*(t==1?1:Inv2)%Mod;A[j+h+k]=(ll)(x-y+Mod)*(t==1?1:Inv2)%Mod;}
}int main()
{n=Getint(),t=Getint(),b[0]=1;for(register int i=0;i<n;++i)b[1<<i]=1;n=1<<n;for(register int i=0;i<n;++i)a[i]=Getint();FWT(a,1),FWT(b,1);for(register int i=0;i<n;++i)a[i]=(ll)a[i]*Pow(b[i],t)%Mod;//T次轉移的b數組都相同FWT(a,-1);for(register int i=0;i<n;++i)Putint(a[i],i==n-1?'\n':' ');fwrite(Out,1,p3-Out,stdout);return 0;
}
)
)
