310623: CF1861E. Non-Intersecting Subpermutations
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$.
InputThe only line of the input contains two integers $n$ and $k$ ($2 \le k \le n \le 4000$).
OutputPrint one integer — the sum of costs of all arrays of length $n$ consisting of integers from $1$ to $k$ taken modulo $998244353$.
ExamplesInput10 3Output
71712Input
2 2Output
2Input
1337 42Output
524933698
Output
这是一个关于子排列的问题。给定两个整数n和k，你需要计算所有长度为n，由1到k的整数组成的数组的成本之和，并对998244353取模。
数组成本的定义是：从数组中可以选择的，长度恰好为k的，互不重叠的连续子数组的最大数量，且每个子数组包含从1到k的每个整数恰好一次。
输入输出数据格式：
输入：
- 一行两个整数n和k（2≤k≤n≤4000）
输出：
- 一个整数，表示所有长度为n，由1到k的整数组成的数组的成本之和，对998244353取模后的结果。
示例：
输入：
10 3
输出：
71712
输入：
2 2
输出：
2
输入：
1337 42
输出：
524933698题目大意： 这是一个关于子排列的问题。给定两个整数n和k，你需要计算所有长度为n，由1到k的整数组成的数组的成本之和，并对998244353取模。 数组成本的定义是：从数组中可以选择的，长度恰好为k的，互不重叠的连续子数组的最大数量，且每个子数组包含从1到k的每个整数恰好一次。 输入输出数据格式： 输入： - 一行两个整数n和k（2≤k≤n≤4000） 输出： - 一个整数，表示所有长度为n，由1到k的整数组成的数组的成本之和，对998244353取模后的结果。 示例： 输入： 10 3 输出： 71712 输入： 2 2 输出： 2 输入： 1337 42 输出： 524933698