Problem:


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.



Sample input:
2 2
1 3
3 1


Sample output:
3

Submission status: Accepted

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

""" convenient functions
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
# accumulate() returns iterator! to get list: list(accumulate())
from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    # TODO: How should I do when n - r is negative?
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    # flat = [flatten for inner in data for flatten in inner]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
"""

# functions used
r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]
"""

# set inputs
# sys.stdin = open('sample.txt') # for test

N, M = R()
S = R()
T = R()

dp = [[0]*(M+1) for _ in range(N+1)] #dp[N][M]
dp_sum = [[1]*(M+1) for _ in range(N+1)]

dp[0][0] = 1
dp_sum[0][0] = 1

for i, j in product(range(N), range(M)):
    if S[i] == T[j]:
        dp[i+1][j+1] = dp_sum[i][j] % MOD
    else:
        dp[i+1][j+1] = 0
    dp_sum[i+1][j+1] = (dp_sum[i+1][j] + dp_sum[i][j+1] - dp_sum[i][j] + dp[i+1][j+1]) % MOD

print(dp_sum[N][M])

"""memo: how to use defaultdict of list
# initialize
Dic = defaultdict(list)
# append
Dic[x].append(y)
# for
for k, v in Dic.items():
"""

# if __name__ == '__main__':
#     main()

Submission status: Accepted

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

""" convenient functions
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
# accumulate() returns iterator! to get list: list(accumulate())
from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    # TODO: How should I do when n - r is negative?
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    # flat = [flatten for inner in data for flatten in inner]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
"""

# functions used
r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]
"""

# set inputs
# sys.stdin = open('sample.txt') # for test

N, M = R()
S = R()
T = R()

dp = [[0]*(M+1) for _ in range(N+1)] #dp[N][M]
dp_sum = [[1]*(M+1) for _ in range(N+1)]

dp[0][0] = 1
dp_sum[0][0] = 1

for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp_sum[i][j] % MOD
        else:
            dp[i+1][j+1] = 0
        dp_sum[i+1][j+1] = (dp_sum[i+1][j] + dp_sum[i][j+1] - dp_sum[i][j] + dp[i+1][j+1]) % MOD

print(dp_sum[N][M])

"""memo: how to use defaultdict of list
# initialize
Dic = defaultdict(list)
# append
Dic[x].append(y)
# for
for k, v in Dic.items():
"""


# if __name__ == '__main__':
#     main()

Submission status: Accepted

Solution code:
mo=10**9+7
n,m=map(int,input().split())
s=[0]+[int(i) for i in input().split()]
t=[0]+[int(i) for i in input().split()]
dp=[[0]*(1+n) for i in range(1+m)]
sm=[[0]*(1+n) for i in range(1+m)]

for i in range(1,1+m):
    if t[i]==s[1]:
        dp[i][1]=1
    sm[i][1]=sm[i-1][1]+dp[i][1]%mo

for i in range(1,1+n):
    if s[i]==t[1]:
        dp[1][i]=1
    sm[1][i]=sm[1][i-1]+dp[1][i]%mo

for i in range(2,1+m):
    for j in range(2,1+n):
        dp[i][j]=1+sm[i-1][j-1] if t[i]==s[j] else 0
        sm[i][j]=dp[i][j]+sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]
        sm[i][j]%=mo

print(1+sm[m][n]%mo)

Submission status: Accepted

Solution code:
mod = 10**9+7
n, m = list(map(int,input().split()))
s = list(map(int,input().split()))
t = list(map(int,input().split()))
dp = [0]*(m+1)
for i in range(n)[::-1]:
    old = 0
    for j in range(m)[::-1]:
        tmp = dp[j] + dp[j+1] - old
        tmp %= mod
        if s[i]== t[j]:
            tmp += 1 + old
            tmp %= mod
        dp[j], old = tmp, dp[j]
print((dp[0]+1)%mod)

Submission status: Accepted

Solution code:
D = 10**9+7
N, M = list(map(int,raw_input().split()))
S = list(map(int,raw_input().split()))
T = list(map(int,raw_input().split()))
a = [[0 for j in xrange(M+1)] for i in xrange(N+1)]
for i in xrange(N+1):
  a[i][0] = 1
for j in xrange(M+1):
  a[0][j] = 1
for i in xrange(N):
  for j in xrange(M):
    a[i+1][j+1] = (a[i][j+1]+a[i+1][j])%D
    if S[i]!=T[j]:
      a[i+1][j+1] = (a[i+1][j+1]-a[i][j])%D
print(a[N][M])

Submission status: Accepted

Solution code:
import numpy as np

N, M = list(map(int, input().split()))
S = list(map(int, input().split()))
T = np.array(list(map(int, input().split())))

dp = np.ones(M+1, dtype='int64')

for s in S:
    dp[1:] = ((dp[:-1] * (s == T)).cumsum() + dp[1:]) % (10**9+7)
print(dp[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

A = []
B = []
mod = 10**9 + 7

for i in range(N):
    if S[i] in T:
        A.append(S[i])

for i in range(M):
    if T[i] in S:
        B.append(T[i])        
        
l1 = [1] * (N + 1)

for i, t in enumerate(T):
    l2 = l1[:]
    k = 0
    for j, s in enumerate(S):
        if t == s:
            k += l1[j]
        l2[j + 1] = (l1[j + 1] + k) % mod
    l1 = l2
print(l1[-1])

Submission status: Accepted

Solution code:
DIVS = 1000000007
def LI(): return [int(x) for x in input().split()]

N,M=LI()
SS=LI()
TT=LI()

dp=[[0]*(M+1) for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(1,M+1):
        if SS[i-1] != TT[j-1]:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] + 1) % DIVS

print((dp[N][M]+1)%DIVS)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

mod = 10 ** 9 + 7
dp = [[0] * (M + 1) for _ in range(N + 1)]

for i in range(N + 1):
	for j in range(M + 1):
		if i == 0 or j == 0:
			dp[i][j] = 1
		elif S[i - 1] == T[j - 1]:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
		else:
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % mod
			
print(dp[N][M])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

mod = 10 ** 9 + 7

dp = [[0 for i in range(M+1)] for i in range(N+1)]

for i in range(1, N+1):
    for j in range(1, M+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = (1 + dp[i-1][j] + dp[i][j-1]) % mod
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % mod

print((dp[-1][-1] + 1) % mod)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[int(i) for i in input().split()]
t=[int(i) for i in input().split()]
mod=10**9+7
dp=[[0 for i in range(m+1)]for j in range(n+1)]
for i in range(n):
    for j in range(m):
        x=0
        if s[i]==t[j]:
            x=dp[i][j]+1
        dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1]-dp[i][j]+x)%mod

print((dp[n][m]+1)%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
MOD = 1000000007  # type: int


def solve(N: int, M: int, S: "List[int]", T: "List[int]"):

    DP = [[1]*(N+1) for _ in range(M+1)]
    for j in range(1, M+1):
        for i in range(1, N+1):
            DP[j][i] = DP[j-1][i] + DP[j][i-1] - \
                DP[j-1][i-1]
            DP[j][i] %= MOD

            if S[i-1] == T[j-1]:
                DP[j][i] += DP[j-1][i-1]
                DP[j][i] %= MOD
    # print(*DP, sep="\n")
    print(DP[M][N])


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    T = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, S, T)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10 ** 9 + 7

dp = [[0] * (M + 1) for i in range(N + 1)]
dp_sum = [[0] * (M + 1) for i in range(N + 1)]

dp[0][0] = 1
for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        if s == t:
            dp[i][j] = dp_sum[i - 1][j - 1] + 1
            dp[i][j] %= MOD
        dp_sum[i][j] = dp_sum[i - 1][j] + dp_sum[i][j - 1] - dp_sum[i - 1][j - 1] + dp[i][j]
        dp_sum[i][j] %= MOD

ans = 0
for i in range(N + 1):
    for j in range(M + 1):
        ans += dp[i][j]
        ans %= MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10 ** 9 + 7

dp = [[0] * (M + 1) for i in range(N + 1)]
dp_sum = [[0] * (M + 1) for i in range(N + 1)]

for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        if s == t:
            dp[i][j] = (dp_sum[i - 1][j - 1] + 1) % MOD
        dp_sum[i][j] = dp_sum[i - 1][j] + dp_sum[i][j - 1] - dp_sum[i - 1][j - 1] + dp[i][j]
        dp_sum[i][j] %= MOD

ans = 0
for i in range(N + 1):
    for j in range(M + 1):
        ans += dp[i][j]
        ans %= MOD

print((ans + 1) % MOD)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[int(i) for i in input().split()]
t=[int(i) for i in input().split()]
mod=10**9+7
dp=[[0 for i in range(m+1)]for j in range(n+1)]
for i in range(n):
    for j in range(m):
        x=0
        if s[i]==t[j]:
            x=dp[i][j]+1
        dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1]-dp[i][j]+x)%mod
#print(dp)
print((dp[n][m]+1)%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def main():

    import sys

    def input(): return sys.stdin.readline().strip()
    def list2d(a, b, c): return [[c] * b for i in range(a)]
    def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
    def ceil(x, y=1): return int(-(-x // y))
    def INT(): return int(input())
    def MAP(): return map(int, input().split())
    def LIST(): return list(map(int, input().split()))
    def Yes(): print('Yes')
    def No(): print('No')
    def YES(): print('YES')
    def NO(): print('NO')
    sys.setrecursionlimit(10 ** 9)
    INF = float('inf')
    MOD = 10 ** 9 + 7

    N,M=MAP()
    S=LIST()
    T=LIST()

    # dp1[i][j], dp2[i][j] := Sをi文字目、Tをj文字目まで考えた時、dp1はi方向、dp2はj方向に遷移させる
    dp1=list2d(N+2, M+2, 0)
    dp2=list2d(N+2, M+2, 0)
    dp1[0][0]=1
    for i in range(N+1):
        for j in range(M+1):
            dp1[i][j]%=MOD
            # 数え上げをi方向とj方向で重複がないように遷移させる
            dp1[i+1][j]+=dp1[i][j]
            dp2[i][j]+=dp1[i][j]
            dp2[i][j+1]+=dp2[i][j]
            # 今回増やす数値が一致するなら
            if i<N and j<M and S[i]==T[j]:
                # 斜めに遷移させる(1→0)
                dp1[i+1][j+1]+=dp2[i][j]
    print((dp2[N][M])%MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():

    N,M=MAP()
    S=LIST()
    T=LIST()

    # dp1[i][j], dp2[i][j] := Sをi文字目、Tをj文字目まで考えた時、dp1はi方向、dp2はj方向に遷移させる
    dp1=list2d(N+2, M+2, 0)
    dp2=list2d(N+2, M+2, 0)
    dp1[0][0]=1
    for i in range(N+1):
        for j in range(M+1):
            dp1[i][j]%=MOD
            # 数え上げをi方向とj方向で重複がないように遷移させる
            dp1[i+1][j]+=dp1[i][j]
            dp2[i][j]+=dp1[i][j]
            dp2[i][j+1]+=dp2[i][j]
            # 今回増やす数値が一致するなら
            if i<N and j<M and S[i]==T[j]:
                # 斜めに遷移させる(1→0)
                dp1[i+1][j+1]+=dp2[i][j]
    print((dp2[N][M])%MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
MOD = 1000000007  # type: int


def solve(N: int, M: int, S: "List[int]", T: "List[int]"):

    DP = [[1]*(N+1) for _ in range(M+1)]
    for i in range(1, N+1):
        for j in range(1, M+1):
            DP[j][i] = DP[j-1][i] + DP[j][i-1] - \
                DP[j-1][i-1]
            DP[j][i] %= MOD

            if S[i-1] == T[j-1]:
                DP[j][i] += DP[j-1][i-1]
                DP[j][i] %= MOD
    # print(*DP, sep="\n")
    print(DP[M][N])


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    T = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, S, T)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = list(input().split())
T = list(input().split())
MOD = 10**9+7
dp = [[0] * (M+1) for _ in range(N+1)]
sum = [[0] * (M+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N+1):
    sum[i][0] = 1
for j in range(M+1):
    sum[0][j] = 1
for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            dp[i+1][j+1] = sum[i][j]
        sum[i+1][j+1] = (sum[i+1][j] + sum[i][j+1] - sum[i][j] + dp[i+1][j+1]) % MOD
print(sum[N][M])

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
N, M = inpl()
S = [0] + inpl()
T = [0] + inpl()

DP = [[1]*(N+1) for _ in range(M+1)]

for i in range(1, M+1):
    for j in range(1, N+1):
        if S[j] == T[i]:
            DP[i][j] = (DP[i][j-1] + DP[i-1][j])%MOD
        else:
            DP[i][j] = (DP[i][j-1] + DP[i-1][j] - DP[i-1][j-1])%MOD
print(DP[-1][-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, M = i2nn()
    S = i2nn()
    T = i2nn()

    rui = [[0] * (M + 1) for _ in range(N + 1)]
    #cnt = [[0] * (M) for _ in range(N)]

    n = 1
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            c = 0
            if s == t:
                c += rui[i][j] + 1
            #cnt[i][j] = c
            rui[i+1][j+1] = (rui[i+1][j] + rui[i][j+1] - rui[i][j] + c) % MOD
            n = (n + c) % MOD

    #for v in cnt:
    #    n = (n + sum(v)) % MOD

    #print(rui)
    #print(cnt)
    print(n)

main()