#573. 「LibreOJ NOI Round #2」单枪匹马

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cz_xuyixuan

题目描述

It's funny, the day you lose someone isn't the worst.
At least you've got something to do.
It's the days they stay gone.

小 X 是一位 X 国的附魔师。

自从那场战争爆发到现在,小 X 已经整整一年没有回到 X 国了。战事不断恶化,小 X 与 X 国的故人的联系也如风中残烛一般时断时续。但小 X 却连缅怀过去的时间都没有,肩负着责任的他只能日复一日地战斗着……

今天,小 X 需要进行一场炼金实验。

小 X 面前有 N 种元素,它们的标号分别为 1,2,\dots,N ,每一种元素 i 都有一个对应的正整数 a_i ,表示它的魔法强度。每个时刻,小 X 会执行如下操作中的一种:

  • 1 :发现一种魔法强度为 x 的新的元素,将其标号为 Max+1 ,其中 Max 表示当前标号最大的元素的标号。

  • 2 :对标号在区间 [l,r] 内的元素进行一次实验,计算它们生成的法术的威力值 f(a_l,a_{l+1},\dots,a_r)

其中 f(x)=x,f(a_0,a_1,a_2,\dots,a_n)=a_0+\frac{1}{f(a_1,a_2,\dots,a_n)}\ (n\geq1)

显然,对于操作 2 ,小 X 所操作的 f(a_l,a_{l+1},\dots,a_r) 一定可以唯一地写为最简分数 \frac{x}{y} 的形式,你需要告诉小 X 的是 x y 分别对 998244353 取模的值。

输入格式

从标准输入读入数据。

第一行三个整数 N,M,Type ,分别表示初始时元素的种类数,操作的个数,以及强制在线参数。

接下来一行 N 个正整数 a_i ,描述初始时各种元素的魔法强度。

接下来 M 行,每行第一个整数 opt ,表示当前操作类型。

对于 opt=1 的操作,接下来输入一个正整数 x ,表示新发现的元素的魔法强度。

对于 opt=2 的操作,接下来输入两个整数 l,r ,表示计算 f(a_l,a_{l+1},\dots,a_r)

特别地,对于 Type=1 的数据,令上一次 opt=2 的操作的答案为 Ansx,Ansy ,所有除 opt 以外的输入数据均需要异或上 Ansx\oplus Ansy ,其中 \oplus 表示二进制下按位异或。规定:在第一次 opt=2 的操作之前, Ansx=0, Ansy=0

输出格式

输出到标准输出。

对于所有 opt=2 的操作,输出一行两个整数 Ansx,Ansy ,分别表示 f(a_l,a_{l+1},\dots,a_r) 最简分数的分子和分母对 998244353 取模的结果。

样例

样例输入 1

2 3 0
3 4
2 1 2
1 7
2 2 3

样例输出 1

13 4
29 7

样例说明 1

对于第一个 opt=2 的操作, f(3,4)=3+\frac{1}{4}=\frac{13}{4}

对于第二个 opt=2 的操作, f(4,7)=4+\frac{1}{7}=\frac{29}{7}

样例输入 2

3 2 0
1 1 998244352
2 2 3
2 1 3

样例输出 2

0 998244352
998244352 0

样例说明 2

对于第一个 opt=2 的操作, f(1,998244352)=1+\frac{1}{998244352}=\frac{998244353}{998244352}

对于第二个 opt=2 的操作, f(1,1,998244352)=1+\frac{998244352}{998244353}=\frac{1996488705}{998244353}

样例 3

见下发文件。

数据范围与提示

数据范围

对于所有测试数据,保证 1 \leq N,M \leq 5\times10^5 Type\in\{0,1\},opt\in\{1,2\} 1\leq a_i\leq 998244352

对于 opt=1 的操作,保证解密后满足 1\leq x\leq 998244352

对于 opt=2 的操作,保证解密后满足 1\leq l\leq r\leq Max ,其中 Max 表示当前标号最大的元素的标号。

详细的数据范围见下表。

测试点编号 Type N M 特殊性质
1 =0 \leq 5 \leq 10 a_i,x\leq50,opt=2
2 \leq 50 \leq 100
3 a_i,x\leq50
4
5 \leq 2\times 10^3 \leq 3\times 10^3
6
7
8 \leq 5\times 10^4 \leq 10^5
9
10
11 \leq 5\times 10^5 \leq 5\times 10^5
12
13 =1 \leq 10^5 l=1
14
15 \leq 5\times 10^5
16
17 \leq 10^5
18
19 \leq 5\times 10^5
20

提示

当你做完这题,向 NOI 发起冲刺的时候,不妨回头看看你抛下的一切吧。