#P17696. Quo Vadis

Quo Vadis

题目描述

在小 M 离别之前,他给小 K 留了一张纸条——

如果你能完成他的话,我将有可能会再次与你相遇。

给定一个无限大的矩阵 AA,其中 Ai,j=ijgcd⁡(i,j)A_{i,j}=ij\gcd(i,j)。

接下来有 mm 个操作,每行 11 至 33 个整数,意义如下:

11:对矩阵 AA 进行高斯消元,使之成为一个上三角矩阵。

注意:这里,高斯消元中只允许将一行的某一个倍数加到另一行上,不允许交换任意两行,不允许将某行乘上一个倍数,保证这样之后仍然可以得到上三角矩阵,并且保证消元之后的矩阵的每个元素均为非负整数。

2 x y2\ x\ y:求出当前矩阵的 Ax,yA_{x,y}。

3 x3\ x:求出 ∑i=1x∑j=1xAi,j\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{x}A_{i,j}。

4 x4\ x:设 BB 是一个 xx 阶矩阵,其中 Bi,j=Ai,jB_{i,j}=A_{i,j},你需要求出 det⁡B\det B。

上述所有答案对 998244353998244353 取模。

如果你不知道什么是行列式,请点这里,其中 det\text{det} 表示求矩阵的行列式。

在你完成了小 M 给小 K 的任务之后,你可以来看小提琴和手风琴的谱子。

输入格式

第一行一个整数 mm。

接下来 mm 行,每行 1∼31\sim 3 个整数,表示操作。

输出格式

若干行,表示你的答案对 998244353998244353 取模后的值。

输入输出样例 #1

输入 #1

6
4 4
2 4 4
3 4
1
2 4 4
3 4

输出 #1

2304
64
186
32
72

说明/提示

【样例解释】

注意到询问的 xx 和 yy 范围都不大于 44,所以我们考虑使用 AA 左上角的 4×44\times 4 子矩阵进行解释,容易证明这不会造成任何影响。

在高斯消元之前,矩阵为 $\begin{pmatrix}1&2&3&4\\2&8&6&16\\3&6&27&12\\4&16&12&64\end{pmatrix}$,高斯消元后则为 $\begin{pmatrix}1&2&3&4\\0&4&0&8\\0&0&18&0\\0&0&0&32\end{pmatrix}$。


【数据范围】

子任务编号 11 操作是否存在 11 操作前 22 操作中 x,y≤x,y \leq 11 操作后 22 操作中 x,y≤x,y \leq 11 操作前 33 操作中 x≤x \leq 11 操作后 33 操作中 x≤x \leq 44 操作中 x≤x \leq 分值
Subtask 1 否 50005000 不存在 500500 不存在 不存在 44
Subtask 2 101810^{18} 1313
Subtask 3 5×1065 \times 10^6 5050 1515
Subtask 4 10810^8 100100 1616
Subtask 5 是 100100 5×1065 \times 10^6 100100 不存在 1717
Subtask 6 5×1055\times 10^5 10810^8 10310^3 100100
Subtask 7 5×1065 \times 10^6 5×1065\times 10^6 1818

对于 100%100\% 的数据,1≤m≤1051 \leq m\leq 10^5,11 操作前的所有 33 操作中 ∑x\sum x 不大于每一个测试点 xx 范围的 1010 倍。

保证 11 操作出现不超过 11 次。