[51nod1773]A国的贸易

题目链接：

51nod1773

首先可以很简单的写出每一天的DP转移式：

(f[i][x]=sum f[i-1][x xor k](k=0 or k=2^j,0le j<n))

其中(f[i][x])表示第(i)天(x)国货物数量((0le 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?'
':' ');
	fwrite(Out,1,p3-Out,stdout);
	return 0;
}