配点 : 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