/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
H 行 W 列からなる盤面があり，各マスには 0 か 1 が書き込まれています．
盤面の状態は H 個の文字列 S_1,S_2,\cdots,S_H で表され，
S_i の j 文字目が，上から i 行目，左から j 列目のマスに書かれている数字を表します．
すぬけくんはこれから，次の操作を繰り返します．
- 一つのマス目を一様ランダムに選ぶ．
そして，そのマス目に書かれている値を flip する．（つまり，
0ならば1に変え，1ならば0に変える）
ところで，すぬけ君は整数列 A=(A_1,A_2,\cdots,A_H) が大好きです． そのため，以下の条件が満たされた瞬間，操作を終了します．
- すべての i (1 \leq i \leq H) について，i 行目にある
1の個数がちょうど A_i である．
特に，操作を 0 回しか行わないこともありえます．
すぬけくんが行う操作回数の期待値を \text{mod }{998244353} で求めてください．
期待値 \text{mod }{998244353} の定義
求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not \equiv 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。
制約
- 1 \leq H,W \leq 50
- S_i は
0,1からなる長さ W の文字列 - 0 \leq A_i \leq W
入力
入力は以下の形式で標準入力から与えられる．
H W S_1 S_2 \vdots S_H A_1 A_2 \cdots A_H
出力
答えを出力せよ．
入力例 1
1 2 01 0
出力例 1
3
操作の様子は以下のようになります．
- 確率 1/2 で
1の書かれたマスを flip する．1 行目にある1の個数が 0 になり，操作が終了する． - 確率 1/2 で
0の書かれたマスを flip する．1 行目にある1の個数は 2 になり，操作は継続する．- いずれかのマスを flip する．flip したマスに依らず，1 行目にある
1の個数は 1 になり，操作は継続する．- 確率 1/2 で
1の書かれたマスを flip する．1 行目にある1の個数が 0 になり，操作が終了する． - 確率 1/2 で
0の書かれたマスを flip する．1 行目にある1の個数は 2 になり，操作は継続する． - \vdots
- 確率 1/2 で
- いずれかのマスを flip する．flip したマスに依らず，1 行目にある
操作回数の期待値は 3 になります．
入力例 2
3 3 000 100 110 0 1 2
出力例 2
0
入力例 3
2 2 00 01 1 0
出力例 3
332748127
入力例 4
5 4 1101 0000 0010 0100 1111 1 3 3 2 1
出力例 4
647836743
Score : 1000 points
Problem Statement
We have a checkerboard with H rows and W columns, where each square has a 0 or 1 written on it.
The current state of checkerboard is represented by H strings S_1,S_2,\cdots,S_H: the j-th character of S_i represents the digit in the square at the i-th row from the top and j-th column from the left.
Snuke will repeat the following operation.
- Choose one square uniformly at random.
Then, flip the value written in that square. (In other words, change
0to1and vice versa.)
By the way, he loves an integer sequence A=(A_1,A_2,\cdots,A_H), so he will terminate the process at the moment when the following condition is satisfied.
- For every i (1 \leq i \leq H), the i-th row from the top contains exactly A_i
1s.
Particularly, he may do zero operations.
Find the expected value of the number of operations Snuke does, modulo 998244353.
Definition of the expected value modulo 998244353
It can be proved that the sought expected value is always a rational number. Additionally, under the Constraints of this problem, when that value is represented as an irreducible fraction \frac{P}{Q}, it can also be proved that Q \not \equiv 0 \pmod{998244353}. Thus, there uniquely exists an integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Find this R.
Constraints
- 1 \leq H,W \leq 50
- S_i is a string of length W consisting of
0,1. - 0 \leq A_i \leq W
Input
Input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H A_1 A_2 \cdots A_H
Output
Print the answer.
Sample Input 1
1 2 01 0
Sample Output 1
3
The process goes as follows.
- With probability 1/2, a square with
1is flipped. The 1-st row now contains zero1s, terminating the process. - With probability 1/2, a square with
0is flipped. The 1-st row now contains two1s, continuing the process.- One of the squares is flipped. Regardless of which square is flipped, the 1-st row now contains one
1, continuing the process.- With probability 1/2, a square with
1is flipped. The 1-st row now contains zero1s, terminating the process. - With probability 1/2, a square with
0is flipped. The 1-st row now contains two1s, continuing the process. - \vdots
- With probability 1/2, a square with
- One of the squares is flipped. Regardless of which square is flipped, the 1-st row now contains one
The expected value of the number of operations is 3.
Sample Input 2
3 3 000 100 110 0 1 2
Sample Output 2
0
Sample Input 3
2 2 00 01 1 0
Sample Output 3
332748127
Sample Input 4
5 4 1101 0000 0010 0100 1111 1 3 3 2 1
Sample Output 4
647836743