← 返回题目列表

AtCoder · oupc2023_day1_q

Q. 库库鲁

中文机器翻译题面 查看原题

配点 : 100 点

問題文

在这个问题中使用以下的数学表达式。

  • (i,j) : 2 从多维数组的上方 i+1 第几行,从左边 j+1 列的位置
  • A_{i,j} : 2 次元配列 A 从上方 i+1 第几行,从左边 j+1 列的值
  • p \bmod q :非负整数 p 除以正整数 q 的余数

N \times N 的 2 对于维度数组 M 个操作被给定。每个操作由整数 t 和若干个整数表示,t 的值决定,(i,j) (0 \leq i,j < N) 对以下操作同时进行。

  • t = 1 时,(i, j) 中的数字被 ((i x + a) \bmod N, (j y + b) \bmod N) 移动。不过 x 和 N、 y 和 N 保证彼此互质,因此每个数字的移动目标不会重复。
  • t = 2 时,(i, j) 中的数字被 (j, i) 移动到。

Q 个查询被给定。每个查询由 L,R,c,d,e,f 的 6 个整数构成。分别 A_{i,j} = i N + j 为 N \times N 的 2 次元配列 A 反对 L, L + 1, \dots , R 第几次操作按顺序进行,操作后 2 次元配列 A' 计算每个 \sum\limits_{i = c}^{d} \sum\limits_{j=e}^{f} A_{i, j}' 的 998244353 求余数。

制約

  • 2 \leq N \leq 10^{9}
  • 1 \leq M \leq 200{,}000
  • 1 \leq Q \leq 200{,}000
  • 1 \leq x < N
  • 1 \leq y < N
  • x 和 N, y 和 N 彼此互质
  • 0 \leq a < N
  • 0 \leq b < N
  • 1 \leq L \leq R \leq M
  • 0 \leq c \leq d < N
  • 0 \leq e \leq f < N
  • 所有输入均为整数

小課題

  1. (1 点) N\leq 10
  2. (99 点)没有额外的否定

入力

输入是按以下格式从标准输入给出的。

N M Q
\mathrm{Operation}_1
\mathrm{Operation}_2
\vdots
\mathrm{Operation}_M
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q

各操作 (\mathrm{Operation}) 如下所示 2 这是其中一种形式。

1 x y a b
2

每个查询 (\mathrm{Query}) 的格式如下。

L R c d e f

出力

Q 请逐行输出。 i 行中, i 输出第 n 个查询的答案。


入力例 1

3 5 2
1 1 1 2 1
1 2 1 0 2
2
1 1 2 1 0
2
2 3 0 1 1 2
1 5 0 2 0 2

出力例 1

24
36

1 在第 n 个查询中,2 从第 x 个 3 到第 y 个应用操作。 操作之前的 2 维度数组是 A=\begin{pmatrix} 0 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{pmatrix} 。 2 施加第 n 个操作后,\begin{pmatrix} 1 & 2 & 0 \\ 7 & 8 & 6 \\ 4 & 5 & 3 \end{pmatrix} 将会变为。 此外, 3 施加第 n 个操作后,\begin{pmatrix} 1 & 7 & 4 \\ 2 & 8 & 5 \\ 0 & 6 & 3 \end{pmatrix} 。 A' = \begin{pmatrix} 1 & 7 & 4 \\ 2 & 8 & 5 \\ 0 & 6 & 3 \end{pmatrix} 当设置为 \sum\limits_{i=0}^1 \sum\limits_{j=1}^2 A'_{i,j} = 7+4+8+5 = 24 。

2 第 n 个查询, 1 从第 x 个 5 将会应用到第 m 个操作为止。应用所有操作后,A' = \begin{pmatrix} 5 & 3 & 4 \\ 8 & 6 & 7 \\ 2 & 0 & 1 \end{pmatrix} 将会变为,但当然所有元素的和与操作前相等 36 。

这个测试用例满足小课题1的否定条件。


入力例 2

999999937 8 3
1 314159265 358979323 846264338 327950288
1 419716939 937510582 97494459 230781640
2
1 628620899 862803482 534211706 798214808
1 651328230 664709384 460955058 223172535
1 940812848 111745028 410270193 852110555
2
1 964462294 895493038 196442881 97566593
3 3 344612847 564823378 67831652 712019091
3 7 45648566 923460348 610454326 648213393
1 8 60726024 914127372 458700660 631558817

出力例 2

511746849
453803153
685820807

这个测试用例不满足小课题1的否定条件。