問題一覧 > 通常問題

No.2801 Unique Maximum

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

問題文

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

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

制約

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

入力

NN MM

出力

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

サンプル

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

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

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

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

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

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

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

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