YbtOJ 971「fwt」猜拳游戏

(Updated: )
oi

题目链接：YbtOJ #971

有 $n=3^m$ 个人（标号为 $0\sim 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$ 取模）

$1\le m\le12$，$0\le t\le10^9$，$1\le P\le10^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

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;
}