問題一覧 > 通常問題

No.2801 Unique Maximum

レベル : / AI推定難易度 : 2900 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 6
作問者 : noya2 / テスター : 👑 potato167 shobonvip
お気に入りにしたユーザー ProblemId : 11116 / 自分の提出
問題文最終更新日: 2024-06-28 21:06:37
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 435 (順位表) の他の問題:

Problem Statement

Find the number, modulo $998244353$, of sequences of positive integers $A=(A_1,A_2,\dots ,A_N)$ of length $N$ that satisfy the following conditions.

  • $1\le A_i\le M\ (1\le i\le N)$
  • Every non-empty contiguous subarray $B$ of $A$ satisfies the following condition.
    • Let $x$ be the maximum value of the elements of $B$. Then $x$ appears exactly $1$ time in $B$.

Constraints

  • All inputs are integers.
  • $1\le N\le 2\times 10^5$
  • $1\le M\le 10^9$

Input

$N$ $M$

Output

Output the answer.

Sample

Sample 1
Input
4 3
Output
10

Examples of $A$ that satisfy the conditions include the following.

  • $(1,2,3,2)$
  • $(1,3,1,2)$
  • $(3,1,2,1)$

Conversely, the following $A$ do not satisfy the conditions.

  • $(2,1,2,3)$
    • In the contiguous subarray $(2,1,2)$, the maximum value $2$ appears $2$ times.
  • $(2,1,1,1)$
    • In the contiguous subarray $(1,1,1)$, the maximum value $1$ appears $3$ times.

Sample 2
Input
628 628
Output
652208441

Sample 3
Input
62862 86286
Output
451956562

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