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