求助,过不了样例,感觉写的很正确了(((
查看原帖
求助,过不了样例,感觉写的很正确了(((
448881
PTqwq楼主2023/1/9 20:56

RT,代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i, l, r) for(int i = l;i <= r; ++ i)
#define per(i, r, l) for(int i = r;i >= l; -- i)
const int mod = 998244353;
const int maxn = 250005;
int n, m, val[maxn][3];
struct matrix {
	int a[6][6], n, m;
	inline void init () {
		rep (i, 0, 5) {
			rep (j, 0, 5) {
				a[i][j] = 0;
			}
		}
	}
	inline void initI (int x) {
		init ();
		rep (i, 1, x) a[i][i] = 1;
	} 
} m1, m2, m3;
matrix operator * (matrix a, matrix b) {
	matrix c;
	c.init ();
	if (a.m == b.n) ;
	else swap (a, b);
	c.n = a.n;
	c.m = b.m;
	rep (i, 1, c.n) {
		rep (j, 1, c.m) {
			rep (k, 1, a.m) {
				c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j] % mod) % mod; 
			}
		}
	} 
	return c;
}
matrix operator + (matrix a, matrix b) {
	matrix c;
	c.init ();
	c.n = a.n, c.m = a.m;
	rep (i, 1, a.n) {
		rep (j, 1, a.m) {
			c.a[i][j] = (a.a[i][j] + b.a[i][j]) % mod;
		}
	}
	if (a.n == 1 && a.m == 4) c.a[1][4] = 1;
	return c;
}
matrix sum[maxn << 2], inc[maxn << 2];
inline void push_up (int u) {
	sum[u] = sum[u << 1] + sum[u << 1 | 1];
}
inline void push_down (int u, int l, int r) {
	sum[u << 1] = sum[u << 1] * inc[u];
	sum[u << 1 | 1] = sum[u << 1 | 1] * inc[u];
	inc[u << 1] = inc[u << 1] * inc[u];
	inc[u << 1 | 1] = inc[u << 1 | 1] * inc[u];
	inc[u].init ();
	inc[u].initI (4);
}
inline void build (int u, int l, int r) {
	sum[u].n = 1;
	sum[u].m = 4;
	inc[u].n = inc[u].m = 4;
	inc[u].initI (4);
	if (l == r) {
		sum[u].a[1][1] = val[l][0];
		sum[u].a[1][2] = val[l][1];
		sum[u].a[1][3] = val[l][2];
		sum[u].a[1][4] = 1;
		return ;
	}
	int mid = l + r >> 1;
	build (u << 1, l, mid);
	build (u << 1 | 1, mid + 1, r);
	push_up (u);
}
inline void upd (int u, int l, int r, int x, int y, matrix mtx) {
	if (x <= l && r <= y) {
		inc[u] = inc[u] * mtx;
		sum[u] = sum[u] * mtx;
		return ;
	}
	push_down (u, l, r);
	int mid = l + r >> 1;
	if (x <= mid) upd (u << 1, l, mid, x, y, mtx);
	if (y > mid) upd (u << 1 | 1, mid + 1, r, x, y, mtx);
	push_up (u);
}
inline matrix query (int u, int l, int r, int x, int y) {
	if (x <= l && r <= y) return sum[u];
	push_down (u, l, r);
	int mid = l + r >> 1;
	matrix ans;
	ans.n = 1, ans.m = 4;
	ans.a[1][1] = ans.a[1][2] = ans.a[1][3] = 0;
	ans.a[1][4] = 1;
	if (x <= mid) ans = ans + (matrix) (query (u << 1, l, mid, x, y));
	if (y > mid) ans = ans + (matrix) (query (u << 1 | 1, mid + 1, r, x, y));
	return ans;
}
signed main () {
	m1.n = m1.m = 4;
	m1.init ();
	m1.a[1][1] = m1.a[2][1] = m1.a[2][2] = m1.a[3][3] = m1.a[4][4] = 1;
	m2.n = m2.m = 4;
	m2.init ();
	m2.a[1][1] = m2.a[2][2] = m2.a[3][2] = m2.a[3][3] = m2.a[4][4] = 1;
	m3.n = m3.m = 4;
	m3.init ();
	m3.a[1][1] = m3.a[1][3] = m3.a[2][2] = m3.a[3][3] = m3.a[4][4] = 1;
	scanf ("%lld", &n);
	rep (i, 1, n) scanf ("%lld %lld %lld", &val[i][0], &val[i][1], &val[i][2]);
	build (1, 1, n);
	scanf ("%lld", &m);
	while (m --) {
		int op, l, r, v;
		scanf ("%lld %lld %lld", &op, &l, &r);
		if (op == 1) upd (1, 1, n, l, r, m1);
		else if (op == 2) upd (1, 1, n, l, r, m2);
		else if (op == 3) upd (1, 1, n, l, r, m3);
		else if (op == 4) {
			scanf ("%lld", &v);
			matrix mtx;
			mtx.n = mtx.m = 4;
			mtx.init ();
			mtx.a[1][1] = mtx.a[2][2] = mtx.a[3][3] = mtx.a[4][4] = 1;
			mtx.a[4][1] = v;
			upd (1, 1, n, l, r, mtx);
		}
		else if (op == 5) {
			scanf ("%lld", &v);
			matrix mtx;
			mtx.n = mtx.m = 4;
			mtx.init ();
			mtx.a[1][1] = mtx.a[3][3] = mtx.a[4][4] = 1;
			mtx.a[2][2] = v;
			upd (1, 1, n, l, r, mtx);
		}
		else if (op == 6) {
			scanf ("%lld", &v);
			matrix mtx;
			mtx.n = mtx.m = 4;
			mtx.init ();
			mtx.a[1][1] = mtx.a[2][2] = mtx.a[4][4] = 1;
			mtx.a[4][3] = v;
			upd (1, 1, n, l, r, mtx);
		}
		else if (op == 7) {
			matrix res = query (1, 1, n, l, r);
			printf ("%lld %lld %lld\n", res.a[1][1], res.a[1][2], res.a[1][3]);
		}
	}
	return 0;
}
2023/1/9 20:56
加载中...