C - Sequence Scores

Contest Duration: 2021-03-14(Sun) 12:00 - 2021-03-14(Sun) 14:00 (local time) (120 minutes) Back to Home

C - Sequence Scores Editorial

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$ で割った余りを出力せよ．

入力例 1Copy

Copy

2 3

出力例 1Copy

Copy

$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$ です．

入力例 2Copy

Copy

3 2

出力例 2Copy

Copy

入力例 3Copy

Copy

34 56

出力例 3Copy

Copy

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 1Copy

Copy

2 3

Sample Output 1Copy

Copy

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 2Copy

Copy

3 2

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

34 56

Sample Output 3Copy

Copy

649717324