#P15018. [2026省选联测]玩具

    ID: 14234 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400组合数学多项式数学前缀和动态规划状压DPFFT

[2026省选联测]玩具

题目描述

Alice 找到 NN 个箱子,箱子里装着互不相同的一些玩具,一共有MM种玩具,编号从 11 到 MM,同一种玩具可能出现在多个箱子里。

Alice 决定从中选择一些箱子,把这些箱子中的玩具聚集到一起,必须保证每种玩具至少出现一次。

你需要 Alice 一共有多少种选择方案。

你还需要对于 k=0,1,⋯ ,nk=0,1,\cdots,n 输出 Alice 恰好选出 kk 个箱子一共有多少种选择方案。

由于我非常善良,你如果只正确的输出了 Alice 一共有多少种选择方案,也可以得到该测试点 60%60\% 的分数。

答案对 998244353998244353 取模。

输入格式

第一行输入两个整数 NN 和 MM。

接下来 NN 行,每行首先输入 KiK_i,接下来输入 KiK_i 个 11 到 MM 之间互不相同的数,表示玩具的编号。

输出格式

第一行一个整数,表示 Alice 一共有多少种选择方案。

第二行 n+1n+1 个整数,第 ii 个数表示 k=i−1k=i-1 的选择方案。

注意,即使你只想获得这个点 60%60\% 的分数,也需要输出第二行 n+1n+1 个整数。

输入输出样例 #1

输入 #1

3 3
3 1 2 3
3 1 2 3
3 1 2 3

输出 #1

7
0 3 3 1

输入输出样例 #2

输入 #2

5 3
2 2 3
1 1
1 3
2 1 2
1 2

输出 #2

17
0 0 3 8 5 1

输入输出样例 #3

见下发文件中的 sample3.in 和 sample3.out。

该组样例满足测试点 3∼53\sim 5 的限制。

输入输出样例 #4

见下发文件中的 sample4.in 和 sample4.out。

该组样例满足测试点 6∼86\sim 8 的限制。

输入输出样例 #5

见下发文件中的 sample5.in 和 sample5.out。

该组样例满足测试点 9∼129\sim 12 的限制。

输入输出样例 #6

见下发文件中的 sample6.in 和 sample6.out。

该组样例满足测试点 13∼1413\sim 14 的限制。

输入输出样例 #7

见下发文件中的 sample7.in 和 sample7.out。

该组样例满足测试点 15∼2015\sim 20 的限制。

说明/提示

对于 100%100\% 的数据,n≤5×105,Ki≤m≤20n\le 5 \times 10^5,K_i\le m\le 20

测试点编号 n≤n\le m≤m\le 特殊性质
1∼21\sim 2 2020 无
3∼53\sim 5 100100 1010
6∼86\sim 8 10310^3 1515
9∼129\sim 12 5×1055 \times 10^5 2020 Ki≥15K_i\ge15
13∼1413\sim 14 10510^5 1515 无
15∼2015\sim 20 5×1055 \times 10^5 2020