CF1861E Non-Intersecting Subpermutations

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 $ .

N/A

N/A