AT_KeioPC2025_m Popcount MST

对于长度为 $N$ 的整数序列 $A = (A_0, \dots, A_{N-1})$，我们定义 $f(A)$ 如下。这里 $a\ \mathrm{AND}\ b$ 表示 $a$ 与 $b$ 的按位与操作。 - 我们考虑一个有 $2^N$ 个顶点的加权完全图 $G$，顶点编号为 $0$ 到 $2^N-1$。对于顶点 $i$ 和顶点 $j$ 之间的边，其权值为 $A_{\mathrm{popcount}(i\ \mathrm{AND}\ j)}$。此时，该图 $G$ 的最小生成树所包含的所有边的权值之和记为 $f(A)$。 给定长度为 $N$ 的整数序列 $B = (B_0, \dots, B_{N-1})$，其中 $B$ 的每个元素为 $-1$ 或者 $1$ 到 $M$ 之间的整数。 将 $B$ 中所有 $-1$ 替换成 $1$ 到 $M$ 之间的整数，可以得到一个数列 $B'$。若 $B$ 中 $-1$ 的个数为 $q$，则这样的 $B'$ 一共有 $M^q$ 种可能。 请你计算所有可能的 $B'$ 的 $f(B')$ 之和，对 $998244353$ 取模后输出。 $\mathrm{popcount}$ 是什么？对于非负整数 $x$，$\operatorname{popcount}(x)$ 表示将 $x$ 用二进制表示时 $1$ 的个数。更严格地说，对于非负整数 $x$，若 $x = \sum_{i=0}^{\infty} b_i 2^i \ (b_i \in \lbrace 0,1\rbrace)$，那么 $\operatorname{popcount}(x) = \sum_{i=0}^{\infty} b_i$。 例如，将 $13$ 用二进制表示为 `1101`，因此 $\operatorname{popcount}(13) = 3$。

输入通过标准输入提供，格式如下： > $N \ M$ > $B_0\ \dots\ B_{N-1}$

请输出答案。

### 部分分 本题包含部分分。 - 如果你的算法可以正确解决满足 $1 \le B_i \le M$ 的数据，将获得 $1$ 分。 ### 样例解释 1 所有可行的 $B'$ 有如下 $2$ 种： - 当 $B' = (1, 2)$ 时，一个可能的最小生成树由边 $(0, 1), (0, 2), (0, 3)$ 构成，权值和为 $3$。 - 当 $B' = (2, 2)$ 时，一个可能的最小生成树由边 $(0, 1), (1, 2), (2, 3)$ 构成，权值和为 $6$。 因此，所有 $B'$ 的 $f(B')$ 之和为 $9$。 # 数据范围 - $1 \le N, M \le 125000$ - $B_i$ 为 $-1$ 或 $1$ 到 $M$ 之间的整数。 由 ChatGPT 5 翻译