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:
# 入力
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))


MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


# LCSと同様にDPで解を求める
dp = [[ModInt(1) for _ in range(M + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, M + 1):
        dp[i][j] = (
            dp[i - 1][j] + dp[i][j - 1] if S[i - 1] == T[j - 1] else
            dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
        )
ans = dp[N][M]

# 出力
print(ans)

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


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


# LCSと同様にDPで解を求める
dp = [[ModInt(1) for _ in range(M + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, M + 1):
        dp[i][j] = (
            dp[i - 1][j] + dp[i][j - 1] if S[i - 1] == T[j - 1] else
            (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1])
        )
ans = dp[N][M]

# 出力
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N,M = map(int,input().split())
MOD = 1e9 + 7
S = np.array(input().split())
T = np.array(input().split())

dp = np.zeros((N+1,M+1))
dp[0] = 1

for n in range(1,N+1):
    same = (T == S[n-1])
    dp[n,1:][same] = dp[n-1,:-1][same]
    dp[n] = (dp[n].cumsum() + dp[n-1])%MOD
    
print(int(dp[N,M]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from pprint import pprint

MOD = 1000000007  # type: int

def solve(N: int, M: int, S: "List[int]", T: "List[int]"):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1
    for i in range(N):
        for j in range(M):
            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
            if not S[i] == T[j]:
                dp[i + 1][j + 1] -= dp[i][j]
            dp[i + 1][j + 1] %= MOD
    #pprint(dp)
    ret = dp[N][M]
    print(ret)
    return


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:
# coding: utf-8
import sys
input = sys.stdin.readline

MOD = int(1e9 + 7)

def f(N, M, s, t):
    cums = [[0] * (M + 1) for _ in range(N + 1)]

    for i in range(N):
        cumsi = cums[i]
        cumsi1 = cums[i+1]
        for j in range(M):
            num = 0
            if s[i] == t[j]:
                num = cumsi[j] + 1
            cumsi1[j+1] = \
                (cumsi1[j] + cumsi[j+1] - cumsi[j] + num) % MOD
    return((cums[N][M] + 1) % MOD)

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = [int(i) for i in input().split()]+['g']
T = [int(i) for i in input().split()]+['a']

MOD = 10 ** 9 + 7

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

for i in range(N + 1) :
    dp[i][0] = 1
for i in range(M + 1) :
    dp[0][i] = 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] = (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:
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, M = inpl()
S = inpl()
T = inpl()

total = [0]*(N+1)*(M+1)
for i in range(N):
	for j in range(M):
		if S[i] == T[j]:
			n = total[(M+1)*i+j] + 1
		else:
			n = 0
		total[(M+1)*(i+1)+(j+1)] = (n + total[(M+1)*i+(j+1)] + total[(M+1)*(i+1)+j] - total[(M+1)*i+j]) % MOD
print((total[-1]+1) % MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
MOD = int(1e9 + 7)

def f(N, M, s, t):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    cums = [[0] * (M + 1) for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, M + 1):
            dp[i][j] = 0 if s[i-1] != t[j-1] else (cums[i-1][j-1] + 1) % MOD
            cums[i][j] = cums[i-1][j] + cums[i][j-1] - cums[i-1][j-1] + dp[i][j]
    return((cums[N][M] + 1) % MOD)

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i - 1] == b[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[n][m] + 1) % MOD)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

MOD = 10 ** 9 + 7
N, M = list(map(int, sys.stdin.readline().split()))
S = list(map(int, sys.stdin.readline().split()))
T = list(map(int, sys.stdin.readline().split()))
S = np.array([-1] + S)
T = np.array([-1] + T)

# # dp[i][j]: S[i] と T[j] で終わる組み合わせの数
# # S[i] != T[j] のとき 0
# # S[i] == T[j] のとき、sum(dp[:i][:j])
# dp = np.zeros((len(S), len(T)), dtype=int)
# dp[0][0] = 1
# # dp の二次元累積和
# cumsum = np.ones(len(T), dtype=int)
# for i in range(1, len(S)):
#     for j in range(1, len(T)):
#         if S[i] != T[j]:
#             continue
#         # dp[i][j] = dp[:i, :j].sum() % MOD
#         dp[i][j] = cumsum[j - 1] % MOD
#     cumsum += dp[i].cumsum()
#     cumsum %= MOD
# print(cumsum[-1])


cumsum = np.ones(len(T), dtype=int)
for i in range(1, len(S)):
    cumsum[1:] += ((T == S[i])[1:] * cumsum[:-1] % MOD).cumsum()
    cumsum %= MOD
print(cumsum[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

MOD = 10**9 + 7

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 1
for j in range(m + 1):
    dp[0][j] = 1

for i in range(n):
    for j in range(m):
        dp[i + 1][j + 1] += dp[i + 1][j]
        dp[i + 1][j + 1] += dp[i][j + 1]
        dp[i + 1][j + 1] += -dp[i][j]
        if s[i] == t[j]:
            dp[i + 1][j + 1] += dp[i][j]
        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] * (M + 1) for i in range(N + 1)]
s = [[0] * (M + 1) for i in range(N + 1)]
dp[0][0] = 1

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

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

Submission status: Accepted

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

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

for i in range(1,N+1) :
    for j in range(1,M+1) :
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - (dp[i-1][j-1] if S[i-1] != T[j-1] else 0)
        dp[i][j] %= 10**9+7
ans = dp[N][M]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def e_common_subsequence(N, M, S, T, MOD=10**9 + 7):
    # dp[i][j]: S[i], T[j] まで考慮したとき、この2つをペアにしたときの場合の数
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    total = [[0] * (M + 1) for _ in range(N + 1)]

    ans = 1  # 空の列は常に等しい列である
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = (total[i][j] + 1) % MOD
                ans = (ans + dp[i + 1][j + 1]) % MOD
            total[i + 1][j + 1] = (total[i][j + 1] + total[i + 1][j]
                                   - total[i][j] + dp[i + 1][j + 1] + MOD) % MOD
    return ans

N, M = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
print(e_common_subsequence(N, M, S, T))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s_list = list(map(int, input().split()))
t_list = list(map(int, input().split()))

mod = 10 ** 9 + 7


def solve(x, y):
    dp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] += dp[i - 1][j - 1] + 1
                dp[i][j] %= mod
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
            dp[i][j] %= mod

    return dp


ans = solve(s_list, t_list)
print((ans[N][M] + 1) % mod)

Submission status: Accepted

Solution code:
M = int(1e+9 + 7)


def main():
  input()
  s = list(map(int, input().split()))
  t = list(map(int, input().split()))
  z = [0] * len(t)

  for v in s:
    c = 0

    for i, w in enumerate(t):
      y = z[i]

      if v == w:
        z[i] = (z[i] + c + 1) % M

      c = (c + y) % M

  y = 0

  for v in z:
    y = (y + v) % M

  y = (y + 1) % M

  print(y)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, M = mi()
Ss = list(mi())
Ts = list(mi())
slen = len(Ss)
tlen = len(Ts)

#DPを2つ作る
#1スタートにしておく。0は、for分でindexエラーを出さないために使う
DP_pairs = [[0] * (len(Ts)+1) for _ in range(len(Ss)+1)] #末尾がS[i]==T[j]である共通部分列の数
DP_cumsum = [[0] * (len(Ts)+1) for _ in range(len(Ss)+1)] #二次元累積和


for i, s in enumerate(Ss):
  i += 1 #1スタート
  for j, t in enumerate(Ts):
    j += 1 #1スタート
    if s==t:
      DP_pairs[i][j] = DP_cumsum[i-1][j-1] + 1
    #s!=tの場合はほっといてもDP_pairsが0なので何もする必要なし
    DP_cumsum[i][j] = (DP_cumsum[i][j-1]+DP_cumsum[i-1][j]-DP_cumsum[i-1][j-1]+DP_pairs[i][j])%(10**9+7)

print(DP_cumsum[len(Ss)][len(Ts)]+1)

Submission status: Accepted

Solution code:
N,M=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)]
mod=10**9+7
for n in range(1,N+1):
    for m in range(1,M+1):
        x=1 if S[n-1]==T[m-1] else -dp[n-1][m-1]
        y=dp[n-1][m]+dp[n][m-1]+x
        dp[n][m]=y if y<mod else y-mod
print((dp[-1][-1]+1)%mod)

Submission status: Accepted

Solution code:
from functools import reduce

NNN = 10 ** 9 + 7


def main():
    N, M = [int(a) for a in input().split()]
    S = [int(a) for a in input().split()]
    T = [int(a) for a in input().split()]

    table = [0] * M

    for si in reversed(S):
        c = 0
        for i in reversed(range(M)):
            prev_score = table[i]
            if T[i] == si:
                table[i] = (table[i] + c + 1) % NNN
            c = (c + prev_score) % NNN

    s = 1
    for a in table:
        s = (s + a) % NNN
    print(s)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

N, M = list(map(int, input().rstrip().split(' ')))
S = list(map(int, input().rstrip().split(' ')))
T = list(map(int, input().rstrip().split(' ')))
dp = [[0] * (N + 1) for _ in range(M + 1)]

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

Submission status: Accepted

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

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

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

for j in range(M + 1):
    dp[0][j] = 1

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

Submission status: Accepted

Solution code:
def e_common_subsequence(N, M, S, T, MOD=10**9 + 7):
    # dp[i][j]: S[i], T[j] まで考慮したとき、この2つをペアにしたときの場合の数
    dp = [[0] * (M + 1) for _ in range(N + 1)]

    total = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        total[i][0] = 1
    for j in range(M + 1):
        total[0][j] = 1

    ans = 1  # 空の列は常に等しい列である
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = (total[i][j] % MOD)
                ans += dp[i + 1][j + 1]
            total[i + 1][j + 1] = (total[i][j + 1] + total[i + 1][j]
                                   - total[i][j] + dp[i + 1][j + 1] + MOD) % MOD
    return ans % MOD

N, M = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
print(e_common_subsequence(N, M, S, T))

Submission status: Accepted

Solution code:
mod=1000000007
n,m=map(int,input().split())
S=tuple(map(int,input().split()))
T=tuple(map(int,input().split()))
DP=[[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
    DP[i][0]=1
for i in range(m+1):
    DP[0][i]=1
for i,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            DP[i+1][j+1]=DP[i][j+1]+DP[i+1][j]
        else:
            DP[i+1][j+1]=DP[i][j+1]+DP[i+1][j]-DP[i][j]
        DP[i+1][j+1]%=mod
print(DP[-1][-1])

Submission status: Accepted

Solution code:
mod=1000000007
n,m=map(int,input().split())
S=tuple(map(int,input().split()))
T=tuple(map(int,input().split()))
DP=[[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
    DP[i][0]=1
for i in range(m+1):
    DP[0][i]=1
for i,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            DP[i+1][j+1]=DP[i][j+1]+DP[i+1][j]
        else:
            DP[i+1][j+1]=DP[i][j+1]+DP[i+1][j]-DP[i][j]
        DP[i+1][j+1]%=mod
print((DP[-1][-1])%mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
q = 10**9 + 7

dp = [[None] * m for _ in range(n)] #[i][j]: s[i], t[j]を使ってできる部分列の数
sumdp = [[None] * m for _ in range(n)]

if s[0] == t[0]:
    dp[0][0] = 1
    sumdp[0][0] = 2
else:
    dp[0][0] = 0
    sumdp[0][0] = 1
    
# j=0
for i in range(1, n):
    if s[i] == t[0]:
        dp[i][0] = 1
        #dp[i][j] = sumdp[i-1][j-1] or 0
        sumdp[i][0] = sumdp[i-1][0] + 1
        sumdp[i][0] %= q
        #sumdp[i][j] = dp[i][j] + (sumdp[i-1][j] - sumdp[i-1][j-1])
        #              + (sum[i][j-1] - sumdp[i-1][j-1]) + sumdp[i-1][j-1]
        
    else:
        dp[i][0] = 0
        sumdp[i][0] = sumdp[i-1][0]
        
for j in range(1, m):
    if s[0] == t[j]:
        dp[0][j] = 1
        sumdp[0][j] = sumdp[0][j-1] + 1
        sumdp[0][j] %= q
    else:
        dp[0][j] = 0
        sumdp[0][j] = sumdp[0][j-1]
        
for i in range(1, n):
    for j in range(1, m):
        if s[i] == t[j]:
            dp[i][j] = sumdp[i-1][j-1]
        else:
            dp[i][j] = 0
        sumdp[i][j] = dp[i][j] + sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1]
        sumdp[i][j] %= q

print(sumdp[n-1][m-1])

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N,M = 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)]

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

print((dp[N][M]+1)%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 for i in range(M)] for j in range(N)]
sum_dp = [[0 for i in range(M)] for j in range(N)]


if S[0] == T[0]:
    dp[0][0] = 1
    sum_dp[0][0] = 1

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

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

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

print((sum_dp[N-1][M-1]+1)%mod)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
Ss = list(map(int, input().split()))
Ts = list(map(int, input().split()))
mod = 10**9 + 7

x = 2160
dp = [[0]*x for i in range(x)]
sum2d = [[0]*x for i in range(x)]
for i in range(N):
    for j in range(M):
        if Ss[i] == Ts[j]:
            dp[i+1][j+1] = sum2d[i][j] + 1
        sum2d[i+1][j+1] = (dp[i+1][j+1]+sum2d[i][j+1]+sum2d[i+1][j]-sum2d[i][j])%mod
print((sum2d[N][M]+1)%mod)

Submission status: Accepted

Solution code:
# 両方の数列から同じ部分列がいくつあるか？
import numpy as np

MOD = 10**9+7
N, M = map(int, input().split())
S = input().split()
T = np.array(input().split(), dtype=np.int32)
dp = np.ones(M+1, dtype=np.int64)

for s in S:
  dp[1:] = ((dp[:-1] * (T == int(s))).cumsum() + dp[1:]) % MOD

print(dp[M])

Submission status: Accepted

Solution code:
# 両方の数列から同じ部分列がいくつあるか？
MOD = 10**9+7
N, M = map(int, input().split())
S = [0] + list(map(int, input().split()))
T = [0] + list(map(int, input().split()))
# 最後に(n,m)でとる
dp = [[0]*(M+1) for _ in range(N+1)]
# 2次元累積和、(n,m) inclusive. 
dp_cum = [[0]*(M+1) for _ in range(N+1)]

# empty
dp[0][0] = 1
dp_cum[0][0] = 1
for n in range(N+1):
  dp_cum[n][0] = 1
for m in range(M+1):
  dp_cum[0][m] = 1  

for n in range(1, N+1):
  for m in range(1, M+1):
    if S[n] != T[m]:
      dp[n][m] = 0
    else:
      # (n-1, m-1)までで作れてるやつから飛んでくる
      dp[n][m] = dp_cum[n-1][m-1]
    dp_cum[n][m] = dp_cum[n-1][m] + dp_cum[n][m-1] - dp_cum[n-1][m-1] + dp[n][m]
    dp_cum[n][m] %= MOD

answer = dp_cum[N][M]
print(answer)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
from itertools import repeat

MOD = 10**9 + 7

N,M = map(int,input().split())
S = tuple(map(int,input().split()))
T = tuple(map(int,input().split()))

if N < M:
    N,M = M,N
    S,T = T,S

dp = deque(repeat(1, M+1), M+2)


for s in S:
    dp.append(1)
    for t in T:
        if s == t:
            dp.append(dp[1]+dp[-1])
        else:
            dp.append(dp[1]-dp[0]+dp[-1])

print(dp[-1]%MOD)

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

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

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

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
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 MAT(h): return [list(map(int, input().split())) for _ in range(h)]
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()
    dp = [[0 for i in range(N + 1)] for j in range(M + 1)]
    for j in range(M):
        for i in range(N):
            if S[i] == T[j]:
                dp[j+1][i+1] = (dp[j][i+1] + dp[j+1][i] + 1) % mod
            else:
                dp[j+1][i+1] = (dp[j][i+1] + dp[j+1][i] - dp[j][i]) % mod
    print((dp[M][N] + 1) % mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
N,M = map(int,input().split())
S = input().split()
T = np.array(input().split(), dtype = np.int32)
dp = np.ones(M+1, dtype = np.int64)
for s in S:
  dp[1:] = (np.where(T == int(s), dp[:-1], 0).cumsum() + dp[1:]) % (10**9 + 7)
print(dp[M])

Submission status: Accepted

Solution code:
import numpy as np
N,M = map(int,input().split())
S = np.array(input().split(), dtype = np.int32)
T = np.array(input().split(), dtype = np.int32)
dp = np.ones(M+1, dtype = np.int64)
for s in S:
  dp[1:] = ((dp[:-1] * (T == s)).cumsum() + dp[1:]) % (10**9 + 7)
print(dp[M])

Submission status: Accepted

Solution code:
import numpy as np
N,M = map(int,input().split())
S = np.array(input().split(), dtype = np.int32)
T = np.array(input().split(), dtype = np.int32)
dp = np.ones(M+1, dtype = np.int64)
for s in S:
  dp[1:] = ((dp[:-1] * (T == int(s))).cumsum() + dp[1:]) % (10**9 + 7)
print(dp[M])

Submission status: Accepted

Solution code:
import numpy as np
N,M = map(int,input().split())
S = [int(x) for x in input().split()]
T = np.array(input().split(), dtype = np.int32)
dp = np.ones(M+1, dtype = np.int64)
for s in S:
  dp[1:] = ((dp[:-1] * (T == s)).cumsum() + dp[1:]) % (10**9 + 7)
print(dp[M])

Submission status: Accepted

Solution code:
import numpy as np
N,M = map(int,input().split())
S = input().split()
T = np.array(input().split(), dtype = np.int32)
dp = np.ones(M+1, dtype = np.int64)
for s in S:
  dp[1:] = ((dp[:-1] * (T == int(s))).cumsum() + dp[1:]) % (10**9 + 7)
print(dp[M])

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10**9 + 7
N,M = map(int,input().split())
S = np.array(input().split(), dtype=np.int32)
T = np.array(input().split(), dtype=np.int32)

# (n,m) 以前で作れている列
dp = np.ones(M+1, dtype = np.int64)

for n in range(N):
  dp[1:] = ((dp[:-1] * (T == S[n])).cumsum() + dp[1:]) % MOD # cumsumに直す

answer = dp[M]
print(answer)

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 k in range(M+1)] for l in range(N+1)]

for k in range(N):
    for l in range(M):
        if S[k] == T[l]:
            dp[k+1][l+1] = dp[k+1][l] + dp[k][l+1] + 1
        else:
            dp[k+1][l+1] = dp[k+1][l] + dp[k][l+1] - dp[k][l]
        dp[k+1][l+1] %= MOD

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

MOD = 10**9 + 7
N,M = map(int,input().split())
S = np.array(input().split(), dtype=np.int32)
T = np.array(input().split(), dtype=np.int32)

# (n,m) 以前で作れている列
dp = np.zeros((N+1, M+1), dtype = np.int64)
dp[0] = 1

for n in range(1, N+1):
  same = (T == S[n-1])
  dp[n,1:][same] = dp[n-1,:-1][same] # ちょうど(n,m)で終わる
  dp[n] = (dp[n].cumsum() + dp[n-1]) % MOD # cumsumに直す

answer = dp[N,M]
print(answer)

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10**9 + 7
N,M = map(int,input().split())
S = np.array(input().split(), dtype=np.int32)
T = np.array(input().split(), dtype=np.int32)

# (n,m) 以前で作れている列
dp = np.zeros((N+1, M+1), dtype = np.int64)
dp[0] = 1

for n in range(1, N+1):
  same = (T == S[n-1])
  dp[n,1:][same] = dp[n-1,:-1][same] # ちょうど(n,m)で終わる
  dp[n] = (dp[n].cumsum() + dp[n-1]) % MOD # cumsumに直す

answer = dp[N,M]
print(answer)

Submission status: Accepted

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

print(dp[N][M][1])