Non-Intersecting Subpermutations
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
You are given two integers $n$ and $k$.
For an array of length $n$, let's define its cost as the maximum number of contiguous subarrays of this array that can be chosen so that:
- each element belongs to at most one subarray;
- the length of each subarray is exactly $k$;
- each subarray contains each integer from $1$ to $k$ exactly once.
For example, if $n = 10$, $k = 3$ and the array is $[1, 2, 1, 3, 2, 3, 2, 3, 1, 3]$, its cost is $2$ because, for example, we can choose the subarrays from the $2$-nd element to the $4$-th element and from the $7$-th element to the $9$-th element, and we can show that it's impossible to choose more than $2$ subarrays.
Calculate the sum of costs over all arrays of length $n$ consisting of integers from $1$ to $k$, and print it modulo $998244353$.
The only line of the input contains two integers $n$ and $k$ ($2 \le k \le n \le 4000$).
Print one integer — the sum of costs of all arrays of length $n$ consisting of integers from $1$ to $k$ taken modulo $998244353$.
Input
The only line of the input contains two integers $n$ and $k$ ($2 \le k \le n \le 4000$).
Output
Print one integer — the sum of costs of all arrays of length $n$ consisting of integers from $1$ to $k$ taken modulo $998244353$.
10 3
2 2
1337 42
71712
2
524933698
9月26日晚上集训比赛
- Status
- Done
- Rule
- IOI
- Problem
- 6
- Start at
- 2023-9-26 19:00
- End at
- 2023-9-26 21:00
- Duration
- 2 hour(s)
- Host
- Partic.
- 19