http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1773
参考1：FWT讲解 https://www.cnblogs.com/RabbitHu/p/9182047.html
参考2：题解 https://www.cnblogs.com/ivorysi/p/9178577.html
（令$\oplus$表示异或）
设$dp[i][j]$表示第$i$天$j$编号城市货物数。
因为只有$i \oplus j$的答案有一个1才能转移，所以$i\oplus j=2^k$
根据异或的性质变成$i\oplus 2^k=j$。
想办法利用它把转移方程写成卷积的形式。
设$b[2^i]=1$，其余都是$0$，于是就有：
$dp[i][j]=dp[i-1][j]+\sum_{a\oplus k=j}dp[i-1][a]*b[k]$
你会发现把$dp$递归展开之后实际上就是一个卷积套卷积……套$t$次的过程，$FWT$运算加快速幂即可。
注意读入输出优化。
#include<map> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<cctype> #include<vector> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=1<<20; const int p=1e9+7; const int inv=500000004; inline int read(){int X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } void write(int x){if(x>9)write(x/10);putchar('0'+x%10); } inline int add(int x,int y){x+=y;if(x>=p)x-=p;return x; } inline int sub(int x,int y){x-=y;if(x<0)x+=p;return x; } void FWT(int a[],int n,int on){for(int i=1;i<n;i<<=1){for(int j=0;j<n;j+=(i<<1)){for(int k=0;k<i;k++){int u=a[j+k],t=a[j+k+i];a[j+k]=add(u,t);a[j+k+i]=sub(u,t);if(on==-1){a[j+k]=(ll)a[j+k]*inv%p;a[j+k+i]=(ll)a[j+k+i]*inv%p;}}}} } int qpow(int k,int n){int res=1;while(n){if(n&1)res=(ll)res*k%p;k=(ll)k*k%p;n>>=1;}return res; } int n,t,m,a[N],b[N]; int main(){n=read(),t=read(),m=1<<n;for(int i=0;i<m;i++)a[i]=read();for(int i=0;i<m;i++){if(i-(i&-i)==0)b[i]=1;}FWT(a,m,1);FWT(b,m,1);for(int i=0;i<m;i++)a[i]=(ll)a[i]*qpow(b[i],t)%p;FWT(a,m,-1);for(int i=0;i<m;i++){write(a[i]);putchar(' ');}puts("");return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
