問題一覧 > 通常問題

No.3095 Many Min Problems

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

問題文

長さ NN の整数列 A1,A2,…,ANA_1,A_2,\dots,A_N に対して、スコアを以下のように定義します。

∑i=1Nmin⁡i≤j≤NAj \sum_{i=1}^N \min_{i \le j \le N} A_j

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

入力

N MN\ M

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 1≤M≤2×1051 \le M \le 2 \times 10^5
  • N,MN,M は整数

出力

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

サンプル

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

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

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

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

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

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