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: Time Limit Exceeded

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[i+1][j+1] : S_iまで，T_jまでで作ることのできる共通部分列の数
dp = [[0] * 2010 for _ in range(2010)]
dp[0][0] = 1

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

print(dp[N][M])

Submission status: Time Limit Exceeded

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 + 2) for _ in range(N + 2)]
sdp = [[0] * (M + 2) for _ in range(N + 2)]
dp[0][0] = 1
sdp[1][1] = 1
for i in range(N + 1):
    for j in range(M + 1):
        if i - 1 >= 0 and j - 1 >= 0 and S[i - 1] == T[j - 1]:
            dp[i][j] = sdp[i][j]
        sdp[i + 1][j + 1] = sdp[i + 1][j] + sdp[i][j + 1] - sdp[i][j] + dp[i][j]
        sdp[i + 1][j + 1] %= MOD
        sdp[i + 1][j + 1] %= MOD
print(sdp[N + 1][M + 1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

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

dp=[[1]*(M+1) for i in range(N+1)]
S_index=[set() for i in range(10**5+1)]

for i in range(N):
  S_index[S[i]].add(i)
  for j in range(M):
    dp[i][j]=dp[i][j-1]
    for k in S_index[T[j]]:
      dp[i][j]=(dp[i][j]+dp[k-1][j-1])%MOD
      
print(dp[N-1][M-1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

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

dp=[[1]*(M+1) for i in range(N+1)]
S_index=[[] for i in range(10**5+1)]

for i in range(N):
  S_index[S[i]].append(i)
  if len(S_index[S[i]])>=2:
    ikkomae=S_index[S[i]][-2]
    for j in range(M+1):
    	dp[i-1][j]=(dp[i-1][j]+dp[ikkomae-1][j])%MOD
  for j in range(M):
    dp[i][j]=dp[i][j-1]
    if len(S_index[T[j]])>=1:
    	dp[i][j]=(dp[i][j]+dp[S_index[T[j]][-1]-1][j-1])%MOD
      
print(dp[N-1][M-1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

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

dp=[[1]*(M+1) for i in range(N+1)]
S_index=[set() for i in range(10**5+1)]

for i in range(N):
  S_index[S[i]].add(i)
  for j in range(M):
    dp[i][j]=dp[i][j-1]
    for k in S_index[T[j]]:
      dp[i][j]=(dp[i][j]+dp[k-1][j-1])%MOD
      
print(dp[N-1][M-1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

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

dp=[[1]*(M+1) for i in range(N+1)]
S_index=[[] for i in range(10**5+1)]

for i in range(N):
  S_index[S[i]].append(i)
  for j in range(M):
    dp[i][j]=dp[i][j-1]
    for k in S_index[T[j]]:
      dp[i][j]=(dp[i][j]+dp[k-1][j-1])%MOD
      
print(dp[N-1][M-1])

Submission status: Time Limit Exceeded

Solution code:
# ほぼ解説AC
# n,m<2000
# len(s),len(t)<100000
import sys

input = sys.stdin.buffer.readline

n, m = map(int, input().split())
mod = 10 ** 9 + 7
S = list(map(int, input().split()))
T = list(map(int, input().split()))


dp = [[0] * (m + 2) for _ in range(n + 2)]
sum_dp = [[0] * (m + 2) for _ in range(n + 2)]
# 空集合も要素とみなすのでdp[0][0]は1
dp[0][0] = 0
# i,jを見る時にi,jまでの累積和がほすぃ。
# i,jを見てi+1,j+1を決める。
for i in range(n + 1):
    for j in range(m + 1):
        # 二次元累積和の計算
        sum_dp[i][j] += dp[i][j]
        if i - 1 >= 0:
            sum_dp[i][j] += sum_dp[i - 1][j]
        if j - 1 >= 0:
            sum_dp[i][j] += sum_dp[i][j - 1]
        if i - 1 >= 0 and j - 1 >= 0:
            sum_dp[i][j] -= sum_dp[i - 1][j - 1]
        sum_dp[i][j] %= mod
        if i < n and j < m:
            # 先にsum_dp[i][j]は計算されていないとだめ。↑
            # i-1字目、j-1字目まででできるものに、新たに一致したものを加えたもの(sum_dp)と空集合(+1)
            if S[i] == T[j]:
                dp[i + 1][j + 1] = sum_dp[i][j] + 1
                dp[i + 1][j + 1] %= mod
print((sum_dp[n][m] + 1) % mod)

Submission status: Time Limit Exceeded

Solution code:
# ほぼ解説AC
# n,m<2000
# len(s),len(t)<100000
n, m = map(int, input().split())
mod = 10 ** 9 + 7
S = list(map(int, input().split()))
T = list(map(int, input().split()))


dp = [[0] * (m + 2) for _ in range(n + 2)]
sum_dp = [[0] * (m + 2) for _ in range(n + 2)]
# 空集合も要素とみなすのでdp[0][0]は1
dp[0][0] = 0
# i,jを見る時にi,jまでの累積和がほすぃ。
# i,jを見てi+1,j+1を決める。
for i in range(n + 1):
    for j in range(m + 1):
        # 二次元累積和の計算
        sum_dp[i][j] += dp[i][j]
        if i - 1 >= 0:
            sum_dp[i][j] += sum_dp[i - 1][j]
        if j - 1 >= 0:
            sum_dp[i][j] += sum_dp[i][j - 1]
        if i - 1 >= 0 and j - 1 >= 0:
            sum_dp[i][j] -= sum_dp[i - 1][j - 1]
        sum_dp[i][j] %= mod
        if i < n and j < m:
            # 先にsum_dp[i][j]は計算されていないとだめ。↑
            # i-1字目、j-1字目まででできるものに、新たに一致したものを加えたもの(sum_dp)と空集合(+1)
            if S[i] == T[j]:
                dp[i + 1][j + 1] = sum_dp[i][j] + 1
                dp[i + 1][j + 1] %= mod
print((sum_dp[n][m] + 1) % mod)

Submission status: Time Limit Exceeded

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)]
for i in range(n+1):
  dp[i][0]=1
for i in range(m+1):
  dp[0][i]=1
mod=pow(10,9)+7
for i in range(n):
  for j in range(m):
    dp[i+1][j+1]=sum((dp[i][j+1],dp[i+1][j],-dp[i][j]))%mod
    if s[i]==t[j]:dp[i+1][j+1]+=dp[i][j]
    dp[i+1][j+1]%=mod
print(dp[-1][-1])
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def solve():
  ans = 0
  mod = 10**9+7
  s = defaultdict(lambda: -1)
  t = defaultdict(lambda: -1)
  N, M = map(int, input().split())
  S = list(map(int, input().split()))
  T = list(map(int, input().split()))
  for i in range(N):
    s[S[i]] = i
  for j in range(M):
    t[T[j]] = j
  dp = [[0]*(M+1) for _ in range(N+1)]
  for j in range(M+1):
    dp[0][j] = 1
  for i in range(1,N+1):
    dp[i][0] = 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]
      else:
        dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
  ans = dp[-1][-1]%mod
  return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

class BIT:
	def __init__(self, n):
		self.n = n
		self.nums = [0] * (n+1)
		
	def add(self, i, x):
		n, nums = self.n, self.nums
		i += 1
		while i <= n:
			nums[i] += x
			i += i & -i
	
	def sum(self, i):
		nums = self.nums
		s = 0
		i += 1
		while i:
			s += nums[i]
			i -= i & -i
		return s
	
	def search(self, x):
		n, nums = self.n, self.nums
		s, p = 0, 0
		for i in range(n.bit_length(), -1, -1):
			np = p + (1<<i)
			if np <= n and s+nums[np] < x:
				s += nums[np]
				p = np
		return p

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

h = defaultdict(list)
for i, t in enumerate(T):
	h[t].append(i)
bit = BIT(M+1)
for i, s in enumerate(S):
	vals = []
	for j in h[s]:
		vals.append((j, bit.sum(j)+1))
	for j, v in vals:
		bit.add(j+1, v%mod)
print((bit.sum(M)+1)%mod)

Submission status: Time Limit Exceeded

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)]
dps = [[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] = (dps[n][m]+1)%mod
        dps[n+1][m+1] = (dp[n+1][m+1]+dps[n+1][m]+dps[n][m+1]-dps[n][m])%mod

print(dps[-1][-1]+1)

Submission status: Time Limit Exceeded

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)]
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
        else:
            dp[n+1][m+1] = dp[n+1][m]+dp[n][m+1]-dp[n][m]
        dp[n+1][m+1] %= mod

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

Submission status: Time Limit Exceeded

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)]
sum = [[0] * (m + 1) for _ in range(n + 1)]
MOD = 10 ** 9 + 7

ans = 0
for i in range(n):
  for j in range(m):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = (sum[i][j] + 1) % MOD
    else:
      dp[i + 1][j + 1] = 0
    sum[i + 1][j + 1] = (sum[i][j + 1] + sum[i + 1][j] 
                       - sum[i][j] + dp[i + 1][j + 1]) % MOD
    ans += dp[i + 1][j + 1]
    ans %= MOD
print((ans + 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
S = LI()
T = LI()

MOD = 10 ** 9 + 7


def main():
    dp = [[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] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]
            dp[i][j] %= MOD
            if S[i - 1] == T[j - 1]:
                x = 1 + dp[i - 1][j - 1]
                dp[i][j] = (dp[i][j] + x) % MOD
    
    ans = (dp[-1][-1] + 1) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#Python遅すぎて話になんねえ
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 i 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(n):
    for j in range(m):
        #答え見たらここの添字間違えてただけ…
        #だけど、適当にダブりを引きたくなっただけなので全然方針としてだめ、要復習
        if s[i]==t[j]:
            dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1])%mod
        else:
            dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1]-dp[i][j])%mod
print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
import numpy
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 i 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(n):
    for j in range(m):
        #答え見たらここの添字間違えてただけ…
        #だけど、適当にダブりを引きたくなっただけなので全然方針としてだめ、要復習
        if s[i]==t[j]:
            dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1])%mod
        else:
            dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1]-dp[i][j])%mod
print(dp[n][m])
#print(numpy.array(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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):
  for j in range(m+1):
    if i == 0 or j == 0:
      dp[i][j] = 1
    else:
      dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
      if S[i-1] == T[j-1]:
        dp[i][j] += dp[i-1][j-1]
      dp[i][j] %= MOD
ans = dp[n][m]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    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 for _ in range(M + 1)] for _ in range(N + 1)]
    sdp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
    for n, s in enumerate(S):
        for m, t in enumerate(T):
            sdp_val = sdp[n][m]
            new_dp_val = (sdp_val + 1) if s == t else 0
            dp[n + 1][m + 1] = new_dp_val % MOD
            sdp[n + 1][m + 1] = (sdp[n][m + 1] + sdp[n + 1][m] - sdp_val + new_dp_val) % MOD
    print((sdp[N][M] + 1) % MOD)  # 1: an empty sequence


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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

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

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

print(dp[N][M])

Submission status: Time Limit Exceeded

Solution code:

def valide(i,A):
    return 0<=i and i <= A

N = 0
M = 0
N, M = input().split()
N = int(N)
M = int(M)
#print(N, M)
S = input().split()
T = input().split()
#print(S)
#print(T)

DP = [[0 for x in range(M)] for y in range(N)]
curr = 0
for i in range(N):
    if S[i] == T[0]:
        curr = curr + 1
        DP[i][0] = curr+1
    DP[i][0] = curr+1
curr = 0
for j in range(M):
    if T[j] == S[0]:
        curr = curr + 1
        DP[0][j] = curr+1
    DP[0][j] = curr+1


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

Submission status: Time Limit Exceeded

Solution code:
def main():
  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 i in range(M+1):
    dp[0][i] = 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]
      dp[i+1][j+1] %= MOD
      if S[i] == T[j]:
        dp[i+1][j+1] += dp[i][j]
      dp[i+1][j+1] %= MOD
  print(dp[N][M])
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  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 i in range(M+1):
    dp[0][i] = 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])
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    s = [int(x) for x in input().split()]
    t = [int(x) for x in input().split()]
    
    mod = pow(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(n):
        for j in range(m):
            dp[i+1][j+1] = (dp[i+1][j]+dp[i][j+1]-dp[i][j])%mod
            if s[i] == t[j]:
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= mod
    
    print(dp[n][m])            
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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 _ in range(n + 1)]

for i, ei in enumerate(s, 1):
    for j, ej in enumerate(t, 1):
        if ei == ej:
            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] %= mod

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():

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

    mod = pow(10, 9) + 7
    dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
    dp[0][0] = 0
    # for i in range(N): dp[i][0] = 0
    # for j in range(M): dp[0][j] = 0

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import bisect
import numpy as np

MOD = 10 ** 9 + 7

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

S_appeared_indices = defaultdict(list)
for i, c1 in enumerate(S):
    S_appeared_indices[c1].append(i)

T_appeared_indices = defaultdict(list)
for j, c2 in enumerate(T):
    T_appeared_indices[c2].append(j)

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

for i, c1 in enumerate(S):
    for j, c2 in enumerate(T):
        dp[i+1, j+1] = dp[i+1, j]
        if c2 in S_appeared_indices:
            tmp = bisect.bisect_right(S_appeared_indices[c2], i) - 1
            while tmp >= 0:
                S_index = S_appeared_indices[c2][tmp]
                dp[i+1, j+1] += dp[S_index, j]
                tmp -= 1
        dp[i+1, j+1] %= MOD

print(dp[N, M])

Submission status: Time Limit Exceeded

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

dp = [0] * n
ndp = [0] * n
for tj in t:
    for i in range(n):
        ndp[i] = 0
    acc = 0
    for i, si in enumerate(s):
        if si == tj:
            ndp[i] = (dp[i] + acc + 1) % MOD
        else:
            ndp[i] = dp[i]
        acc = (acc + dp[i]) % MOD
    dp, ndp = ndp, dp
print((sum(dp) + 1) % MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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 1 + accum[i-1][j-1]
        accum[i][j] = accum[i-1][j]+accum[i][j-1]-accum[i-1][j-1]+dp[i][j]   

ans = (sum(map(sum, dp))+1)%MOD
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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, a in enumerate(A, start=1):
    for j, b in enumerate(B, start=1):
        if a == b:
            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: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
mod = 10**9+7
a = [0]+[int(i) for i in readline().split()]
b = [0]+[int(i) for i in readline().split()]
dp = [[0]*(m+1) for i in range(n+1)]
su = [[0]*(m+1) for i in range(n+1)]

dp[0][0] = 1
su[0][0] = 1
for i in range(1,n+1):
  su[i][0] = 1
for j in range(1,m+1):
  su[0][j] = 1
  
for i in range(1,n+1):
  for j in range(1,m+1):
    if a[i] == b[j]:
      dp[i][j] = su[i-1][j-1]
    else:
      dp[i][j] = 0
    su[i][j] = su[i-1][j]+su[i][j-1]-su[i-1][j-1]+dp[i][j]
    su[i][j] %= mod
    
print(su[n][m])

Submission status: Time Limit Exceeded

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 _ 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(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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    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)]
    SUM=[[0]*(M+2) for _ in range(N+2)]
    ans=1
    for s in range(N):
        for t in range(M):
            if S[s]==T[t]:
                dp[s+1][t+1]=SUM[s+1][t+1]+1
                ans+=dp[s+1][t+1]
                ans%=MOD
            else:
                dp[s+1][t+1]=0
            SUM[s+2][t+2]=SUM[s+1][t+2]+SUM[s+2][t+1]-SUM[s+1][t+1]+dp[s+1][t+1]
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M,*L = map(int, open(0).read().split())
S = L[:N]
T = L[N:]
MOD = 10**9+7
dp = [[0]*(M+1) for i 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(1,N+1):
  for j in range(1,M+1):
    if S[i-1]==T[j-1]:
      dp[i][j] += dp[i][j-1]+dp[i-1][j]
    else:
      dp[i][j] += dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]
    dp[i][j] %= MOD
print(dp[N][M])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
LAST = 10**6
MOD = 10**9 + 7
S.append(LAST)
T.append(LAST)
total = [[0 for j in range(M+2)] for i in range(N+2)]
for i in range(N+1):
    for j in range(M+1):
        I,J = i+1,j+1
        if S[i] != T[j]:
            total[I][J] = (total[I][J-1] + total[I-1][J] - total[I-1][J-1]) % MOD
        else:
            total[I][J] = (total[I][J-1] + total[I-1][J] + 1) % MOD
        
print((total[N][M] + 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#ABC130-E Common Subsequence
"""
問題：
整数列のリストが与えられる
空であるものも含めて、sとtの部分列として等しいものの個数を求めよ
解法：
LCSのmaxではなくsumのバージョンでかつ、
数え上げなので重複をなくさなければならない。
具体的には、
dp[i][j]:sをi文字目迄見た時のtをj文字目迄見た時に、
dp0:横方向(j方向)を優先して遷移した後に、縦方向(i方向)への遷移を行った時の合計
dp1:縦方向、横方向への遷移を行った時の合計
として、dp1[-1][-1]が答え。

"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m = map(int,readline().split())
s = list(map(int,readline().split())) + [-1]
t = list(map(int,readline().split())) + [-2]
mod = 10**9+7

#dp table
dp0 = [[0]*(m+2) for _ in range(n+2)]
dp1 = [[0]*(m+2) for _ in range(n+2)]
dp0[0][0] = 1
#process1
for i in range(n+1):
    for j in range(m+1):
        dp0[i+1][j] += dp0[i][j]
        dp1[i][j] += dp0[i][j]
        dp1[i][j+1] += dp1[i][j]
        if s[i] == t[j]:
            dp0[i+1][j+1] += dp1[i][j]


print(dp1[n][m]%mod)

Submission status: Time Limit Exceeded

Solution code:
# https://drken1215.hatenablog.com/entry/2019/06/21/230200

def main():
    MOD = 10 ** 9 + 7

    N, M = map(int, input().split())
    *s, = map(int, input().split())
    *t, = map(int, input().split())

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N + 1):
        for j in range(M + 1):
            if j > 0:
                dp[i][j] += dp[i][j - 1]
            if i > 0:
                dp[i][j] += dp[i - 1][j]
            if i > 0 and j > 0 and s[i - 1] != t[j - 1]:
                dp[i][j] -= dp[i - 1][j - 1]
            dp[i][j] %= MOD
    print(dp[N][M])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://hiramekun.hatenablog.com/entry/2019/06/18/184256

def main():
    MOD = 10 ** 9 + 7

    N, M = map(int, input().split())
    *s, = map(int, input().split())
    *t, = map(int, input().split())

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    acc = [[0] * (M + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(M):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = acc[i][j] + 1
            acc[i + 1][j + 1] = (acc[i + 1][j] + acc[i][j + 1] - acc[i][j] + dp[i + 1][j + 1]) % MOD
    print(acc[N][M] + 1)  # ''の分


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
def main():
    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 si in range(1, n+1):
        for ti in range(1, m+1):
            if s[si-1] == t[ti-1]:
                dp[si][ti] += 1
                dp[si][ti] += dp[si-1][ti-1]
            dp[si][ti] += dp[si-1][ti] + dp[si][ti-1]
            dp[si][ti] -= dp[si-1][ti-1]
            dp[si][ti] %= MOD
    print(dp[n][m] + 1)
#    for i in range(n+1):
#        print(dp[i])

if __name__ == "__main__":
    main()