返回首页 返回专题

【51NOD1773】A国的贸易 题解

简洁题意

有2n个点，每次i点会使count(i xor j)=1的j点增加ai个货物，其中count(i)表示i在二进制下1的个数，ai表示i点上一次的货物数量。求t次操作后序列中每个数是多少。答案对1e9+7取模

题解

设t次操作后的序列为，根据题意列出柿子：

那个sigma下面的东西怎么看怎么像卷积，那就根据xor的性质来把它变成卷积形式：

定义，特别地，

上式就成功地化为了：

定义卷积满足：

那么上式可以简洁地表达为：

进而得到：

用FWT和快速幂即可，注意不要进行多余的DWT和IDWT，这一点在【BZOJ4589】Hard Nim已经体现过了

此外，本题卡常，需要加读入优化和输出优化

#include<bits/stdc++.h>
#define Mod 1000000007
#define inv2 500000004
using namespace std;

inline int read()
{
	int x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return x;
}

inline void put(int x)
{
    if(x>9) put(x/10);
    putchar(x%10+'0');
}

const int N=2097162;
int f[N],g[N],ans[N];

void FWT(int *a,int n,bool flag)
{
	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 x=a[j+k],y=a[i+j+k];
				if(flag) a[j+k]=(x+y)%Mod,a[i+j+k]=(x-y+Mod)%Mod;
				else a[j+k]=1ll*(x+y)*inv2%Mod,a[i+j+k]=1ll*(x-y+Mod)*inv2%Mod;
			}
}

int main()
{
	int n=read(),t=read();
	int len=1<<n;
	for(int i=0;i<len;i++) f[i]=read();
	if(t==0){for(int i=0;i<len;i++) put(f[i]),putchar(' ');return 0;}
	for(int i=0;i<n;i++) g[1<<i]=1;g[0]=1;
	FWT(f,len,1);FWT(g,len,1);
	for(int i=0;i<len;i++) ans[i]=g[i];
	for(t--;t;t>>=1)
	{
		if(t&1) for(int i=0;i<len;i++) ans[i]=1ll*ans[i]*g[i]%Mod;
		for(int i=0;i<len;i++) g[i]=1ll*g[i]*g[i]%Mod;
	}
	for(int i=0;i<len;i++) ans[i]=1ll*ans[i]*f[i]%Mod;
	FWT(ans,len,0);
	for(int i=0;i<len;i++) put(ans[i]),putchar(' ');
	return 0;
}