No.3095 Many Min Problems
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
hamo21