2020牛客暑期多校训练营（第一场） G、BaXianGuoHai, GeXianShenTong（数学、群论）

题面：

题意：
定义一个三元组的运算。 $p = 998244353$
$(a_{0}, a_{1}, a_{2}) * (b_{0}, b_{1}, b_{2}) =$
$((a_{0} b_{0} + a_{1} b_{2} + a_{2} b_{1}) m o d <mtext> </mtext> p, (a_{1} b_{0} + a_{2} b_{2} + a_{0} b_{1}) m o d <mtext> </mtext> p, (a_{2} b_{0} + a_{0} b_{2} + a_{1} b_{1}) m o d <mtext> </mtext> p)$

v是一个三元组 $(x, y, z)$
求 $v^{n}$ ，其中 n 大约是 $2^{400}$ 数量级。

题解：

观察发现：单位元是 $(1, 0, 0)$ ，具有结合律。可以用快速幂加速。
但是 n 的数量级太大了，无法直接快速幂。
玄学发现，循环节为 $p^{2} - 1$ 。（其实是看了别人的，应该是合理猜测+打表试验）
$i n t 128$ 直接冲。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int up=100000;
const ll p32=1ll<<32;
const __int128 mod2=(__int128)mod*mod-1;

struct node
{
    ll a[3];
    void init(void)
    {
        memset(a,0,sizeof(a));
        a[0]=1;
    }
    node operator * (const node &b) const
    {
        node ans;
        ans.a[0]=(a[0]*b.a[0]+a[1]*b.a[2]+a[2]*b.a[1])%mod;
        ans.a[1]=(a[1]*b.a[0]+a[2]*b.a[2]+a[0]*b.a[1])%mod;
        ans.a[2]=(a[2]*b.a[0]+a[0]*b.a[2]+a[1]*b.a[1])%mod;
    	return ans;
	}
}v[maxn];

__int128 p2[500],e[25][maxn];

node mypow(node a,__int128 b)
{
	//node a 不能传引用，因为一个a会被多次使用 
    node ans;
    ans.init();
    while(b)
    {
        if(b&1) ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}

int main(void)
{
    ll n,m,q,z0,a,b;
    while(scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&z0,&a,&b)!=EOF)
    {
        ll z=z0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=2;j++)
            {
                z=(z*a+b)%p32;
                v[i].a[j]=z%mod;
            }
        }

        p2[0]=1;
        for(int i=1;i<=400;i++)
            p2[i]=p2[i-1]*2%mod2;

        for(int k=1;k<=q;k++)
        {
            for(int i=1;i<=n;i++)
            {
                e[k][i]=0;
                for(int j=0;j<=m-1;j++)
                {
                    z=(z*a+b)%p32;
                    e[k][i]=(e[k][i]+z*p2[32*j])%mod2;
                }
            }
        }
       	for(int i=1;i<=q;i++)
        {
            node ans;
            ans.init();
            for(int j=1;j<=n;j++)
                ans=ans*mypow(v[j],e[i][j]);
            printf("%lld %lld %lld\n",ans.a[0],ans.a[1],ans.a[2]);
        }
    }
    return 0;
}