← 返回题目列表

AtCoder · arc136_f

F. 翻转细胞

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

我们有一个棋盘 H 行和 W 列,其中每个方格都有一个 上面写着 0 or 1 。 棋盘格的当前状态表示为 H 字符串 S_1,S_2,\cdots,S_H: j- 第一个字符 S_i 表示 i从顶部数第行和 j左起第 列。

Snuke 将重复以下操作。

  • 随机均匀选择一个方格。 然后,翻转该方块中写入的值。 (换句话说,改变 0 to 1 反之亦然。)

顺便说一句,他喜欢整数序列 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

操作次数的预期值为 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