CF2070F Friends and Pizza

Monocarp 有 $n$ 个披萨，第 $i$ 个披萨包含 $a_i$ 片。披萨用从 A 开始的拉丁字母大写字符表示（第 $n$ 个披萨对应第 $n$ 个拉丁字母）。 Monocarp 还有 $m$ 个朋友，他想要邀请其中恰好两人来吃披萨。对于每个朋友，Monocarp 知道该朋友喜欢哪些披萨。 当朋友到达 Monocarp 家后，每个披萨的处理方式如下： - 如果该披萨不被任何被邀请的朋友喜欢，Monocarp 将吃掉它； - 如果该披萨恰好被一位被邀请的朋友喜欢，该朋友将吃掉它； - 如果该披萨被两位朋友都喜欢，他们将尝试分食。若披萨包含偶数片，两人各吃一半；若包含奇数片，他们会因争夺额外一片而发生争吵——Monocarp 不喜欢这种情况。 对于每个 $k$ 从 $0$ 到 $\sum a_i$，计算选择两个朋友的方式数，使得朋友不会争吵且 Monocarp 恰好吃掉 $k$ 片。

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 20$；$2 \le m \le 5 \cdot 10^5$）——分别表示披萨数量和朋友数量。 第二行包含 $m$ 个字符串 $s_1, s_2, \dots, s_m$（$1 \le |s_i| \le n$），其中 $s_i$ 由互不重复的 A 到第 $n$ 个拉丁字母组成，表示第 $i$ 个朋友喜欢的披萨。每个 $s_i$ 中的字符按字典序（字母顺序）排列。 第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \cdot 10^4$）——各披萨的片数。

输出 $\sum a_i + 1$ 个整数，其中第 $k$ 个整数（从 $0$ 开始）表示满足条件（朋友不争吵且 Monocarp 吃 $k$ 片）的选法数目。

以第一个示例的所有朋友对为例： - 邀请朋友 $1$ 和 $2$：他们将吃掉披萨 $1$ 和 $2$，Monocarp 吃披萨 $3$； - 邀请朋友 $1$ 和 $3$：他们将吃掉所有披萨； - 邀请朋友 $1$ 和 $4$：他们将吃披萨 $1$ 和 $2$，Monocarp 吃披萨 $3$； - 邀请朋友 $1$ 和 $5$：他们将吃掉所有披萨； - 邀请朋友 $1$ 和 $6$：他们将吃披萨 $1$ 和 $3$，Monocarp 吃披萨 $2$； - 邀请朋友 $2$ 和 $3$：因披萨 $2$ 发生争吵； - 邀请朋友 $2$ 和 $4$：因披萨 $2$ 发生争吵； - 邀请朋友 $2$ 和 $5$：因披萨 $2$ 发生争吵； - 邀请朋友 $2$ 和 $6$：他们将吃掉所有披萨； - 邀请朋友 $3$ 和 $4$：因披萨 $2$ 发生争吵； - 邀请朋友 $3$ 和 $5$：因披萨 $2$ 发生争吵； - 邀请朋友 $3$ 和 $6$：因披萨 $3$ 发生争吵； - 邀请朋友 $4$ 和 $5$：因披萨 $2$ 发生争吵； - 邀请朋友 $4$ 和 $6$：他们将吃掉所有披萨； - 邀请朋友 $5$ 和 $6$：因披萨 $3$ 发生争吵。 翻译由 DeepSeek R1 完成