問題一覧 > 通常問題

No.3762 Glowing Utility Pole

レベル : / AI推定難易度 : 2325 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 9
作問者 : ei1333333 / テスター : kyoprouno ei13333333
お気に入りにしたユーザー ProblemId : 9574 / 自分の提出
問題文最終更新日: 2026-10-09 00:25:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 517 (順位表) の他の問題:

Problem Statement

Iroha found $N$ gaming utility poles. The gaming utility poles stand in a row, and each of them glows in one of the colors $1, 2, \cdots, M$.

As information about the color of pole $i$, an integer $C_i$ is given.

  • If $1 \leq C_i \leq M$, pole $i$ glows in color $C_i$.
  • If $C_i = 0$, pole $i$ is so dazzling that its color is unknown.

Let $T$ be the number of poles with $C_i = 0$. There are $M^T$ ways to assign each of these $T$ poles one of the colors $1, 2, \cdots, M$.

For each of the $M^T$ ways, consider the number of contiguous intervals $[l, r] (1 \leq l \leq r \leq N)$ that contain at least $1$ pole of every one of the $M$ colors.

Find the sum of this number over all color assignments, modulo $998244353$.

Constraints

  • $1 \leq N \leq 3 \times 10^5$
  • $1 \leq M \leq 16$
  • $0 \leq C_i \leq M$
  • All inputs are integers.

Input

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

Output

Print the answer on $1$ line.

Sample

Sample 1
Input
5 3
1 2 1 0 0
Output
18
  • $(1, 2, 1, 1, 1), (1, 2, 1, 1, 2), (1, 2, 1, 2, 1), (1, 2, 1, 2, 2)$: $0$ intervals
  • $(1, 2, 1, 1, 3)$: $2$ intervals, $[1, 5], [2, 5]$
  • $(1, 2, 1, 2, 3)$: $3$ intervals, $[1, 5], [2, 5], [3, 5]$
  • $(1, 2, 1, 3, 1)$: $4$ intervals, $[1, 4], [1, 5], [2, 4], [2, 5]$
  • $(1, 2, 1, 3, 2)$: $5$ intervals, $[1, 4], [1, 5], [2, 4], [2, 5], [3, 5]$
  • $(1, 2, 1, 3, 3)$: $4$ intervals, $[1, 4], [1, 5], [2, 4], [2, 5]$

We have $0 + 2 + 3 + 4 + 5 + 4 = 18$.

Sample 2
Input
5 5
1 2 3 2 1
Output
0

Sample 3
Input
15 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output
984264678

Print the sum modulo $998244353$.

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