#ABC226B. [ABC226B] Counting Arrays

    ID: 2721 Type: Default 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>STLABC入门算法闯关STL与数据结构

[ABC226B] Counting Arrays

题目背景

翻译自「AtCoder ABC226B」

题目描述

给定 NN 个序列,第 ii 个序列的长度为 LiL_i ,序列 ii 中含有 LiL_i 个元素,其第 jj 个元素(1jLi1\le j \le L_i)是 ai,ja_{i,j}

若序列 iijj 的长度相等,且序列 iijj 中的每个元素都相同,则认为这两个序列是同一个序列,问有多少个不同的序列。

输入格式

第一行输入一个整数 NN

第二行到第 N+1N+1 行,每行先输入 LiL_i 然后输入 LiL_i 个元素,元素之间用空格隔开。

输出格式

输出仅一行,表示有多少个 不同的序列。

样例

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

说明/提示

样例 1 解释

样例输入 11 包含四个序列:

  • 序列 11(1,2)(1, 2)

  • 序列 22(1,1)(1, 1)

  • 序列 33(2,1)(2, 1)

  • 序列 44(1,2)(1, 2)

除了序列 11 和序列 44 相同外,这些序列两两不同,所以共有三个不同的序列。

样例 2 解释

样例输入 22 包含五个序列:

  • 序列 11(1)(1)

  • 序列 22(1)(1)

  • 序列 33(2)(2)

  • 序列 44(1,1)(1, 1)

  • 序列 55(1,1,1)(1, 1, 1)

数据范围

$1\le N \le 2\times 10^5,1\le L_i \le 2\times 10^5,0\le a_{i,j}\le 10^9$。

所有序列的元素总数 i=1NLi\sum_{i=1}^N L_i 不超过 2×1052\times 10^5