自动搬运

查看原文

来自洛谷，原作者为

	FZzzz **

搬运于2025-08-24 22:22:58，当前版本为作者最后更新于2021-12-24 10:53:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实是挺无聊的一个板子题，我不会做真的是败笔。

构造数列 $g$，若 $i$ 的三进制表示中有 $x$ 个 $1$ 和 $y$ 个 $2$，则 $g_i=b_{x,y}$。那么容易发现 $f_i$ 即为 $f_{i-1}$ 与 $g$ 的高维循环卷积，每一维长度为 $3$（$3$ 进制不进位加法卷积）。

显然我们对它进行三进制的 FWT，即高维 FFT。FFT 的意义是多项式在单位根处的取值，但是我们不方便求三次单位根。

作为一个熟练的选手立即想到扩域。将每个复数表示为 $a\omega_3+b$ 的形式（而非 $ai+b$），那么根据 $\omega_3^3=1$ 且 $\omega_3\ne1$，$\omega_3^2+\omega_3+1=0$ 可以定义乘法。

IFWT 的式子可以手解一下三元一次方程。但是我们还需要证明 $3$ 有逆元，这是容易的：若 $3\mid p$ 有 $x=y=\dfrac23p$ 满足 $\dfrac1x+\dfrac1y=\dfrac3p$。

FWT 是线性变换，所以直接 FWT 过去之后快速幂一下再 IFWT 回来即可。

时间复杂度 $O(3^m(m+\log))$，轻微卡常。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll readint(){
	ll x=0;
	bool f=0;
	char c=getchar();
	while(!isdigit(c)&&c!='-') c=getchar();
	if(c=='-'){
		f=1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return f?-x:x;
}
const int maxn=5.4e5,maxm=12+5;
int m,n=1,t,p,b[maxm][maxm],phip;
struct cp{
	int a,b;
	cp operator +(cp x){
		return {(a+x.a)%p,(b+x.b)%p};
	}
	cp operator *(cp x){
		return {(int)((1ll*a*x.b%p+1ll*b*x.a%p-1ll*a*x.a%p+p)%p),(int)((1ll*b*x.b%p-1ll*a*x.a%p+p)%p)};
	}
	cp operator *(ll x){
		return {(int)(1ll*a*x%p),(int)(1ll*b*x%p)};
	}
}f[maxn],g[maxn];
cp ksm(cp a,int b){
	cp ans={0,1};
	while(b){
		if(b%2==1) ans=ans*a;
		a=a*a;
		b/=2;
	}
	return ans;
}
int phi(int n){
	int res=n;
	for(int i=2;i*i<=n;i++) if(n%i==0){
		res=1ll*res*(i-1)/i;
		while(n%i==0) n/=i;
	}
	if(n>1) res=1ll*res*(n-1)/n;
	return res;
}
int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b%2==1) ans=1ll*ans*a%p;
		a=1ll*a*a%p;
		b/=2;
	}
	return ans;
}
void FWT(cp* f,int n,bool flag){
	for(int i=1;i<n;i*=3) for(int j=0;j<n;j+=i*3) for(int k=j;k<j+i;k++){
		cp t0=f[k],t1=f[k+i],t2=f[k+i*2];
		if(flag){
			f[k]=t0+t1+t2;
			f[k+i]=t0+t1*(cp){1,0}+t2*(cp){p-1,p-1};
			f[k+i*2]=t0+t1*(cp){p-1,p-1}+t2*(cp){1,0};
		}
		else{
			f[k]=t0+t1+t2;
			f[k+i]=t0+t1*(cp){p-1,p-1}+t2*(cp){1,0};
			f[k+i*2]=t0+t1*(cp){1,0}+t2*(cp){p-1,p-1};
		}
	}
	if(!flag){
		int invn=ksm(n,phip-1);
		for(int i=0;i<n;i++) f[i]=f[i]*invn;
	}
}
int main(){
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	m=readint();
	for(int i=0;i<m;i++) n*=3;
	t=readint();
	p=readint();
	for(int i=0;i<n;i++) f[i].b=readint();
	for(int i=0;i<=m;i++) for(int j=0;j<=m-i;j++) b[i][j]=readint();
	for(int i=0;i<n;i++){
		int x=i,cnt1=0,cnt2=0;
		for(int j=0;j<m;j++){
			if(x%3==1) cnt1++;
			else if(x%3==2) cnt2++;
			x/=3;
		}
		g[i].b=b[cnt1][cnt2];
	}
	phip=phi(p);
	FWT(f,n,1);
	FWT(g,n,1);
	for(int i=0;i<n;i++) f[i]=f[i]*ksm(g[i],t);
	FWT(f,n,0);
	for(int i=0;i<n;i++) printf("%d\n",f[i].b);
	#ifdef LOCAL
	fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
	#endif
	return 0;
}