1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| #include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define W while #define I inline #define RI register int #define LL long long #define Cn const #define CI Cn int& using namespace std; namespace Debug{ Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;} Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);} Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;} #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__) }using namespace Debug; namespace FastIO{ #define FS 100000 #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++) #define pc(c) (FC==FE&&(clear(),0),*FC++=c) int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS; I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;} Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));} Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);} Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');} }using namespace FastIO; Cn int N=531450,M=13; int n,m,t,P,a[M][M]; I int C(RI x,CI v){RI i,X=0;for(i=0;i<m;i++) X+=(x%3==v),x/=3;return X;} struct node{int x,y;I node(CI a=0,CI b=0):x(a),y(b){}}; I node operator+(Cn node& X,Cn node& Y){return (node){(X.x+Y.x)%P,(X.y+Y.y)%P};} I node operator-(Cn node& X,Cn node& Y){return (node){(X.x+P-Y.x)%P,(X.y+P-Y.y)%P};} I node operator*(Cn node& X,Cn node& Y){RI o=P-1LL*X.y*Y.y%P;return (node){(1LL*X.x*Y.x+o)%P,(1LL*X.x*Y.y+1LL*X.y*Y.x+o)%P};} struct FWT{node f[N];}S,A; I node QP(node a,RI b){node s=(node){1,0};W(b) b&1&&(s=s*a,0),a=a*a,b>>=1;return s;} I void exgcd(CI a,CI b,int& x,int& y){if(!b) return x=1,y=0,void();exgcd(b,a%b,y,x),y-=a/b*x;} I void AFWT(FWT& s){ RI i,j,k;node x,y,z;for(i=1;i^n;i*=3) for(j=0;j^n;j+=i*3) for(k=0;k^i;++k) x=s.f[j+k],y=s.f[i+j+k],z=s.f[2*i+j+k],s.f[j+k]=x+y+z,s.f[i+j+k]=x+y*(node){0,1}+z*(node){P-1,P-1},s.f[2*i+j+k]=x+y*(node){P-1,P-1}+z*(node){0,1}; } I void UFWT(FWT& s){ RI i,j,k;node x,y,z;for(i=1;i^n;i*=3) for(j=0;j^n;j+=i*3) for(k=0;k^i;++k) x=s.f[j+k],y=s.f[i+j+k],z=s.f[2*i+j+k],s.f[j+k]=x+y+z,s.f[i+j+k]=x+y*(node){P-1,P-1}+z*(node){0,1},s.f[2*i+j+k]=x+y*(node){0,1}+z*(node){P-1,P-1}; RI a,b;for(exgcd(n,P,a,b),a=(a%P+P)%P,i=0;i^n;++i) s.f[i].x=1LL*s.f[i].x*a%P; } int main(){ freopen("guess.in","r",stdin),freopen("guess.out","w",stdout); RI i,j;for(read(m,t,P),n=pow(3,m),i=0;i<n;i++) read(S.f[i].x);for(i=0;i<=m;i++) for(j=0;j<=m-i;j++) read(a[i][j]); for(i=0;i<n;i++) A.f[i].x=a[C(i,1)][C(i,2)]; for(AFWT(S),AFWT(A),i=0;i<n;i++) S.f[i]=S.f[i]*QP(A.f[i],t); for(UFWT(S),i=0;i<n;i++) writeln(S.f[i].x);return clear(),0; }
|