#P14506. [2026年省队模拟联测]玩具

    ID: 13723 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500状压DP分治数学前缀和动态规划枚举模拟

[2026年省队模拟联测]玩具

题目描述

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

Alice 决定从中选择一些箱子,将箱子中的玩具聚拢在一起,再去掉重复的玩具,将这些玩具组成一个新的玩具箱子。

你需要求出 Alice 最后能得到多少种不同的玩具箱子。

两种玩具箱子不同当且仅当存在一种玩具,使得他在一种玩具箱子中出现了,而在另一种玩具箱子中并没有出现。

注意,即使 Alice 什么都不选,也是一种方案。

输入格式

第一行输入两个整数 NNMM

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

输出格式

一行一个整数,表示 Alice 最后能得到多少种不同的玩具箱子。

样例输入和输出

输入样例1

3 4
2 1 3 
3 1 2 3 
1 2 

输出样例1

4

说明/提示

对于 100%100\% 的数据,n5×105,KiM28n\le 5 \times 10^5,K_i\le M\le 28

测试点编号 nn\le mm\le
121\sim 2 1616 1010
343\sim 4 10001000 1313
575\sim 7 5×1055\times 10^5 2020
8108\sim 10 2626
111611\sim 16 2727
172017\sim 20 2828