201365: [AtCoder]ARC136 F - Flip Cells

Memory Limit：1024 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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 0 to 1 and 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 1 is flipped. The $1$-st row now contains zero 1s, terminating the process.
  • With probability $1/2$, a square with 0 is flipped. The $1$-st row now contains two 1s, 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 1 is flipped. The $1$-st row now contains zero 1s, terminating the process.
      • With probability $1/2$, a square with 0 is flipped. The $1$-st row now contains two 1s, continuing the process.
      • $\vdots$

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

Input

题意翻译

有一个 $h$ 行 $w$ 列的棋盘，每个格子内都有一个为 $0$ 或 $1$ 的数字。棋盘的初始状态由 $h$ 个长为 $w$ 的只包含 `0` 和 `1` 的字符串 $S_1, S_2, \dots, S_n$ 给定，$S_i$ 的第 $j$ 个字符表示棋盘上从上往下第 $i$ 行、从左往右第 $j$ 列的数字。 给定长为 $h$ 的序列 $a = (a_1, a_2, \dots, a_n)$，Sunke 会重复以下的操作直到对所有 $i$ 有从上往下第 $i$ 行中 $1$ 的数量恰为 $a_i$。 - 随机选择一个格子，翻转该格子中的数（$1$ 变为 $0$，$0$ 变为 $1$）。 请求出 Snuke 执行操作次数的期望在模 $998244353$ 意义下的值。

Source/Category

加入题单

算法标签：