AtCoder Regular Contest 114
翻译中…
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$.
翻译中…
样例
Input #1
2 3
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$.
Input #2
3 2
Output #2
15
Input #3
34 56
Output #3
649717324
题目信息
题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。