問題一覧 > 通常問題

No.2801 Unique Maximum

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : noya2noya2 / テスター : 👑 potato167potato167 shobonvipshobonvip
3 ProblemId : 11116 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-06-28 21:06:37

問題文

長さ $N$ の正整数列 $A=(A_1,A_2,\dots ,A_N)$ であって、次の条件を満たすものの個数を $998244353$ で割ったあまりを求めてください。

  • $1\le A_i\le M\ (1\le i\le N)$
  • $A$ の任意の空でない連続部分列 $B$ は次の条件を満たす。
    • $B$ の要素の最大値を $x$ とする。 $B$ の中に $x$ はちょうど $1$ 度だけ現れる。

制約

  • 入力はすべて整数
  • $1\le N\le 2\times 10^5$
  • $1\le M\le 10^9$

入力

$N$ $M$

出力

答えを出力してください。

サンプル

サンプル1
入力
4 3
出力
10

条件を満たす $A$ としては次のようなものが挙げられます。

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

逆に次の $A$ は条件を満たしません。

  • $(2,1,2,3)$
    • 連続部分列 $(2,1,2)$ は、最大値 $2$ が $2$ 度現れています。
  • $(2,1,1,1)$
    • 連続部分列 $(1,1,1)$ は、最大値 $1$ が $3$ 度現れています。

サンプル2
入力
628 628
出力
652208441

サンプル3
入力
62862 86286
出力
451956562

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