← 返回题目列表

AtCoder · arc190_c

C. 更新的基本网格问题

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

分数: 800 点

问题陈述

有一个 H \times W 网格。让 (h,w) 表示位于 h从顶部算起的第行和 w左起第 列。非负整数 A_{h,w} 写入单元格 (h,w).

高桥从牢房开始 (sh,sw) 并将执行 Q 更改为网格。的 i-th 更改由字符给出 d_i (d_i 是其中之一 L, R, U, D) 和一个非负整数 a_i,意味着高桥将执行以下操作:

  • 朝 方向移动一个单元格 d_i。也就是说,如果 d_i is L,向左移动;如果 R,向右移动;如果 U,向上移动;如果 D,向下移动一个单元格。然后,让目标单元格为 (h,w),并设置 A_{h,w} to a_i.

保证在每次改变时,他可以向方向移动一个单元格 d_i.

每次更改后,打印以下问题的答案:

一系列细胞 P = ((h_1,w_1), \ldots, (h_{M},w_{M})) 据说是 路径 当且仅当满足以下所有条件时:

  • (h_1,w_1) = (1,1), (h_{M},w_{M}) = (H,W),和 M = H + W - 1.
  • 对于每个 i 与 1 \leq i \leq M-1,或者 (h_{i+1}, w_{i+1}) = (h_i + 1, w_i) or (h_{i+1}, w_{i+1}) = (h_i, w_i + 1).

有 \binom{H+W-2}{H-1} 路径。对于一条路径 P = ((h_1,w_1), \ldots, (h_{M},w_{M})),定义 f(P) = \prod_{1\leq i\leq M}A_{h_i,w_i}。打印总和,模数 998244353,属于 f(P) 在所有路径上 P.

约束

  • 2 \leq H, W \leq 200000
  • HW \leq 200000
  • 0 \leq A_{h,w} < 998244353
  • 1 \leq Q \leq 200000
  • 1 \leq sh \leq H, 1 \leq sw \leq W
  • 0 \leq a_i < 998244353
  • H, W, A_{h,w}, Q, sh, sw,和 a_i 是整数。
  • 每个 d_i is L, R, U,或 D.
  • 在每次变化中,高桥可以朝以下方向移动一个单元格 d_i.

输入

输入由标准输入按以下格式给出:

H W
A_{1,1} \cdots A_{1,W}
\vdots
A_{H,1} \cdots A_{H,W}
Q sh sw
d_1 a_1
\vdots
d_Q a_Q

输出

打印 Q 行。

的 i- 第行应包含求和、模数 998244353,属于 f(P) 在所有路径上 P 执行后 i- 对网格的更改。


示例输入 1

2 3
1 2 3
4 5 6
3 2 2
U 7
R 8
L 9

示例输出 1

456
666
822
  • 最初,高桥位于 (2,2).
  • 向上移动,然后设置 A_{1,2} to 7。的价值 每个路径的 f(P) 是:
    • P=((1,1),(1,2),(1,3),(2,3)): f(P)=1 \times 7 \times 3 \times 6=126.
    • P=((1,1),(1,2),(2,2),(2,3)): f(P)=1 \times 7 \times 5 \times 6=210.
    • P=((1,1),(2,1),(2,2),(2,3)): f(P)=1 \times 4 \times 5 \times 6=120.
  • 向右移动,然后设置 A_{1,3} to 8。的价值 每个路径的 f(P) 是:
    • P=((1,1),(1,2),(1,3),(2,3)): f(P)=1 \times 7 \times 8 \times 6=336.
    • P=((1,1),(1,2),(2,2),(2,3)): f(P)=1 \times 7 \times 5 \times 6=210.
    • P=((1,1),(2,1),(2,2),(2,3)): f(P)=1 \times 4 \times 5 \times 6=120.
  • 向左移动,然后设置 A_{1,2} to 9。的价值 每个路径的 f(P) 是:
    • P=((1,1),(1,2),(1,3),(2,3)): f(P)=1 \times 9 \times 8 \times 6=432.
    • P=((1,1),(1,2),(2,2),(2,3)): f(P)=1 \times 9 \times 5 \times 6=270.
    • P=((1,1),(2,1),(2,2),(2,3)): f(P)=1 \times 4 \times 5 \times 6=120.

示例输入 2

5 4
147015809 294958521 852121867 499798308
790350368 404692331 645419803 290531806
275766153 896286651 239187926 945049742
340760022 236352314 926236110 223464913
287023679 590772036 340282357 521075891
6 3 1
U 344644511
R 45812235
D 260083498
R 781118585
L 156297846
L 411901560

示例输出 2

299123226
548055393
810247224
876210800
773990840
506814544