Occurrences
题意翻译
定义 $a$ 的子序列是 $[a_l,a_{l+1},\cdots,a_r]$ 的连续子段构成的序列,定义 $a$ 序列在 $b$ 序列中出现的次数为 $b$ 序列中与 $a$ 相同的子序列个数。
有 $n$ 个值域在 $[1,k]$ 的数列 $A_1,A_2,\cdots,A_n$,要求构造一个长为 $m$ 的值域在 $[1,k]$ 的序列 $a$,满足对于所有数列 $A_i$,$A_i$ 在序列 $a$ 中的出现次数大于等于其任意一个非空子序列在 $a$ 中的出现次数。
求不同的 $a$ 的数量,答案 $\bmod 998244353$。
**数据范围**:$1\le n,m,k\le 3\times 10^5,\sum c_i\le 3\times 10^5$。
题目描述
A subarray of array $ a $ from index $ l $ to the index $ r $ is the array $ [a_l, a_{l+1}, \dots, a_{r}] $ . The number of occurrences of the array $ b $ in the array $ a $ is the number of subarrays of $ a $ such that they are equal to $ b $ .
You are given $ n $ arrays $ A_1, A_2, \dots, A_n $ ; the elements of these arrays are integers from $ 1 $ to $ k $ . You have to build an array $ a $ consisting of $ m $ integers from $ 1 $ to $ k $ in such a way that, for every given subarray $ A_i $ , the number of occurrences of $ A_i $ in the array $ a $ is not less than the number of occurrences of each non-empty subarray of $ A_i $ in $ a $ . Note that if $ A_i $ doesn't occur in $ a $ , and no subarray of $ A_i $ occurs in $ a $ , this condition is still met for $ A_i $ .
Your task is to calculate the number of different arrays $ a $ you can build, and print it modulo $ 998244353 $ .
输入输出格式
输入格式
The first line contains three integers $ n $ , $ m $ and $ k $ ( $ 1 \le n, m, k \le 3 \cdot 10^5 $ ) — the number of the given arrays, the desired length of the array $ a $ , and the upper bound on the values in the arrays.
Then $ n $ lines follow. The $ i $ -th line represents the array $ A_i $ . The first integer in the $ i $ -th line is $ c_i $ ( $ 1 \le c_i \le m $ ) — the number of elements in $ A_i $ ; then, $ c_i $ integers from $ 1 $ to $ k $ follow — the elements of the array $ A_i $ .
Additional constraint on the input: $ \sum\limits_{i=1}^n c_i \le 3 \cdot 10^5 $ ; i. e., the number of elements in the given arrays in total does not exceed $ 3 \cdot 10^5 $ .
输出格式
Print one integer — the number of different arrays $ a $ you can build, taken modulo $ 998244353 $ .
输入输出样例
输入样例 #1
2 4 3
2 1 2
1 3
输出样例 #1
5
输入样例 #2
2 4 3
2 1 2
3 3 2 1
输出样例 #2
0
输入样例 #3
1 42 1337
2 13 31
输出样例 #3
721234447