M - Popcount MST Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

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