問題一覧 > 通常問題

No.3095 Many Min Problems

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 43
作問者 : hamo21 / テスター : autumn09 downer RiRinbaru 👑 ygussany Yotugi
2 ProblemId : 11904 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-04-06 13:27:35

問題文

長さ $N$ の整数列 $A_1,A_2,\dots,A_N$ に対して、スコアを以下のように定義します。

$$ \sum_{i=1}^N \min_{i \le j \le N} A_j $$

長さが $N$ で、任意の $i$ に対して $1 \le A_i \le M$ を満たす整数列は $M^N$ 個存在します。これらの全ての整数列に対して、スコアの総和を求めてください。 答えは非常に大きくなる可能性があるので、$998244353$ で割った余りを出力してください。

入力

$N\ M$

  • $1 \le N \le 2 \times 10^5$
  • $1 \le M \le 2 \times 10^5$
  • $N,M$ は整数

出力

スコアの総和を $998244353$ で割った余りを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
2 2
出力
11

$A$ の候補は $(1,1),(1,2),(2,1),(2,2)$ の $4$ 通りあります。 これらのスコアはそれぞれ $1+1=2,\ 1+2=3,\ 1+1=2,\ 2+2=4$ であり、合計で $11$ です。

サンプル2
入力
1 10
出力
55

サンプル3
入力
200000 200000
出力
43302656

$998244353$ で割った余りを出力してください

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