这题的式子形式是异或卷积的三进制推广,因此可以设计一个类似fwt的变换,这里需要一个三次单位根$w$,满足$w^3\%p==1$且$(1+w+w^2)\%p==0$,对给定的模数,在整数中可能找不到满足要求的w,因此考虑模意义的复数域,发现只要用$a+bfrac{sqrt{3}i}{2}$的形式表示复数,a,b为模p意义下的整数,可以满足要求。时间复杂度$O((m+log(t))3^m)$。
#include<cstdio> typedef long long i64; int p,n=1,m,t; struct cplx{ int a,b; cplx(int _a=0,int _b=0):a(_a),b(_b){} cplx operator+(cplx x)const{return cplx((a+x.a)%p,(b+x.b)%p);} cplx operator*(cplx x)const{return cplx((i64(a)*x.a-3ll*b*x.b)%p,(i64(a)*x.b+i64(b)*x.a)%p);} cplx operator^(int n)const{ cplx v(1),x(a,b); for(;n;n>>=1,x=x*x)if(n&1)v=v*x; return v; } }A[600007],B[600007]; void dft(cplx*v,int t){ cplx w1=cplx((p-1)/2,(p+t)/2),w2=w1*w1; for(int i=1;i<n;i*=3){ for(int j=0;j<n;j+=i*3){ cplx*a=v+j,*b=a+i,*c=b+i; for(int k=0;k<i;++k){ cplx a1=a[k],b1=b[k],c1=c[k]; a[k]=a1+b1+c1; b[k]=a1+b1*w1+c1*w2; c[k]=a1+b1*w2+c1*w1; } } } if(t==-1){ i64 In=1,I3=(p*((p+1)%3?2:1)+1)/3; for(int i=0;i<m;++i)In=In*I3%p; for(int i=0;i<n;++i)A[i].a=A[i].a*In%p; } } char ib[10000007],*ip=ib,ob[10000007],*op=ob; int _(){ int x=0; while(*ip<48)++ip; while(*ip>47)x=x*10+*ip++-48; return x; } void pr(int x){ if(x<0)x+=p; int ss[12],sp=0; do ss[++sp]=x%10;while(x/=10); while(sp)*op++=ss[sp--]+48; *op++=10; } int v0[33][33]; void dfs(int w,int u,int t1,int t2){ if(w==m){ B[u]=v0[t1][t2]; return; } u*=3; dfs(w+1,u,t1,t2); dfs(w+1,u+1,t1+1,t2); dfs(w+1,u+2,t1,t2+1); } int main(){ fread(ib,1,sizeof(ib),stdin); m=_(),t=_(),p=_(); for(int i=0;i<m;++i)n*=3; for(int i=0;i<n;++i)A[i]=_(); for(int i=0;i<=m;++i) for(int j=0;j<=m-i;++j)v0[i][j]=_(); dfs(0,0,0,0); dft(A,1); dft(B,1); for(int i=0;i<n;++i)A[i]=A[i]*(B[i]^t); dft(A,-1); for(int i=0;i<n;++i)pr(A[i].a); fwrite(ob,1,op-ob,stdout); return 0; }