CF1989E Distance to Different

题目描述

给定一个长度为 $n$ 的整数数组 $a$，其中每个元素的取值范围为 $1$ 到 $k$，并且 $1$ 到 $k$ 的每个整数在 $a$ 中至少出现一次。

定义数组 $b$ 的构造方式如下：对于 $a$ 的第 $i$ 个元素，$b_i$ 表示距离最近的、不等于 $a_i$ 的元素在 $a$ 中的位置距离。换句话说，$b_i = \min \limits_{j \in [1, n], a_j \ne a_i} |i - j|$。

例如，如果 $a = [1, 1, 2, 3, 3, 3, 3, 1]$，那么 $b = [2, 1, 1, 1, 2, 2, 1, 1]$。

请计算在所有可能的数组 $a$ 中，可以得到多少种不同的数组 $b$，并将答案对 $998244353$ 取模后输出。

输入格式

输入仅一行，包含两个整数 $n$ 和 $k$（$2 \le n \le 2 \cdot 10^5$；$2 \le k \le \min(n, 10)$）。

输出格式

输出一个整数，表示可以得到的不同数组 $b$ 的数量，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

2 2

输出 #1

1

输入输出样例 #2

输入 #2

4 3

输出 #2

3

输入输出样例 #3

输入 #3

6 2

输出 #3

20

输入输出样例 #4

输入 #4

6 5

输出 #4

3

输入输出样例 #5

输入 #5

133 7

输出 #5

336975971

说明/提示

由 ChatGPT 4.1 翻译