???别的都对,第三列全输出 0???
查看原帖
???别的都对,第三列全输出 0???
809729
SJZ2010楼主2024/1/5 21:33

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;
}
2024/1/5 21:33
加载中...