记录编号	617809	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4438.「LibreOJ NOI Round #2」单枪匹马	最终得分	100
用户昵称	zcx	是否通过	通过
代码语言	C++	运行时间	8.880 s
提交时间	2026-08-03 19:29:07	内存使用	217.32 MiB

#include<bits/stdc++.h>
#define M ((L + R)>>1)
#define lson p * 2
#define rson p * 2 + 1
#define int long long
using namespace std;
const int N = 1e6 + 5;
const int mod = 998244353;

struct Mat{
	int a[2][2];
	Mat(){ memset(a,0,sizeof(a));}
};

struct tree{
	int l,r;
	Mat b;
} tr[N<<2]; 


int n,m,t;

Mat d[N];

Mat Mul(Mat x,Mat y){
	Mat res;
	for(int i = 0;i < 2;i++)
		for(int j = 0;j < 2;j++)
			for(int k = 0;k < 2;k++) res.a[i][j] = (res.a[i][j] + x.a[i][k] * y.a[k][j]) % mod;
	return res;
}

void build(int p,int L,int R){
	tr[p].l = L;tr[p].r = R;
	if(L == R){
		tr[p].b = d[L];
		return ;
	}
	build(lson,L,M);build(rson,M + 1,R);
	tr[p].b = Mul(tr[rson].b,tr[lson].b);
}

void add(int p, int x,int k){
	if(tr[p].l == tr[p].r){
		tr[p].b = d[tr[p].l];
		return ;
	}
	if(x <= tr[lson].r) add(lson,x,k);
	else add(rson,x,k);
	tr[p].b = Mul(tr[rson].b,tr[lson].b);
}

Mat que(int p,int x,int y){
	if(tr[p].l >= x && tr[p].r <= y) return tr[p].b;
	int mid = tr[lson].r;
	if(y <= mid) return que(lson,x,y);
	else if(x > mid) return que(rson,x,y);
	else{
		Mat res1 = que(lson,x,y);
		Mat res2 = que(rson,x,y);
		return Mul(res2,res1);
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	freopen("single_noi.in","r",stdin);
	freopen("single_noi.out","w",stdout);
	
	cin>>n>>m>>t;
	for(int i = 1;i <= n;i++){
		cin>>d[i].a[1][1];d[i].a[1][1] %= mod;
		d[i].a[0][1] = d[i].a[1][0] = 1;
	}
	
	build(1,1,n + m);
	
	int ansx = 0,ansy = 0;
	while(m--){
		int opt;cin>>opt;
		if(opt == 1){
			int x;cin>>x;
			if(t == 1) x ^= ansx ^ ansy;
			d[++n].a[1][1] = x % mod;
			d[n].a[0][1] = d[n].a[1][0] = 1;
			add(1,n,x);
		}else{
			int x,y;cin>>x>>y;
			if(t == 1) x ^= ansx ^ ansy,y ^= ansx ^ ansy;
			if(x > y) swap(x,y);
			if(x == y){
				cout<<d[x].a[1][1]<<" "<<1<<'\n';
				ansx = d[x].a[1][1],ansy = 1;
				continue;
			}
			Mat res;res.a[0][0] = 1,res.a[0][1] = d[y].a[1][1];
			
			Mat base = que(1,x,y - 1);
			
			res = Mul(res,base);
			
			ansx = res.a[0][1],ansy = res.a[0][0];
			
			cout<<ansx<<" "<<ansy<<'\n';
		}
	}
	
	return 0;
}