102261: [AtCoder]ABC226 B - Counting Arrays
Description
Score : $200$ points
Problem Statement
You are given $N$ sequences numbered $1$ to $N$.
Sequence $i$ has a length of $L_i$ and its $j$-th element $(1 \leq j \leq L_i)$ is $a_{i,j}$.
Sequence $i$ and Sequence $j$ are considered the same when $L_i = L_j$ and $a_{i,k} = a_{j,k}$ for every $k$ $(1 \leq k \leq L_i)$.
How many different sequences are there among Sequence $1$ through Sequence $N$?
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq L_i \leq 2 \times 10^5$ $(1 \leq i \leq N)$
- $0 \leq a_{i,j} \leq 10^{9}$ $(1 \leq i \leq N, 1 \leq j \leq L_i)$
- The total number of elements in the sequences, $\sum_{i=1}^N L_i$, does not exceed $2 \times 10^5$.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$
$L_1$ $a_{1,1}$ $a_{1,2}$ $\dots$ $a_{1,L_1}$
$L_2$ $a_{2,1}$ $a_{2,2}$ $\dots$ $a_{2,L_2}$
$\vdots$
$L_N$ $a_{N,1}$ $a_{N,2}$ $\dots$ $a_{N,L_N}$
Output
Print the number of different sequences.
Sample Input 1
4 2 1 2 2 1 1 2 2 1 2 1 2
Sample Output 1
3
Sample Input $1$ contains four sequences:
- Sequence $1$ : $(1, 2)$
- Sequence $2$ : $(1, 1)$
- Sequence $3$ : $(2, 1)$
- Sequence $4$ : $(1, 2)$
Except that Sequence $1$ and Sequence $4$ are the same, these sequences are pairwise different, so we have three different sequences.
Sample Input 2
5 1 1 1 1 1 2 2 1 1 3 1 1 1
Sample Output 2
4
Sample Input $2$ contains five sequences:
- Sequence $1$ : $(1)$
- Sequence $2$ : $(1)$
- Sequence $3$ : $(2)$
- Sequence $4$ : $(1, 1)$
- Sequence $5$ : $(1, 1, 1)$
Sample Input 3
1 1 1
Sample Output 3
1
Input
题意翻译
**题目描述** 给定 $N$ 个序列，第 $i$ 个序列的长度为 $L_i$ ，序列 $i$ 中含有 $L_i$ 个元素，若序列 $i$ 和 $j$ 的长度相等，且序列 $i$ 和 $j$ 中的每个元素都相同，则认为这两个序列是同一个序列，问有多少个序列。 **输入格式** 第一行输入 $N$ 。第二行到第 $N+1$ 行，每行先输入 $L_i$ 然后输入 $L_i$ 个元素，元素之间用空格隔开。 **输出格式** 输出仅一行，表示有多少个序列。 **样例解释** 例如样例一：序列 $1$ 和 $4$ 是相同的两个相同序列，所以我们认为他是同一个序列。没有与序列 $2$ 和 $3$ 相同的序列，所以它们各算作一个序列，故一共有三个序列。Output
得分：200分
问题描述
你有编号为1到N的N个序列。
序列i的长度为L_i，它的第j个元素（1≤j≤L_i）为a_{i,j}。
当L_i = L_j并且对于所有的k（1≤k≤L_i）有a_{i,k} = a_{j,k}时，序列i和序列j被认为是相同的。
在序列1到序列N之间有多少个不同的序列？
限制条件
- 1≤N≤2×10^5
- 1≤L_i≤2×10^5 （1≤i≤N）
- 0≤a_{i,j}≤10^{9} （1≤i≤N, 1≤j≤L_i）
- 序列中的元素总数，即∑_{i=1}^N L_i，不超过2×10^5。
- 输入中的所有值都是整数。
输入
输入以以下格式从标准输入给出：
$N$
$L_1$ $a_{1,1}$ $a_{1,2}$ $\dots$ $a_{1,L_1}$
$L_2$ $a_{2,1}$ $a_{2,2}$ $\dots$ $a_{2,L_2}$
$\vdots$
$L_N$ $a_{N,1}$ $a_{N,2}$ $\dots$ $a_{N,L_N}$
输出
打印不同的序列数量。
样例输入1
4 2 1 2 2 1 1 2 2 1 2 1 2
样例输出1
3
样例输入1包含四个序列：
- 序列1：(1, 2)
- 序列2：(1, 1)
- 序列3：(2, 1)
- 序列4：(1, 2)
除了序列1和序列4相同之外，这些序列是两两不同的，所以我们有三个不同的序列。
样例输入2
5 1 1 1 1 1 2 2 1 1 3 1 1 1
样例输出2
4
样例输入2包含五个序列：
- 序列1：(1)
- 序列2：(1)
- 序列3：(2)
- 序列4：(1, 1)
- 序列5：(1, 1, 1)
样例输入3
1 1 1
样例输出3
1