← 返回题目列表

Codeforces · 1129/D

D. 隔离

中文机器翻译题面 查看原题

求出将 $$$n$$$ 整数组成的数组 $$$a$$$ 划分为任意数量的不相交非空段的方法数,以便在每个段中最多存在 $$$k$$$ 个仅出现一次的不同整数。

由于答案可能很大,请对 $$$998\,244\,353$$$ 求模。

输入

第一行包含两个空格分隔的整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 10^5$$$) — 数组 $$$a$$$ 中的元素数量以及语句的限制。

以下行包含 $$$n$$$ 以空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — 数组 $$$a$$$ 的元素。

输出

第一行也是唯一一行包含以 $$$998\,244\,353$$$ 为模除以数组 $$$a$$$ 的方法数。

示例

输入 #1

3 1
1 1 2

输出 #1

3

输入 #2

5 2
1 1 2 1 3

输出 #2

14

输入 #3

5 5
1 2 3 4 5

输出 #3

16

注意

在第一个示例中,三种可能的划分如下。

- $$$[[1], [1], [2]]$$$
- $$$[[1, 1], [2]]$$$
- $$$[[1, 1, 2]]$$$

除 $$$[[1], [1, 2]]$$$ 是不可能的,因为两个不同的整数在第二段 $$$[1, 2]$$$ 中只出现一次。