rt,太奇怪了,检查了各个矩阵也没看出什么问题
Code:
#include <cstdio>
#include <vector>
const int mod = 998244353;
struct Matrix
{
std::vector < std::vector < long long > > v;
Matrix(int n, int m)
{
v.resize(n);
for (auto &i : v)
i.resize(m);
}
Matrix(std::vector < std::vector < long long > > a)
{
v = a;
}
Matrix(){}
Matrix operator * (const Matrix& a) const
{
Matrix b(v.size(), a.v[0].size());
int i, j, k, temp;
for (i = 0; i < (int)v.size(); i++)
for (k = 0; k < (int)v[0].size(); k++)
{
temp = v[i][k];
for (j = 0; j < (int)a.v[0].size(); j++)
{
b.v[i][j] += temp * a.v[k][j] % mod;
b.v[i][j] = (b.v[i][j] + mod) % mod;
}
}
return b;
}
};
const Matrix I({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}});
const Matrix A({{1, 0, 0, 0}, {1, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}});
const Matrix B({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 1, 1, 0}, {0, 0, 0, 1}});
const Matrix C({{1, 0, 1, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}});
#define D(x) Matrix({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {x, 0, 0, 1}})
#define E(x) Matrix({{1, 0, 0, 0}, {0, x, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}})
#define F(x) Matrix({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 0, 0}, {0, 0, x, 1}})
#define lson(now) (now << 1)
#define rson(now) (now << 1 | 1)
const int N = 2.5e5 + 5;
int n, m, a[N], b[N], c[N];
struct Segment_Tree
{
Matrix data[N << 2], tag[N << 2];
bool need[N << 2];
void pushup(int now)
{
int l = lson(now), r = rson(now);
data[now].v[0][0] = (data[l].v[0][0] + data[r].v[0][0]) % mod;
data[now].v[0][1] = (data[l].v[0][1] + data[r].v[0][1]) % mod;
data[now].v[0][2] = (data[l].v[0][2] + data[r].v[0][2]) % mod;
data[now].v[0][3] = (data[l].v[0][3] + data[r].v[0][3]) % mod;
}
void pushdown(int now)
{
if (!need[now])
return;
Matrix delta(tag[now].v);
tag[lson(now)] = tag[lson(now)] * delta;
tag[rson(now)] = tag[rson(now)] * delta;
data[lson(now)] = data[lson(now)] * delta;
data[rson(now)] = data[rson(now)] * delta;
need[lson(now)] = need[rson(now)] = 1;
tag[now].v = I.v;
need[now] = 0;
}
void build(int s, int t, int now)
{
need[now] = 0;
tag[now] = I;
if (s == t)
{
data[now].v.resize(1); data[now].v[0].resize(4);
data[now].v[0][0] = a[s], data[now].v[0][1] = b[s];
data[now].v[0][2] = c[s], data[now].v[0][3] = 1;
return;
}
int mid = (s + t) >> 1;
build(s, mid, lson(now));
build(mid + 1, t, rson(now));
data[now].v.resize(1), data[now].v[0].resize(4);
pushup(now);
}
void Modify(int l, int r, int s, int t, int now, Matrix delta)
{
if (l <= s && t <= r)
{
data[now] = data[now] * delta;
tag[now] = tag[now] * delta;
need[now] = 1;
return;
}
pushdown(now);
int mid = (s + t) >> 1;
if (mid >= l)
Modify(l, r, s, mid, lson(now), delta);
if (mid < r)
Modify(l, r, mid + 1, t, rson(now), delta);
pushup(now);
}
Matrix Query(int l, int r, int s, int t, int now)
{
if (l <= s && t <= r)
return data[now];
Matrix res(1, 4), tmp;
pushdown(now);
int mid = (s + t) >> 1;
if (mid >= l)
{
tmp = Query(l, r, s, mid, lson(now));
res.v = tmp.v;
}
if (mid < r)
{
tmp = Query(l, r, mid + 1, t, rson(now));
(res.v[0][0] += tmp.v[0][0]) %= mod;
(res.v[0][1] += tmp.v[0][1]) %= mod;
(tmp.v[0][2] += tmp.v[0][2]) %= mod;
}
pushup(now);
return res;
}
}
Tree;
int opt, l, r, v;
int main()
{
//freopen("1.in", "r", stdin);
scanf("%d", &n);
int i;
for (i = 1; i <= n; i++)
scanf("%d %d %d", &a[i], &b[i], &c[i]);
scanf("%d", &m);
Tree.build(1, n, 1);
while (m--)
{
scanf("%d %d %d", &opt, &l, &r);
if (opt == 1)
Tree.Modify(l, r, 1, n, 1, A);
else if (opt == 2)
Tree.Modify(l, r, 1, n, 1, B);
else if (opt == 3)
Tree.Modify(l, r, 1, n, 1, C);
else if (opt == 4)
{
scanf("%d", &v);
Tree.Modify(l, r, 1, n, 1, D(v));
}
else if (opt == 5)
{
scanf("%d", &v);
Tree.Modify(l, r, 1, n, 1, E(v));
}
else if (opt == 6)
{
scanf("%d", &v);
Tree.Modify(l, r, 1, n, 1, F(v));
}
else
{
Matrix ans(Tree.Query(l, r, 1, n, 1));
printf("%lld %lld %lld\n", ans.v[0][0], ans.v[0][1], ans.v[0][2]);
}
}
return 0;
}