← 返回题目列表

AtCoder · abc226_b

C. 计数数组

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

你被给予 N 序列编号 1 to N.
序列 i 的长度为 L_i 及其 j- 第一个元素 (1 \leq j \leq L_i) is a_{i,j}.

序列 i 和序列 j 被认为是相同的 L_i = L_j 和 a_{i,k} = a_{j,k} 对于每个 k (1 \leq k \leq L_i).
Sequence中有多少个不同的序列 1 通过序列 N?

约束

  • 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)
  • 序列中元素的总数, \sum_{i=1}^N L_i,不超过 2 \times 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