← 返回题目列表

AtCoder · past202010_k

K. 跌倒次数

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

分数: 6 点

警告

2020 年 11 月 8 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

你有 K 调用的数字序列 a_1 通过 a_K。 序列的长度 a_i is n_i,及其 j第一个元素是 a_{i,j}.

使用这些序列,您决定制作一个新序列 x。 最初,长度为 x is 0.

你会做 Q 操作。 在 i- 第一个,您将替换 x 与连接序列的结果 a_{b_i} 到年底 x.

让 |x| 表示长度 x。 查找整数对的数量 (i,j) 这样 1 \leq i < j \leq |x| 和 x_i > x_j 完成所有操作后。 因为它可能很大,所以打印它的模 10^9.

约束

  • 输入中的所有值都是整数。
  • 1 \leq K,Q \leq 10^5
  • 1 \leq n_i \leq 10^5
  • 1 \leq a_{i,j} \leq 20
  • 1 \leq b_i \leq K
  • \sum_{i=1}^{K} n_i \leq 3 \times 10^5

输入

输入由标准输入按以下格式给出:

K
n_1
a_{1,1} a_{1,2} \cdots a_{1,{n_1}}
n_2
a_{2,1} a_{2,2} \cdots a_{2,{n_2}}
\vdots
n_K
a_{K,1} a_{K,2} \cdots a_{K,{n_K}}
Q
b_1 b_2 \cdots b_Q

输出

打印整数对的数量 (i,j) 这样 1 \leq i < j \leq |x| 和 x_i > x_j 所有运算后,取模 10^9.


样本输入 1

2
3
1 3 2
2
5 4
2
1 2

示例输出 1

2
  • 最初, 黑板上写着 x 为空。
  • 在 1-st 操作, x 被替换为串联 x 和 (1,3,2),即 (1,3,2).
  • 在 2-st 操作, x 被替换为串联 x 和 (5,4),即 (1,3,2,5,4).
  • 现在有两对 (i,j) 这样 1 \leq i < j \leq |x| 和 x_i > x_j: (2,3) 和 (4,5).

示例输入 2

10
8
16 6 15 10 18 13 17 11
13
4 10 6 4 14 17 13 9 3 9 4 8 14
11
11 17 12 3 13 8 10 11 18 2 19
10
18 11 16 19 4 17 7 3 5 8
3
3 10 9
13
8 17 20 8 20 1 5 17 4 16 18 20 4
15
11 2 1 16 8 17 4 7 3 6 4 13 16 16 16
2
12 12
8
7 14 7 5 8 17 19 4
15
3 6 1 16 11 5 3 15 9 15 12 15 5 19 7
20
4 3 7 6 1 8 2 3 9 8 6 3 10 9 7 7 3 2 2 10

示例输出 2

12430