分数: 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