P16535 [THUPC 2026 决赛] 供电网络

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）决赛。 题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。 > 整理完年鉴后，会场准备开启夜间活动的灯光特效。然而，由于后台的供电网络尚未配置完成，备受期待的全息投影仪却迟迟未能亮起。 > > 整个电网由众多中继节点组成，这些节点必须分别接入两个并行的主供电模块。根据电气安全协议，处于同一模块内的相邻节点极易产生相位共振。因此，系统对每个节点在所属模块内的邻点总数，有着严格的奇偶性限制。 > > 面对错综复杂的输送线路，小 S 翻出了一叠陈旧的测试记录。参与过测试的小 T 指出，由于当年的测试是顺着电网层级逐级开展的，记录中涉及的节点集合呈现出规整的嵌套关系：任意两份记录涉及的节点集合，要么完全独立，要么存在严格的包含关系。 > > 盲目试错不仅耗时且风险极高。为了尽快配置好供电网络，小 T 和小 S 需要预先还原出每次测试中，将所有节点接入主模块的方案数。

供电网络包含 $n$ 个节点，节点之间通过若干条双向输送线路相连，构成一张无向图。 在配置网络时，所有节点将被分配至两个独立的主供电模块中。对于节点 $i \ (1 \le i \le n)$，定义其**同模块邻点数** $d_i$ 为：在节点 $i$ 所接入的供电模块内，与其有直接线路连接的节点数量。 小 S 共找出了 $q$ 次测试的记录，每次测试的记录通过一个长度为 $n$ 的字符串 $s$ 来表示。对于第 $i \ (1 \le i \le n)$ 个节点： - 若 $s_i = \text{`0'}$，则要求在该配置下节点 $i$ 的同模块邻点数 $d_i$ 为偶数； - 若 $s_i = \text{`1'}$，则要求在该配置下节点 $i$ 的同模块邻点数 $d_i$ 为奇数； - 若 $s_i = \text{`?'}$，则记录中不涉及节点 $i$，即对节点 $i$ 的同模块邻点数奇偶性不作要求。 小 T 指出，记录中涉及的节点集合呈现出规整的嵌套关系。具体而言，设第 $i \ (1 \le i \le q)$ 份测试涉及的节点集合为 $S_i$（即对应字符串中所有不为 `?` 的位置构成的集合），则对于任意两份不同的测试记录 $i, j \ (1 \le i < j \le q)$，$S_i$ 和 $S_j$ 必定满足以下三种关系之一：$S_i \subseteq S_j$，$S_j \subseteq S_i$，或 $S_i \cap S_j = \varnothing$。 为了尽快配置好供电网络，你需要协助小 T 和小 S 求出，每次测试中将所有节点接入两个主模块的本质不同方案数。两个方案被视为不同，当且仅当存在至少一个节点，在两套方案中被接入了不同的主模块。由于答案可能很大，你只需要求出其对 $10 ^ 9 + 7$ 取模后的结果。

输入的第一行包含两个正整数 $n, q \ (1 \le n, q \le 3 \times 10 ^ 3)$。 接下来 $n$ 行，每行包含一个长度为 $n$ 的 $01$ 字符串，其中第 $i \ (1 \le i \le n)$ 行的第 $j \ (1 \le j \le n)$ 位表示节点 $i$ 与节点 $j$ 间是否存在输送线路，若存在则为 `1`，否则为 `0`。 接下来 $q$ 行，每行包含一个长度为 $n$ 的字符串 $s$，表示一次测试的记录。

输出 $q$ 行，每行一个非负整数，表示该次测试中将所有节点接入两个主模块的本质不同方案数对 $10 ^ 9 + 7$ 取模后的结果。

对于样例 1 的第一次测试，共有以下四种接入方案： 1. 将所有节点接入第一个主模块； 2. 将所有节点接入第二个主模块； 3. 将节点 $1, 2$ 接入第一个主模块，将节点 $3$ 接入第二个主模块； 4. 将节点 $1, 2$ 接入第二个主模块，将节点 $3$ 接入第一个主模块。