← 返回题目列表

AtCoder · awc0088_d

D. 控制面板操作顺序

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

分数: 400 分

问题陈述

高桥表演 N 控制面板上的操作类型 K 灯排成一排,每天执行一种类型,总共超过 N 天。

每个操作只执行一次,但执行顺序已丢失。

每个灯都处于两种状态之一:“开”或“关”。

面板的状态由 0/1 长度的字符串 K,其中 j- 第一个字符 (1 \leq j \leq K) 是 1 表示该灯 j 已打开,并且 0 表示已关闭。

面板的初始状态由字符串给出 S.

用于操作 i (1 \leq i \leq N),三个 0/1 长度的字符串 K: A_i, B_i, X_i 已定义。

执行条件: 操作 i 只有当每个条件都满足以下条件时才能执行 j (1 \leq j \leq K):

  • 如果 j- 第一个字符 A_i is 1,然后灯 j 必须打开。
  • 如果 j- 第一个字符 B_i is 1,然后灯 j 必须关闭。

当两个 j- 第一个字符 A_i 和 j- 第一个字符 B_i 是 0,灯的状态 j 没关系。

另一方面,有可能 j- 第一个字符 A_i 和 j- 第一个字符 B_i 是 1。在这种情况下,灯 j 必须同时亮和灭,任何面板状态都不能满足,所以操作 i 在任何情况下都不能被执行。

效果: 操作时 i 被执行,对于每个 j (1 \leq j \leq K):

  • 如果 j- 第一个字符 X_i is 1,灯的开/关状态 j 已切换。
  • 如果 j- 第一个字符 X_i is 0,灯 j 不变。

青木仅记录每天手术后打开的灯的数量。

作为初始记录,当天运行后亮灯数 给出了 t (1 \leq t \leq N), C_t。

该记录受 Q 事后更正。

在 q-第更正(1 \leq q \leq Q),天的值 当前记录中的 T_q 更改为 Y_q。先前更正的所有更改均会保留,并且新的更正将作为覆盖应用。

每次修正后,求出与该点记录一致的操作执行指令数,取模 998244353.

这里,操作执行顺序是一个排列 (p_1, p_2, \ldots, p_N) of (1, 2, \ldots, N),当且仅当满足以下所有条件时,排列与记录一致:

  • 面板的初始状态是 S.
  • 当天 t (t = 1, 2, \ldots, N),操作 p_t 被执行。
  • 执行操作前的面板状态 p_t 满足操作的执行条件 p_t.
  • 当天运行后亮灯数量 t 等于 记录中的 C_t 。

请注意,操作编号的不同排列被视为不同的执行顺序,即使它们仅交换具有相同条件和效果的操作。

约束

  • 1 \leq N \leq 9
  • 1 \leq K \leq 9
  • 1 \leq Q \leq 10^5
  • S 是一个长度为的字符串 K,其中每个字符是 0 or 1
  • 0 \leq C_t \leq K (1 \leq t \leq N)
  • A_i, B_i, X_i 是每个长度的字符串 K,其中每个字符是 0 or 1 (1 \leq i \leq N)
  • 两者都有可能 j- 第一个字符 A_i 和 j- 第一个字符 B_i 是 1
  • 1 \leq T_q \leq N (1 \leq q \leq Q)
  • 0 \leq Y_q \leq K (1 \leq q \leq Q)
  • 所有输入都是指定格式的整数或字符串

输入

N K Q
S
C_1 C_2 \ldots C_N
A_1 B_1 X_1
A_2 B_2 X_2
\vdots
A_N B_N X_N
T_1 Y_1
T_2 Y_2
\vdots
T_Q Y_Q
  • 第一行包含操作类型的数量 N,灯数量 K,以及更正次数 Q,用空格分隔。
  • 第二行包含 0/1 字符串 S 长度 K 代表面板的初始状态。
  • 第三行包含整数 C_1, C_2, \ldots, C_N 表示初始记录值,以空格分隔。
  • 以下 N 行,其中 i第行包含 0/1 字符串 A_i, B_i, X_i 长度 K 表示操作的执行条件和效果 i,用空格分隔。
  • 以下 Q 行,其中 q- 第行包含整数 T_q, Y_q 代表 q第更正,以空格分隔。这意味着一天的价值 T_q 更改为 Y_q.

输出

输出 Q 行。

关于 q第行,输出与紧随其后的记录一致的操作执行命令数 q-次校正,模数 998244353.


示例输入 1

3 3 4
010
2 1 2
010 000 100
100 000 001
000 001 010
2 3
2 1
1 0
1 2

示例输出 1

0
1
0
1

示例输入 2

2 2 3
00
1 2
00 00 10
10 10 01
2 1
1 0
2 0

示例输出 2

0
0
0

示例输入 3

6 5 8
10100
3 2 3 4 3 2
10000 00010 01001
00100 00000 10010
00000 01000 00101
01001 10000 00011
00010 00100 11000
00000 00001 01110
3 4
6 1
1 2
4 5
5 0
2 3
3 2
6 2

示例输出 3

0
0
0
0
0
0
0
0

示例输入 4

9 9 12
101011001
5 4 6 5 3 4 5 4 6
100000001 000100000 010010000
000010000 001000000 100000100
010000000 000000010 001001000
000000100 100000000 000110001
001000010 000010000 010000011
000100000 000001000 101000000
000000000 010000001 000001110
100010000 000000100 001000101
000001001 001000000 110000010
1 4
9 5
5 6
3 3
7 7
2 2
8 4
4 1
6 5
1 5
9 0
5 3

示例输出 4

0
0
0
0
0
0
0
0
0
0
0
0

示例输入 5

1 1 1
0
0
0 0 1
1 1

示例输出 5

1