問題一覧 > 通常問題

No.3095 Many Min Problems

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 46
作問者 : hamo21 / テスター : autumn09 downer RiRinbaru ygussany Yotugi
お気に入りにしたユーザー ProblemId : 11904 / 自分の提出
問題文最終更新日: 2025-04-06 13:27:35
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
QUPC2024 (順位表) の他の問題:

Problem Statement

For an integer sequence $A_1,A_2,\dots,A_N$ of length $N$, define its score as follows.

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

There are $M^N$ integer sequences of length $N$ satisfying $1 \le A_i \le M$ for every $i$. Find the sum of the scores over all of these integer sequences. Since the answer can be very large, output it modulo $998244353$.

Input

$N\ M$

  • $1 \le N \le 2 \times 10^5$
  • $1 \le M \le 2 \times 10^5$
  • $N,M$ are integers

Output

Output the sum of the scores modulo $998244353$. End the output with a newline.

Sample

Sample 1
Input
2 2
Output
11

There are $4$ candidates for $A$: $(1,1),(1,2),(2,1),(2,2)$. Their scores are $1+1=2,\ 1+2=3,\ 1+1=2,\ 2+2=4$ respectively, for a total of $11$.

Sample 2
Input
1 10
Output
55

Sample 3
Input
200000 200000
Output
43302656

Output the answer modulo $998244353$.

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