YbtOJ 971「fwt」猜拳游戏
题目链接：YbtOJ #971
有 n=3^m 个人（标号为 0sim n-1）在玩猜拳。共有 t 轮游戏，每轮游戏都会进行 m 次猜拳。
把每个人的标号转化为一个三进制数，则标号为 x 的人在每轮的第 i 次都会使出 x 从低到高第 i 位数对应的手势（0 对应剪刀，1 对应石头，2 对应布）。
小 A 设定了一个评分数组 a_{u,v}，记第 i 轮结束后 x 的分数为 f_{i,x}，则第 i 1 轮过后 x 的分数会变成 f_{i 1,x}=sum_{y=0}^{n-1}f_{i,y}times a_{Win(x,y),Lose(x,y)}，其中 Win(x,y) 和 Lose(x,y) 分别表示 x 对 y 赢和输的次数。
现给定所有人初始的分数，小 A 想要知道最终所有人的分数。（答案向给定 P 取模）
1le mle12，0le tle10^9，1le Ple10^9 7 且保证 P 不为 3 的倍数，初始分数和评分数组中的值都在 [0,P) 范围内。
Solution
石头剪刀布本质即为三进制计算，考虑三进制异或。
显然两位选手的操作的三进制不退位减法的结果分别对应 平-0，赢-1，输-2。
所以可以处理出序列 A，满足 A_i=a[text{popcount}_1(i)][text{popcount}_2(i)]。
那么与 f_0 做 t 次三进制异或卷积即可。
发现 omega_3 不好处理，所以可以扩域整个代数单位代替。
根据单位根的性质，注意到 omega_3^2 omega_3 1=0，那么有 omega_3^2=-omega_3-1。
Code
代码语言：javascript复制#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 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;
}
