/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 以上 M 以下の整数から成る長さ N の数列 A に対して， f(A) を以下のように定義します．
- 長さ N の数列 X があり，初め全ての要素は 0 である．f(A) を，次の操作を繰り返して X を A に等しくするための最小の操作回数とする．
- 1 \leq l \leq r \leq N と 1 \leq v \leq M を指定する．l \leq i \leq r に対して X_i を \max(X_i, v) で置き換える．
A として考えられる数列は M^N 通りあります．これら全ての数列に対する f(A) の和を 998244353 で割った余りを求めてください．
制約
- 1 \leq N, M \leq 5000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる．
N M
出力
全ての数列に対する f(A) の和を 998244353 で割った余りを出力せよ．
入力例 1
2 3
出力例 1
15
3 ^ 2 = 9 通りの数列と，それに対する f の値は以下の通りです．
- A = (1, 1) のとき，(l = 1, r = 2, v = 1) として 1 回の操作で可能なので，f(A) = 1 です．
- A = (1, 2) のとき，(l = 1, r = 2, v = 1) , (l = 2, r = 2, v = 2) として 2 回の操作で可能なので，f(A) = 2 です．
- A = (1, 3) のとき，(l = 1, r = 2, v = 1) , (l = 2, r = 2, v = 3) として 2 回の操作で可能なので，f(A) = 2 です．
- A = (2, 1) のとき，(l = 1, r = 2, v = 1) , (l = 1, r = 1, v = 2) として 2 回の操作で可能なので，f(A) = 2 です．
- A = (2, 2) のとき，(l = 1, r = 2, v = 2) として 1 回の操作で可能なので，f(A) = 1 です．
- A = (2, 3) のとき，(l = 1, r = 2, v = 2) , (l = 2, r = 2, v = 3) として 2 回の操作で可能なので，f(A) = 2 です．
- A = (3, 1) のとき，(l = 1, r = 2, v = 1) , (l = 1, r = 1, v = 3) として 2 回の操作で可能なので，f(A) = 2 です．
- A = (3, 2) のとき，(l = 1, r = 2, v = 2) , (l = 1, r = 1, v = 3) として 2 回の操作で可能なので，f(A) = 2 です．
- A = (3, 3) のとき，(l = 1, r = 2, v = 3) として 1 回の操作で可能なので，f(A) = 1 です．
これらの和は 3 \times 1 + 6 \times 2 = 15 です．
入力例 2
3 2
出力例 2
15
入力例 3
34 56
出力例 3
649717324
Score : 600 points
Problem Statement
For a sequence A of length N consisting of integers between 1 and M (inclusive), let us define f(A) as follows:
- We have a sequence X of length N, where every element is initially 0. f(A) is the minimum number of operations required to make X equal A by repeating the following operation:
- Specify 1 \leq l \leq r \leq N and 1 \leq v \leq M, then replace X_i with \max(X_i, v) for each l \leq i \leq r.
Find the sum, modulo 998244353, of f(A) over all M^N sequences that can be A.
Constraints
- 1 \leq N, M \leq 5000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the sum of f(A) over all sequences A, modulo 998244353.
Sample Input 1
2 3
Sample Output 1
15
The 3 ^ 2 = 9 sequences and the value of f for those are as follows:
- For A = (1, 1), we can make X equal it with one operation with (l = 1, r = 2, v = 1), so f(A) = 1.
- For A = (1, 2), we can make X equal it with two operations with (l = 1, r = 2, v = 1) and (l = 2, r = 2, v = 2), so f(A) = 2.
- For A = (1, 3), we can make X equal it with two operations with (l = 1, r = 2, v = 1) and (l = 2, r = 2, v = 3), so f(A) = 2.
- For A = (2, 1), we can make X equal it with two operations with (l = 1, r = 2, v = 1) and (l = 1, r = 1, v = 2), so f(A) = 2.
- For A = (2, 2), we can make X equal it with one operation with (l = 1, r = 2, v = 2), so f(A) = 1.
- For A = (2, 3), we can make X equal it with two operations with (l = 1, r = 2, v = 2) , (l = 2, r = 2, v = 3), so f(A) = 2.
- For A = (3, 1), we can make X equal it with two operations with (l = 1, r = 2, v = 1) and (l = 1, r = 1, v = 3) so f(A) = 2.
- For A = (3, 2), we can make X equal it with two operations with (l = 1, r = 2, v = 2) and (l = 1, r = 1, v = 3), so f(A) = 2.
- For A = (3, 3), we can make X equal it with one operation with (l = 1, r = 2, v = 3), so f(A) = 1.
The sum of these values is 3 \times 1 + 6 \times 2 = 15.
Sample Input 2
3 2
Sample Output 2
15
Sample Input 3
34 56
Sample Output 3
649717324