[THUSCH2017] 大魔法师

标签：break Matrix read res 魔法师 int THUSCH2017

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,MOD=998244353;
int n,m,opt,l,r,v;
struct Matrix{
    int n,m,h[2][5];
    inline void print(){
        printf("%d %d %d\n",h[1][1],h[1][2],h[1][3]);
    }
};
struct Matrixhhh{
    int n,m,h[5][5];
    inline void Set0(int a){
        n=m=a,memset(h,0,sizeof(h));
        for(int i=1;i<=a;++i) h[i][i]=1;
    }
};
Matrix operator + (const Matrix &a,const Matrix &b){
    Matrix ans1;ans1.n=a.n,ans1.m=b.m;
    for(register int i=1;i<=a.n;++i){
        for(register int j=1;j<=b.m;++j)
        ans1.h[i][j]=(a.h[i][j]+b.h[i][j])%MOD;
    }
    return ans1;
}
Matrix operator * (const Matrix &a,const Matrixhhh &b){
    Matrix ans1;ans1.n=a.n,ans1.m=b.m;
    memset(ans1.h,0,sizeof(ans1.h));
    for(register int i=1;i<=a.n;++i){
        for(register int j=1;j<=b.m;++j){
            for(register int k=1;k<=a.m;++k)
            ans1.h[i][j]+=1ll*a.h[i][k]*b.h[k][j]%MOD,ans1.h[i][j]%=MOD;
        }
    }
    return ans1;
}
Matrixhhh operator * (const Matrixhhh &a,const Matrixhhh &b){
    Matrixhhh ans2;ans2.n=a.n,ans2.m=b.m;
    memset(ans2.h,0,sizeof(ans2.h));
    for(register int i=1;i<=a.n;++i){
        for(register int j=1;j<=b.m;++j){
            for(register int k=1;k<=a.m;++k)
            ans2.h[i][j]+=1ll*a.h[i][k]*b.h[k][j]%MOD,ans2.h[i][j]%=MOD;
        }
    }
    return ans2;
}
Matrix s[N];Matrixhhh go[8];
inline void init(){
    for(register int i=1;i<=6;++i) go[i].n=go[i].m=4;
    go[1].h[1][1]=go[1].h[2][2]=go[1].h[3][3]=go[1].h[4][4]=go[1].h[2][1]=1;
    go[2].h[1][1]=go[2].h[2][2]=go[2].h[3][3]=go[2].h[4][4]=go[2].h[3][2]=1;
    go[3].h[1][1]=go[3].h[2][2]=go[3].h[3][3]=go[3].h[4][4]=go[3].h[1][3]=1;
    return ;
}
struct Node{
    Matrix data;
    Matrixhhh tag;
}tr[N<<2];
inline void up(int p){
    tr[p].data=tr[p<<1].data+tr[p<<1|1].data;
}
inline void down(int p,int l,int r){
    int mid=(l+r)>>1;
    tr[p<<1].data=tr[p<<1].data*tr[p].tag;
    tr[p<<1].tag=tr[p<<1].tag*tr[p].tag;
    tr[p<<1|1].data=tr[p<<1|1].data*tr[p].tag;
    tr[p<<1|1].tag=tr[p<<1|1].tag*tr[p].tag;
    tr[p].tag.Set0(4);
    return ;
}
inline void build(int p,int l,int r){
    tr[p].tag.Set0(4);
    if(l==r) return tr[p].data=s[l],void();
    int mid=(l+r)>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    return up(p);
}
inline void add(int p,int l,int r,int x,int y,int opt){
    if(x<=l&&r<=y){
        tr[p].data=tr[p].data*go[opt];
        tr[p].tag=tr[p].tag*go[opt];
        return ;
    }
    int mid=(l+r)>>1;down(p,l,r);
    if(x<=mid) add(p<<1,l,mid,x,y,opt);
    if(y>=mid+1) add(p<<1|1,mid+1,r,x,y,opt);
    return up(p);
}
inline Matrix query(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y) return tr[p].data;
    int mid=(l+r)>>1;down(p,l,r);
    Matrix res;res.n=1,res.m=4;
    memset(res.h,0,sizeof(res.h));
    if(x<=mid) res=res+query(p<<1,l,mid,x,y);
    if(y>=mid+1) res=res+query(p<<1|1,mid+1,r,x,y);
    return res;
}
inline int read(){
    char c=getchar();int x=0;
    while(c<'0'||'9'<c) c=getchar();
    while('0'<=c&&c<='9') x*=10,x+=c-'0',c=getchar();
    return x;
}
signed main(){
    init(),n=read();
    for(register int i=1;i<=n;i+=4){
        s[i].n=1,s[i].m=4;
        s[i].h[1][1]=read();
        s[i].h[1][2]=read();
        s[i].h[1][3]=read();
        s[i].h[1][4]=1;
        if(i+1>n) break;
        s[i+1].n=1;
        s[i+1].m=4;
        s[i+1].h[1][1]=read();
        s[i+1].h[1][2]=read();
        s[i+1].h[1][3]=read();
        s[i+1].h[1][4]=1;
        if(i+2>n) break;
        s[i+2].n=1,s[i+2].m=4;
        s[i+2].h[1][1]=read();
        s[i+2].h[1][2]=read();
        s[i+2].h[1][3]=read();
        s[i+2].h[1][4]=1;
        if(i+3>n) break;
        s[i+3].n=1,s[i+3].m=4;
        s[i+3].h[1][1]=read();
        s[i+3].h[1][2]=read();
        s[i+3].h[1][3]=read();
        s[i+3].h[1][4]=1;
    }
    build(1,1,n);
    m=read();
    for(register int i=1;i<=m;++i){
        opt=read(),l=read(),r=read();
        if(4<=opt&&opt<=6){
            v=read();
            switch(opt){
                case 4:{
                    go[4].h[1][1]=go[4].h[2][2]=go[4].h[3][3]=go[4].h[4][4]=1;
                    go[4].h[4][1]=v;
                    break;
                }
                case 5:{
                    go[5].h[1][1]=go[5].h[3][3]=go[5].h[4][4]=1;
                    go[5].h[2][2]=v;
                    break;
                }
                case 6:{
                    go[6].h[1][1]=go[6].h[2][2]=go[6].h[4][4]=1;
                    go[6].h[4][3]=v;
                    break;
                }
            }
        }
        if(opt==7) query(1,1,n,l,r).print();
        else add(1,1,n,l,r,opt);
    }
}

标签：break,Matrix,read,res,魔法师,int,THUSCH2017
From： https://www.cnblogs.com/certificate/p/16705328.html