[51nod1773]A国的贸易

题目链接：

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;
}

[51nod1773]A国的贸易

代码：

推荐阅读