306182: CF1158F. Density of subarrays
Memory Limit:256 MB
Time Limit:6 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Density of subarrays
题意翻译
我们定义一个“c序列”为序列里的数都是$[1,c]$的序列。定义一个c序列的“密度”为最大的$p$,使得**任意**长度为$p$的序列(总共$c^p$个)都是它的子序列。 给定一个长度为$n$的$c$序列,对$p\in[0,n]$,求该序列有多少个子序列的密度为$p$,mod $998244353$。 $n,c<=3000$题目描述
Let $ c $ be some positive integer. Let's call an array $ a_1, a_2, \ldots, a_n $ of positive integers $ c $ -array, if for all $ i $ condition $ 1 \leq a_i \leq c $ is satisfied. Let's call $ c $ -array $ b_1, b_2, \ldots, b_k $ a subarray of $ c $ -array $ a_1, a_2, \ldots, a_n $ , if there exists such set of $ k $ indices $ 1 \leq i_1 < i_2 < \ldots < i_k \leq n $ that $ b_j = a_{i_j} $ for all $ 1 \leq j \leq k $ . Let's define density of $ c $ -array $ a_1, a_2, \ldots, a_n $ as maximal non-negative integer $ p $ , such that any $ c $ -array, that contains $ p $ numbers is a subarray of $ a_1, a_2, \ldots, a_n $ . You are given a number $ c $ and some $ c $ -array $ a_1, a_2, \ldots, a_n $ . For all $ 0 \leq p \leq n $ find the number of sequences of indices $ 1 \leq i_1 < i_2 < \ldots < i_k \leq n $ for all $ 1 \leq k \leq n $ , such that density of array $ a_{i_1}, a_{i_2}, \ldots, a_{i_k} $ is equal to $ p $ . Find these numbers by modulo $ 998\,244\,353 $ , because they can be too large.输入输出格式
输入格式
The first line contains two integers $ n $ and $ c $ , separated by spaces ( $ 1 \leq n, c \leq 3\,000 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ , separated by spaces ( $ 1 \leq a_i \leq c $ ).
输出格式
Print $ n + 1 $ numbers $ s_0, s_1, \ldots, s_n $ . $ s_p $ should be equal to the number of sequences of indices $ 1 \leq i_1 < i_2 < \ldots < i_k \leq n $ for all $ 1 \leq k \leq n $ by modulo $ 998\,244\,353 $ , such that the density of array $ a_{i_1}, a_{i_2}, \ldots, a_{i_k} $ is equal to $ p $ .
输入输出样例
输入样例 #1
4 1
1 1 1 1
输出样例 #1
0 4 6 4 1
输入样例 #2
3 3
1 2 3
输出样例 #2
6 1 0 0
输入样例 #3
5 2
1 2 1 2 1
输出样例 #3
10 17 4 0 0 0