Common Subsequence

题目描述

给你两个整数序列 $S$ 和 $T$，长度分别为 $N$ 和 $M$，两者的元素均为 $1$ 到 $10^5$（包含端点）之间的整数。 有多少对由 $S$ 的一个子序列与 $T$ 的一个子序列组成的配对，使得这两个子序列在内容上相同？ 这里，$A$ 的子序列是通过从 $A$ 中删除零个或多个元素并在不改变相对顺序的情况下将剩余元素连接起来得到的序列。 对于 $S$ 和 $T$ 的子序列，如果被删除元素的索引集合不同，即使子序列的内容相同，我们也将其视为不同的子序列。 由于答案可能非常大，请输出答案对 $10^9+7$ 取模的结果。

输入格式

输入按下列格式从标准输入给出： $N$ $M$ $S_1$ $S_2$ $...$ $S_{N-1}$ $S_{N}$ $T_1$ $T_2$ $...$ $T_{M-1}$ $T_{M}$

输出格式

打印满足子序列在内容上相同的 $S$ 的一个子序列和 $T$ 的一个子序列的配对数量，对 $10^9+7$ 取模。

2 2
1 3
3 1

3

2 2
1 1
1 1

6

4 4
3 4 5 6
3 4 5 6

16

10 9
9 6 5 7 5 9 8 5 6 7
8 6 8 5 5 7 9 9 7

191

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

846527861

提示

$1 \leq N, M \leq 2 \times 10^3$ 序列 $S$ 的长度为 $N$。 序列 $T$ 的长度为 $M$。
$1 \leq S_i, T_i \leq 10^5$ 输入中的所有数值均为整数。$S$ 有四个子序列： $(), (1), (3), (1, 3)$。 $T$ 有四个子序列： $(), (3), (1), (3, 1)$。 存在 $1 \times 1$ 对子序列两者均为 $()$ 的配对，$1 \times 1$ 对两者均为 $(1)$ 的配对，以及 $1 \times 1$ 对两者均为 $(3)$ 的配对，总计三对。
$S$ 有四个子序列： $(), (1), (1), (1, 1)$。 $T$ 有四个子序列： $(), (1), (1), (1, 1)$。 存在 $1 \times 1$ 对子序列两者均为 $()$ 的配对，$2 \times 2$ 对两者均为 $(1)$ 的配对，以及 $1 \times 1$ 对两者均为 $(1,1)$ 的配对，总计六对。 再次注意，如果被删除元素的索引集合不同，即使子序列内容相同，我们也将其视为不同的子序列。
请务必对 $10^9+7$ 取模后输出答案。

标签: AtCoder|abc130E

来源

AtCoder|abc130E