← 返回题目
题库练习 公共子序列对
← 上一题 下一题 →

A6966 | 公共子序列对

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

小明有两个整数序列，分别是长度为 $N$ 的序列 $S$ 和长度为 $M$ 的序列 $T$。序列中的元素均为 $1$ 到 $10^5$ 之间的整数。

小明想知道，有多少对 $(s', t')$ 满足以下条件：

1. $s'$ 是 $S$ 的一个子序列。
2. $t'$ 是 $T$ 的一个子序列。
3. $s'$ 和 $t'$ 的内容完全相同（即长度相等，且对应位置的元素值相等）。

**注意：**

- 子序列是指从原序列中删除 $0$ 个或多个元素，保留剩余元素相对顺序组成的新序列。
- 在本题中，即使两个子序列的内容完全相同，但如果它们是由原序列中**不同下标**的元素组成的，也被视为不同的子序列。例如，对于 $S = (1, 1)$，取第一个 $1$ 和取第二个 $1$ 形成的子序列内容都是 $(1)$，但它们被视为两个不同的子序列。
- 空序列也是一种合法的子序列。

由于答案可能非常大，请输出答案对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示序列 $S$ 和序列 $T$ 的长度。

第二行包含 $N$ 个整数 $S_1, S_2, \dots, S_N$，表示序列 $S$ 的元素。

第三行包含 $M$ 个整数 $T_1, T_2, \dots, T_M$，表示序列 $T$ 的元素。

输出格式

输出一个整数，表示满足条件的子序列对 $(s', t')$ 的数量，结果对 $10^9 + 7$ 取模。

输入输出样例

输入 #1
2 2
1 3
3 1
输出 #1
3
输入 #2
2 2
1 1
1 1
输出 #2
6
输入 #3
4 4
3 4 5 6
3 4 5 6
输出 #3
16
输入 #4
10 9
9 6 5 7 5 9 8 5 6 7
8 6 8 5 5 7 9 9 7
输出 #4
191
输入 #5
20 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
输出 #5
846527861
C++ 编辑器
输入
输出