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

【题目背景】

由于评测机差异，本题目于 COGS 上增加 1000ms 时限

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)}\quad (n\geq 1)$$

显然，对于操作 $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

【样例输入 #2】

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

【样例输出 #2】

0 998244352

998244352 0

【样例说明】

样例 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：
第一个 $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}$$ 对 $998244353$ 取模后得到对应输出。

【数据规模与约定】

对于所有测试数据，保证 $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$ 表示当前标号最大的元素的标号。

【提示】

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

【来源】

LibreOJ NOI Round #2