← 返回题目列表

AtCoder · KeioPC2025_m

M. 按位计数最小生成树

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

配点 : 101 点

問題文

长度为 N 的整数列 A = (A_0, \dots , A_{N-1}) , f(A) 如下。这里 表示 a \ \mathrm{AND} \ b 是 a 和 b 的按位与。

  • 在顶部 编号为 0 它们的编号最大为 2^N-1 它有多个 2^N 顶点加权完整图 考虑 G 。然而,顶点 i 和顶点 连接 j 的边的权重为 \displaystyle 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 然后 M^q 方法有很多。

可能 B' 对于所有人 f(B') 的总和 除以 998244353 取余。起初,数列

\mathrm{popcount} 是什么? 关于

非負整数 x 关于 \operatorname{popcount}(x) 是什么?x 的 2 当用基本符号表示时 1 的数量。更准确地说,非负整数 当 x 关于 \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace) 成立时 \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i 。

例如, 经过13 的 2 以基本符号表示 小于或等于 1101 所以, 正确答案是输出组合 \operatorname{popcount}(13)=3 。

制約

  • 1 \le N, M \le 125000
  • B_i 是 -1 或 1 以上 M 的整数 如果正确答案是满足

部分点

针对此问题设置了部分分数。 如果所有满足

  • 1 \le B_i \le M 的数据集 1 点。

入力

输入是按以下格式从标准输入给出的。

N \ M
B_0 \ \dots \ B_{N-1}

出力

输出答案。


入力例 1

2 2
-1 2

出力例 1

9

可能 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 。


入力例 2

7 7
-1 7 -1 7 -1 7 -1

出力例 2

801052

入力例 3

8 8
5 7 2 4 7 1 8 6

出力例 3

445