/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1 以上 10^5 以下の整数から成る、長さ N の整数列 S と 長さ M の整数列 T が与えられます。
S の部分列と T の部分列の組であって、整数列として等しいような組は何通りあるでしょうか。
ただし、整数列 A の部分列とは、A の要素を 0 個以上いくつか選んで削除し、残ったものを元の順序を保って並べた整数列を表します。
また、S, T それぞれの部分列は、整数列として等しい場合でも、削除した要素の添字の集合が異なる場合には異なる部分列として区別してください。
答えは非常に大きくなることがあるので、10^9+7 で割った余りを出力してください。
制約
- 1 \leq N, M \leq 2 \times 10^3
- S の長さは N である
- T の長さは M である
- 1 \leq S_i, T_i \leq 10^5
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
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 で割った余りを出力せよ。
入力例 1
2 2 1 3 3 1
出力例 1
3
S の部分列としては (), (1), (3), (1, 3) が考えられます。
T の部分列としては (), (3), (1), (3, 1) が考えられます。
共に部分列が () である組は 1 \times 1 通り、共に部分列が (1) である組は 1 \times 1 通り、共に部分列が (3) である組は 1 \times 1 通り考えられるので、合計 3 通りの組が存在します。
入力例 2
2 2 1 1 1 1
出力例 2
6
S の部分列としては (), (1), (1), (1, 1) が考えられます。
T の部分列としては (), (1), (1), (1, 1) が考えられます。
共に部分列が () である組は 1 \times 1 通り、共に部分列が (1) である組は 2 \times 2 通り、共に部分列が (1, 1) である組は 1 \times 1 通り考えられるので、合計 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
個数を 10^9+7 で割った余りを出力することに注意してください。
Score : 500 points
Problem Statement
You are given two integer sequences S and T of length N and M, respectively, both consisting of integers between 1 and 10^5 (inclusive).
In how many pairs of a subsequence of S and a subsequence of T do the two subsequences are the same in content?
Here the subsequence of A is a sequence obtained by removing zero or more elements from A and concatenating the remaining elements without changing the order.
For both S and T, we distinguish two subsequences if the sets of the indices of the removed elements are different, even if the subsequences are the same in content.
Since the answer can be tremendous, print the number modulo 10^9+7.
Constraints
- 1 \leq N, M \leq 2 \times 10^3
- The length of S is N.
- The length of T is M.
- 1 \leq S_i, T_i \leq 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
S_1 S_2 ... S_{N-1} S_{N}
T_1 T_2 ... T_{M-1} T_{M}
Output
Print the number of pairs of a subsequence of S and a subsequence of T such that the subsequences are the same in content, modulo 10^9+7.
Sample Input 1
2 2 1 3 3 1
Sample Output 1
3
S has four subsequences: (), (1), (3), (1, 3).
T has four subsequences: (), (3), (1), (3, 1).
There are 1 \times 1 pair of subsequences in which the subsequences are both (), 1 \times 1 pair of subsequences in which the subsequences are both (1), and 1 \times 1 pair of subsequences in which the subsequences are both (3), for a total of three pairs.
Sample Input 2
2 2 1 1 1 1
Sample Output 2
6
S has four subsequences: (), (1), (1), (1, 1).
T has four subsequences: (), (1), (1), (1, 1).
There are 1 \times 1 pair of subsequences in which the subsequences are both (), 2 \times 2 pairs of subsequences in which the subsequences are both (1), and 1 \times 1 pair of subsequences in which the subsequences are both (1,1), for a total of six pairs. Note again that we distinguish two subsequences if the sets of the indices of the removed elements are different, even if the subsequences are the same in content.
Sample Input 3
4 4 3 4 5 6 3 4 5 6
Sample Output 3
16
Sample Input 4
10 9 9 6 5 7 5 9 8 5 6 7 8 6 8 5 5 7 9 9 7
Sample Output 4
191
Sample Input 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
Sample Output 5
846527861
Be sure to print the number modulo 10^9+7.