Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 1100 点
問題文
PCT 君は以下の問題を作りました。
Increasing Problem長さ N の非負整数列 A_1,A_2,\dots,A_N が与えられます。あなたは以下の操作を好きな回数(0 回でもよい)行うことが出来ます。
- 1 \le i \le N を満たす整数 i を 1 個選び、A_i を 1 増やすか 1 減らす。
あなたの目標は A を広義単調増加にすることです。目標を達成するために必要な最小の操作回数を求めてください。
この問題がコンテストの最後に置くには簡単だと考えた PCT 君は、以下のように改題しました。
Many Increasing Problems長さ N かつ全ての要素が 1 以上 M 以下であるような整数列 A は M^N 個ありますが、その全てに対する Increasing Problem の答えの総和を 998244353 で割ったあまりを求めてください。
Many Increasing Problems を解いてください。
制約
- 1 \le N,M \le 10^5
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
Many Increasing Problems の答えを出力せよ。
入力例 1
2 2
出力例 1
1
長さが 2 かつ全ての要素が 1 以上 2 以下である数列全てに対して Increasing Problem を解きます。
- A=(1,1) の時の解は 0
- A=(1,2) の時の解は 0
- A=(2,1) の時の解は 1
- A=(2,2) の時の解は 0
よって、答えは 0+0+1+0=1 です。
入力例 2
6 4
出力例 2
14668
入力例 3
163 702
出力例 3
20728656
入力例 4
98765 99887
出力例 4
103564942
Score : 1100 points
Problem Statement
PCT-kun created the following problem.
Increasing ProblemYou are given a length-N sequence of non-negative integers A_1,A_2,\dots,A_N. You can perform the following operation any number of times (possibly zero).
- Choose an integer i such that 1 \le i \le N, and increase or decrease A_i by 1.
Your goal is to make A non-decreasing. Find the minimum number of operations required to achieve this goal.
Thinking that this problem is too easy to be placed at the end of the contest, PCT-kun has revised it as follows.
Many Increasing ProblemsThere are M^N integer sequences A of length N where all elements are between 1 and M, inclusive. Find the sum of the answers to Increasing Problem for all those sequences, modulo 998244353.
Solve Many Increasing Problems.
Constraints
- 1 \le N,M \le 10^5
Input
The input is given from Standard Input in the following format:
N M
Output
Print the answer to Many Increasing Problems.
Sample Input 1
2 2
Sample Output 1
1
Let us solve Increasing Problem for all sequences of length 2 where all elements are between 1 and 2, inclusive.
- For A=(1,1), the answer is 0.
- For A=(1,2), the answer is 0.
- For A=(2,1), the answer is 1.
- For A=(2,2), the answer is 0.
Therefore, the final answer is 0+0+1+0=1.
Sample Input 2
6 4
Sample Output 2
14668
Sample Input 3
163 702
Sample Output 3
20728656
Sample Input 4
98765 99887
Sample Output 4
103564942