分数: 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,其中每个字符是
0or1 - 0 \leq C_t \leq K (1 \leq t \leq N)
- A_i, B_i, X_i 是每个长度的字符串 K,其中每个字符是
0or1(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