提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

YbtOJ 971「fwt」猜拳游戏

游戏 YbtOJ
2023-06-13 09:12:49 时间

YbtOJ 971「fwt」猜拳游戏

题目链接：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

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

相关文章