306006: CF1129D. Isolation

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Isolation

题意翻译

给出一个长度为 $n$ 的序列,把它划分成若干段,使得每一段中出现过**恰好**一次的元素个数 $\le k$,求方案数对 $998244353$ 取模后的结果。

题目描述

Find the number of ways to divide an array $ a $ of $ n $ integers into any number of disjoint non-empty segments so that, in each segment, there exist at most $ k $ distinct integers that appear exactly once. Since the answer can be large, find it modulo $ 998\,244\,353 $ .

输入输出格式

输入格式


The first line contains two space-separated integers $ n $ and $ k $ ( $ 1 \leq k \leq n \leq 10^5 $ ) — the number of elements in the array $ a $ and the restriction from the statement. The following line contains $ n $ space-separated integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ) — elements of the array $ a $ .

输出格式


The first and only line contains the number of ways to divide an array $ a $ modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #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

说明

In the first sample, the three possible divisions are as follows. - $ [[1], [1], [2]] $ - $ [[1, 1], [2]] $ - $ [[1, 1, 2]] $ Division $ [[1], [1, 2]] $ is not possible because two distinct integers appear exactly once in the second segment $ [1, 2] $ .

Input

题意翻译

给出一个长度为 $n$ 的序列,把它划分成若干段,使得每一段中出现过**恰好**一次的元素个数 $\le k$,求方案数对 $998244353$ 取模后的结果。

加入题单

上一题 下一题 算法标签: