AT_arc114_c [ARC114C] Sequence Scores

[problemUrl]: https://atcoder.jp/contests/arc114/tasks/arc114_c $ 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 $ で割った余りを求めてください．

N/A

N/A

### 制約 - $ 1\ \leq\ N,\ M\ \leq\ 5000 $ - 入力は全て整数 ### Sample Explanation 1 $ 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 $ です．