No.1887 K Consecutive Ks (Easy)
タグ : / 解いたユーザー数 53
作問者 :
miscalc
/ テスター :
akakimidori
Problem Statement
This is the same problem as Problem G, but with different constraints and a different execution time limit.
Find the number of sequences $A = (A_1, A_2, \ldots, A_N)$ of length $N$ consisting of integers between $1$ and $M$, inclusive, that satisfy the following condition.
- $A$ contains a place where some positive integer $k$ appears $k$ times consecutively. That is, there exist positive integers $i, k$ ($i + k - 1 \leq N$) such that $A_i = A_{i + 1} = \cdots = A_{i + k - 1} = k$.
Input
$N$ $M$
- All inputs are integers.
- $1 \leq N \leq 3000$
- $1 \leq M \leq 3000$
Output
Print the number of sequences $A$ satisfying the condition, modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
2 3
Output
6
The following $6$ sequences $A$ satisfy the condition.
- $(1, 1), (1, 2), (1, 3), (2, 1), (3, 1)$ contain a place where $1$ appears $1$ time consecutively.
- $(2, 2)$ contains a place where $2$ appears $2$ times consecutively.
Sample 2
Input
5 4
Output
884
Here are some examples of sequences $A$ that satisfy the condition.
- $(4, 2, 4, 1, 3)$ contains a place where $1$ appears $1$ time consecutively.
- $(4, 3, 3, 3, 2)$ contains a place where $3$ appears $3$ times consecutively.
- $(2, 2, 4, 2, 2)$ contains a place where $2$ appears $2$ times consecutively.
- $(2, 2, 3, 3, 3)$ contains a place where $2$ appears $2$ times consecutively and a place where $3$ appears $3$ times consecutively.
- $(3, 3, 3, 3, 3)$ contains a place where $3$ appears $3$ times consecutively.
Sample 3
Input
3000 3000
Output
762730266
Print the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。