F - Many Increasing Problems Editorial /

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 Problem

You 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 Problems

There 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