問題一覧 > 通常問題

No.3762 Glowing Utility Pole

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 9
作問者 : ei1333333 / テスター : kyoprouno ei13333333
お気に入りにしたユーザー ProblemId : 9574 / 自分の提出
問題文最終更新日: 2026-10-09 00:25:48
yukicoder contest 517 (順位表) の他の問題:

問題文

いろはは、$N$ 本のゲーミング電柱を見つけました。ゲーミング電柱は一列に並んでいて、それぞれ $1, 2, \cdots, M$ のいずれかの色に光っています。

電柱 $i$ の色に関する情報として、整数 $C_i$ が与えられます。

  • $1 \leq C_i \leq M$ のとき、電柱 $i$ は色 $C_i$ に光っています。
  • $C_i = 0$ のとき、電柱 $i$ は眩しくて何色に光っているかわかりません。

$C_i = 0$ の電柱の本数を $T$ とします。これら $T$ 本の電柱の色を、それぞれ $1, 2, \cdots, M$ のいずれかに決める方法は $M^T$ 通りあります。

$M^T$ 通りのそれぞれについて、$M$ 種類全ての色を少なくとも $1$ 本ずつ含む連続区間 $[l, r] (1 \leq l \leq r \leq N)$ の個数を考えます。

全ての色の決め方におけるこの個数の総和を、 $998244353$ で割った余りとして求めてください。

制約

  • $1 \leq N \leq 3 \times 10^5$
  • $1 \leq M \leq 16$
  • $0 \leq C_i \leq M$
  • 入力はすべて整数

入力

$N$ $M$
$C_1$ $C_2$ $\cdots$ $C_N$

出力

$1$ 行に答えを出力せよ。

サンプル

サンプル1
入力
5 3
1 2 1 0 0
出力
18
  • $(1, 2, 1, 1, 1), (1, 2, 1, 1, 2), (1, 2, 1, 2, 1), (1, 2, 1, 2, 2)$: $0$ 通り
  • $(1, 2, 1, 1, 3)$: 区間 $[1, 5], [2, 5]$ の $2$ 通り
  • $(1, 2, 1, 2, 3)$: 区間 $[1, 5], [2, 5], [3, 5]$ の $3$ 通り
  • $(1, 2, 1, 3, 1)$: 区間 $[1, 4], [1, 5], [2, 4], [2, 5]$ の $4$ 通り
  • $(1, 2, 1, 3, 2)$: 区間 $[1, 4], [1, 5], [2, 4], [2, 5], [3, 5]$ の $5$ 通り
  • $(1, 2, 1, 3, 3)$: 区間 $[1, 4], [1, 5], [2, 4], [2, 5]$ の $4$ 通り

$0 + 2 + 3 + 4 + 5 + 4 = 18$ です。

サンプル2
入力
5 5
1 2 3 2 1
出力
0

サンプル3
入力
15 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力
984264678

総和を $998244353$ で割ったあまりで出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。