D - Control Panel Operation Sequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、K 個のランプが一列に並んだ制御パネルに対して、N 種類の操作を 1 日に 1 種類ずつ、合計 N 日間かけてすべて実行しました。

それぞれの操作はちょうど 1 回だけ実行されましたが、どの順序で実行されたかは分からなくなりました。

各ランプは「点灯」または「消灯」のどちらかの状態をとります。

パネルの状態は長さ K の 0/1 文字列で表され、j 文字目（1 \leq j \leq K）の 1 はランプ j の点灯を、0 は消灯を表します。

パネルの初期状態は文字列 S で与えられます。

操作 i（1 \leq i \leq N）には、長さ K の 0/1 文字列 A_i, B_i, X_i が定められています。

実行条件： 操作 i を実行できるのは、すべての j（1 \leq j \leq K）について以下の条件をすべて満たすときに限ります。

  • A_i の j 文字目が 1 のとき、ランプ j が点灯していなければならない。
  • B_i の j 文字目が 1 のとき、ランプ j が消灯していなければならない。

A_i の j 文字目と B_i の j 文字目がともに 0 のとき、ランプ j の状態は問いません。

一方、A_i の j 文字目と B_i の j 文字目がともに 1 であることもありえます。その場合、ランプ j が点灯かつ消灯でなければならず、どのようなパネル状態でもこの条件を満たせないため、操作 i はいかなる状況でも実行できません。

効果： 操作 i を実行すると、各 j（1 \leq j \leq K）について、

  • X_i の j 文字目が 1 であるとき、ランプ j の点灯・消灯が反転する。
  • X_i の j 文字目が 0 であるとき、ランプ j は変化しない。

青木君は、各日の操作後に点灯しているランプの個数だけを記録していました。

記録の初期値として、t 日目（1 \leq t \leq N）の操作後に点灯しているランプの個数 C_t が与えられます。

この記録には後から Q 回の訂正が入ります。

q 回目（1 \leq q \leq Q）の訂正では、その時点での記録のうち T_q 日目の値を Y_q に変更します。それまでの訂正による変更はすべて保持されたまま、新たな訂正が上書き適用されます。

各訂正の直後について、その時点での記録と矛盾しない操作の実行順序の個数を 998244353 で割った余りを求めてください。

ここで、操作の実行順序とは (1, 2, \ldots, N) の順列 (p_1, p_2, \ldots, p_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 または 1 である
  • 0 \leq C_t \leq K（1 \leq t \leq N）
  • A_i, B_i, X_i はそれぞれ長さ K の文字列であり、各文字は 0 または 1 である（1 \leq i \leq N）
  • A_i の j 文字目と B_i の j 文字目がともに 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
  • 1 行目には、操作の種類数 N、ランプの個数 K、訂正の回数 Q が、スペース区切りで与えられる。
  • 2 行目には、パネルの初期状態を表す長さ K の 0/1 文字列 S が与えられる。
  • 3 行目には、記録の初期値を表す整数列 C_1, C_2, \ldots, C_N が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目には、操作 i の実行条件と効果を表す長さ K の 0/1 文字列 A_i, B_i, X_i が、スペース区切りで与えられる。
  • 続く Q 行のうち q 行目には、q 回目の訂正を表す整数 T_q, Y_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

Score : 400 pts

Problem Statement

Takahashi performed N types of operations on a control panel with K lamps arranged in a row, executing one type per day over a total of N days.

Each operation was executed exactly once, but the order in which they were executed has been lost.

Each lamp is in one of two states: "on" or "off".

The state of the panel is represented by a 0/1 string of length K, where the j-th character (1 \leq j \leq K) being 1 indicates that lamp j is on, and 0 indicates it is off.

The initial state of the panel is given by the string S.

For operation i (1 \leq i \leq N), three 0/1 strings of length K: A_i, B_i, X_i are defined.

Execution condition: Operation i can be executed only when the following conditions are all satisfied for every j (1 \leq j \leq K):

  • If the j-th character of A_i is 1, then lamp j must be on.
  • If the j-th character of B_i is 1, then lamp j must be off.

When both the j-th character of A_i and the j-th character of B_i are 0, the state of lamp j does not matter.

On the other hand, it is possible that both the j-th character of A_i and the j-th character of B_i are 1. In that case, lamp j must be both on and off simultaneously, which cannot be satisfied by any panel state, so operation i can never be executed under any circumstances.

Effect: When operation i is executed, for each j (1 \leq j \leq K):

  • If the j-th character of X_i is 1, the on/off state of lamp j is toggled.
  • If the j-th character of X_i is 0, lamp j does not change.

Aoki recorded only the number of lamps that are on after the operation on each day.

As the initial record, the number of lamps on after the operation on day t (1 \leq t \leq N), C_t, is given.

This record is subject to Q corrections afterwards.

In the q-th correction (1 \leq q \leq Q), the value for day T_q in the current record is changed to Y_q. All changes from previous corrections are retained, and the new correction is applied as an overwrite.

After each correction, find the number of operation execution orders that are consistent with the record at that point, modulo 998244353.

Here, an operation execution order is a permutation (p_1, p_2, \ldots, p_N) of (1, 2, \ldots, N), and a permutation is consistent with the record if and only if all of the following are satisfied:

  • The initial state of the panel is S.
  • On day t (t = 1, 2, \ldots, N), operation p_t is executed.
  • The panel state immediately before executing operation p_t satisfies the execution condition of operation p_t.
  • The number of lamps on after the operation on day t equals C_t in the record.

Note that different permutations of operation numbers are counted as different execution orders, even if they only swap operations with identical conditions and effects.

Constraints

  • 1 \leq N \leq 9
  • 1 \leq K \leq 9
  • 1 \leq Q \leq 10^5
  • S is a string of length K, where each character is 0 or 1
  • 0 \leq C_t \leq K (1 \leq t \leq N)
  • A_i, B_i, X_i are each strings of length K, where each character is 0 or 1 (1 \leq i \leq N)
  • It is possible that both the j-th character of A_i and the j-th character of B_i are 1
  • 1 \leq T_q \leq N (1 \leq q \leq Q)
  • 0 \leq Y_q \leq K (1 \leq q \leq Q)
  • All inputs are integers or strings in the specified format

Input

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
  • The first line contains the number of operation types N, the number of lamps K, and the number of corrections Q, separated by spaces.
  • The second line contains a 0/1 string S of length K representing the initial state of the panel.
  • The third line contains the integers C_1, C_2, \ldots, C_N representing the initial record values, separated by spaces.
  • The following N lines, where the i-th line contains the 0/1 strings A_i, B_i, X_i of length K representing the execution condition and effect of operation i, separated by spaces.
  • The following Q lines, where the q-th line contains integers T_q, Y_q representing the q-th correction, separated by spaces. This means the value for day T_q in the current record is changed to Y_q.

Output

Output Q lines.

On the q-th line, output the number of operation execution orders consistent with the record immediately after the q-th correction, modulo 998244353.

Sample Input 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

Sample Output 1

0
1
0
1

Sample Input 2

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

Sample Output 2

0
0
0

Sample Input 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

Sample Output 3

0
0
0
0
0
0
0
0

Sample Input 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

Sample Output 4

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

Sample Input 5

1 1 1
0
0
0 0 1
1 1

Sample Output 5

1