求调
查看原帖
求调
959201
Sukilin楼主2024/12/15 10:40
#include <iostream>
#include <cstdio>
//#define int long long
const int N = 2.5e5, NN = (1 << 18) + 7, MOD = 998244353;
class mat4 {
    public:
        int a[5][5];
        friend mat4 operator + (mat4 x, mat4 y) {
            mat4 res;
            res.a[1][1] = (x.a[1][1] + y.a[1][1]) % MOD;
            res.a[1][2] = (x.a[1][2] + y.a[1][2]) % MOD;
            res.a[1][3] = (x.a[1][3] + y.a[1][3]) % MOD;
            res.a[1][4] = (x.a[1][4] + y.a[1][4]) % MOD;
            res.a[2][1] = (x.a[2][1] + y.a[2][1]) % MOD;
            res.a[2][2] = (x.a[2][2] + y.a[2][2]) % MOD;
            res.a[2][3] = (x.a[2][3] + y.a[2][3]) % MOD;
            res.a[2][4] = (x.a[2][4] + y.a[2][4]) % MOD;
            res.a[3][1] = (x.a[3][1] + y.a[3][1]) % MOD;
            res.a[3][2] = (x.a[3][2] + y.a[3][2]) % MOD;
            res.a[3][3] = (x.a[3][3] + y.a[3][3]) % MOD;
            res.a[3][4] = (x.a[3][4] + y.a[3][4]) % MOD;
            res.a[4][1] = (x.a[4][1] + y.a[4][1]) % MOD;
            res.a[4][2] = (x.a[4][2] + y.a[4][2]) % MOD;
            res.a[4][3] = (x.a[4][3] + y.a[4][3]) % MOD;
            res.a[4][4] = (x.a[4][4] + y.a[4][4]) % MOD;
            return res;
        }
        friend mat4 operator * (mat4 x, mat4 y) {
            mat4 res;
            res.a[1][1] = (1ll * x.a[1][1] * y.a[1][1] + 1ll * x.a[1][2] * y.a[2][1] + 1ll * x.a[1][3] * y.a[3][1] + 1ll * x.a[1][4] * y.a[4][1]) % MOD;
            res.a[1][2] = (1ll * x.a[1][1] * y.a[1][2] + 1ll * x.a[1][2] * y.a[2][2] + 1ll * x.a[1][3] * y.a[3][2] + 1ll * x.a[1][4] * y.a[4][2]) % MOD; 
            res.a[1][3] = (1ll * x.a[1][1] * y.a[1][3] + 1ll * x.a[1][2] * y.a[2][3] + 1ll * x.a[1][3] * y.a[3][3] + 1ll * x.a[1][4] * y.a[4][3]) % MOD; 
            res.a[1][4] = (1ll * x.a[1][1] * y.a[1][4] + 1ll * x.a[1][2] * y.a[2][4] + 1ll * x.a[1][3] * y.a[3][4] + 1ll * x.a[1][4] * y.a[4][4]) % MOD; 
            res.a[2][1] = (1ll * x.a[2][1] * y.a[1][1] + 1ll * x.a[2][2] * y.a[2][1] + 1ll * x.a[2][3] * y.a[3][1] + 1ll * x.a[2][4] * y.a[4][1]) % MOD;
            res.a[2][2] = (1ll * x.a[2][1] * y.a[1][2] + 1ll * x.a[2][2] * y.a[2][2] + 1ll * x.a[2][3] * y.a[3][2] + 1ll * x.a[2][4] * y.a[4][2]) % MOD; 
            res.a[2][3] = (1ll * x.a[2][1] * y.a[1][3] + 1ll * x.a[2][2] * y.a[2][3] + 1ll * x.a[2][3] * y.a[3][3] + 1ll * x.a[2][4] * y.a[4][3]) % MOD; 
            res.a[2][4] = (1ll * x.a[2][1] * y.a[1][4] + 1ll * x.a[2][2] * y.a[2][4] + 1ll * x.a[2][3] * y.a[3][4] + 1ll * x.a[2][4] * y.a[4][4]) % MOD; 
            res.a[3][1] = (1ll * x.a[3][1] * y.a[1][1] + 1ll * x.a[3][2] * y.a[2][1] + 1ll * x.a[3][3] * y.a[3][1] + 1ll * x.a[3][4] * y.a[4][1]) % MOD;
            res.a[3][2] = (1ll * x.a[3][1] * y.a[1][2] + 1ll * x.a[3][2] * y.a[2][2] + 1ll * x.a[3][3] * y.a[3][2] + 1ll * x.a[3][4] * y.a[4][2]) % MOD;
            res.a[3][3] = (1ll * x.a[3][1] * y.a[1][3] + 1ll * x.a[3][2] * y.a[2][3] + 1ll * x.a[3][3] * y.a[3][3] + 1ll * x.a[3][4] * y.a[4][3]) % MOD; 
            res.a[3][4] = (1ll * x.a[3][1] * y.a[1][4] + 1ll * x.a[3][2] * y.a[2][4] + 1ll * x.a[3][3] * y.a[3][4] + 1ll * x.a[3][4] * y.a[4][4]) % MOD; 
            res.a[4][1] = (1ll * x.a[4][1] * y.a[1][1] + 1ll * x.a[4][2] * y.a[2][1] + 1ll * x.a[4][3] * y.a[3][1] + 1ll * x.a[4][4] * y.a[4][1]) % MOD; 
            res.a[4][2] = (1ll * x.a[4][1] * y.a[1][2] + 1ll * x.a[4][2] * y.a[2][2] + 1ll * x.a[4][3] * y.a[3][2] + 1ll * x.a[4][4] * y.a[4][2]) % MOD; 
            res.a[4][3] = (1ll * x.a[4][1] * y.a[1][3] + 1ll * x.a[4][2] * y.a[2][3] + 1ll * x.a[4][3] * y.a[3][3] + 1ll * x.a[4][4] * y.a[4][3]) % MOD; 
            res.a[4][4] = (1ll * x.a[4][1] * y.a[1][4] + 1ll * x.a[4][2] * y.a[2][4] + 1ll * x.a[4][3] * y.a[3][4] + 1ll * x.a[4][4] * y.a[4][4]) % MOD;
            return res;
        }
        void clear() {
            this -> a[1][1] = this -> a[1][2] = this -> a[1][3] = this -> a[1][4] = this -> a[2][1] = this -> a[2][2] = this -> a[2][3] = this -> a[2][4] = this -> a[3][1] = this -> a[3][2] = this -> a[3][3] = this -> a[3][4] = this -> a[4][1] = this -> a[4][2] = this -> a[4][3] = this -> a[4][4] = 0;
        }
        void init() {
            this -> a[1][2] = this -> a[1][3] = this -> a[1][4] = this -> a[2][1] = this -> a[2][3] = this -> a[2][4] = this -> a[3][1] = this -> a[3][2] = this -> a[3][4] = this -> a[4][1] = this -> a[4][2] = this -> a[4][3] = 0;
            this -> a[1][1] = this -> a[2][2] = this -> a[3][3] = this -> a[4][4] = 1;
        }
};
mat4 ar[N];
mat4 tr[NN];
mat4 laz[NN];
void build(int L, int R, int p) {
    laz[p].init();
    if(L == R) {
        tr[p] = ar[L];
        return;
    }
    int mid = L + R >> 1;
    build(L, mid, p << 1);
    build(mid + 1, R, p << 1 | 1);
    tr[p] = tr[p << 1] + tr[p << 1 | 1];
}
void mul(int L, int R, int l, int r, int p, mat4 k) {
    if(L >= l && R <= r) {
        tr[p] = tr[p] * k;
        laz[p] = laz[p] * k;
        return;
    }
    int mid = L + R >> 1;
    tr[p << 1] = tr[p << 1] * laz[p];
    tr[p << 1 | 1] = tr[p << 1 | 1] * laz[p];
    laz[p << 1] = laz[p << 1] * laz[p];
    laz[p << 1 | 1] = laz[p << 1 | 1] * laz[p];
    laz[p].init();
    if(l <= mid) mul(L, mid, l, r, p << 1, k);
    if(r > mid) mul(mid + 1, R, l, r, p << 1 | 1, k);
    tr[p] = tr[p << 1] + tr[p << 1 | 1];
}
mat4 getsum(int L, int R, int l, int r, int p) {
    if(L >= l && R <= r) return tr[p];
    int mid = L + R >> 1;
    mat4 res;
    res.clear();
    if(l <= mid) res = res + getsum(L, mid, l, r, p << 1);
    if(r > mid) res = res + getsum(mid + 1, R, l, r, p << 1 | 1);
    return res;
}
mat4 op[7];
void opt() {
    op[1].init();
    op[1].a[2][1] = 1;
    op[2].init();
    op[2].a[3][2] = 1;
    op[3].init();
    op[3].a[1][3] = 1;
    op[4].init();
    op[5].init();
    op[5].a[2][2] = 0;
    op[6].init();
    op[6].a[3][3] = op[6].a[4][3] = 0;
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    opt();
    int n;
    std::cin >> n;
    for(int i = 1; i <= n; i++) {
        int a, b, c;
        std::cin >> a >> b >> c;
        mat4 tmp;
        tmp.clear();
        tmp.a[1][1] = a;
        tmp.a[1][2] = b;
        tmp.a[1][3] = c;
        tmp.a[1][4] = 1;
        ar[i] = tmp;
    }  
    build(1, n, 1);
    int m;
    std::cin >> m;
    for(int i = 1; i <= m; i++) {
        int o, l, r, v;
        std::cin >> o >> l >> r;
        if(o != 7) {
            if(o == 4 || o == 5 || o == 6) {
                std::cin >> v;
                if(o == 4)
                    op[o].a[4][1] = v;
                else if(o == 5)
                    op[o].a[2][2] = v;
                else if(o == 6)
                    op[o].a[4][3] = v;
            }
            mul(1, n, l, r, 1, op[o]);
        }
        else {
            mat4 ans = getsum(1, n, l, r, 1);
            std::cout << ans.a[1][1] << ' ' << ans.a[1][2] << ' ' << ans.a[1][3] << '\n';
        }
    }
    return 0;
}

#3#4AC别的都蛙

2024/12/15 10:40
加载中...