分数: 1000 点
问题陈述
我们有一个棋盘 H 行和 W 列,其中每个方格都有一个
上面写着 0 or 1 。
棋盘格的当前状态表示为 H 字符串 S_1,S_2,\cdots,S_H: j- 第一个字符 S_i 表示 i从顶部数第行和 j左起第 列。
Snuke 将重复以下操作。
- 随机均匀选择一个方格。
然后,翻转该方块中写入的值。 (换句话说,改变
0to1反之亦然。)
顺便说一句,他喜欢整数序列 A=(A_1,A_2,\cdots,A_H),所以当满足以下条件时他将终止进程。
- 对于每个 i (1 \leq i \leq H), i- 从顶部算起的第行恰好包含 A_i
1s。
特别地,他可以进行零操作。
求 Snuke 操作次数的期望值,取模 998244353.
期望值模的定义 998244353
可以证明,求的期望值始终是有理数。此外,在该问题的约束下,当该值表示为不可约分数时 \frac{P}{Q},还可以证明 Q \not \equiv 0 \pmod{998244353}。因此,唯一存在一个整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。找到这个 R.
约束
- 1 \leq H,W \leq 50
- S_i 是一个长度为的字符串 W 组成
0,1. - 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被翻转。的 1-st 行现在包含零1s,终止进程。 - 有概率 1/2,一个正方形
0被翻转。的 1-st 行现在包含两个1s,继续该过程。- 其中一个方块被翻转。无论翻转哪个方格, 1-st 行现在包含一个
1,继续该过程。- 有概率 1/2,一个正方形
1被翻转。的 1-st 行现在包含零1s,终止进程。 - 有概率 1/2,一个正方形
0被翻转。的 1-st 行现在包含两个1s,继续该过程。 - \vdots
- 有概率 1/2,一个正方形
- 其中一个方块被翻转。无论翻转哪个方格, 1-st 行现在包含一个
操作次数的预期值为 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