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
c=[0]*N
d=[0]*M
dp=[[ 0 for i in range(M)] for j in range(N)]
sm=[[ 0 for i in range(M)] for j in range(N)]
for i in range(N):
  if t[0]==s[i]:
    dp[i][0]=1
    c[i]=1
for i in range(M):
  if s[0]==t[i]:
    dp[0][i]=1
    d[i]=1
for i in range(N):
  sm[i][0]=sum(c[0:i+1])
for i in range(M):
  sm[0][i]=sum(d[0:i+1])
for i in range(1,N):
  for j in range(1,M):
    if s[i] != t[j]:
      dp[i][j]=0
    else:
      dp[i][j]=sm[i-1][j-1]+1
    sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+dp[i][j]
ans=(sm[N-1][M-1]+1)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#解説読み 2次元dp
mod = 10**9 + 7
n,m = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
tmp = [1 for _ in range(m+1)]
dp = [tmp]
for ni in range(n):
  last = tmp
  tmp = [1]
  for mi in range(m):
    if A[ni] != B[mi]:
      x = tmp[-1]+last[mi+1]-last[mi]
    else:
      x = tmp[-1]+last[mi+1]
    x %= mod
    tmp.append(x)
  dp.append(tmp)
print(dp[-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()))

# 累積和参照のために0の行，列を追加
sm = [[0] * (M+1) for _ in range(N+1)]

for i , s in enumerate(S) :
    l1 = sm[i][:]
    l2 = 0
    for j , t in enumerate(T) :
        new = l1[j+1] + l2
        if s == t :
            new += 1  # dp = sm[i-1][j-1] + 1
        else :
            new -= l1[j] # dp = 0
        l2 = new
        sm[i+1][j+1] = new

ans = (sm[-1][-1] + 1) % (10**9 + 7)

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()))

# 累積和参照のために0の行，列を追加
sm = [[0] * (M+1) for _ in range(N+1)]

for i in range(1,N+1) :
    l1 = sm[i-1][:]
    l2 = 0
    s = S[i-1]
    for j in range(1,M+1) :
        new = l1[j] + l2
        if s == T[j-1] :
            new += 1  # dp = sm[i-1][j-1] + 1
        else :
            new -= l1[j-1] # dp = 0
        l2 = new
        sm[i][j] = new

ans = (sm[-1][-1] + 1) % (10**9 + 7)

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()))

# 累積和参照のために0の行，列を追加
sm = [[0] * (M+1) for _ in range(N+1)]

for i in range(1,N+1) :
    l1 = sm[i-1][:]
    l2 = 0
    for j in range(1,M+1) :
        new = l1[j] + l2
        if S[i-1] == T[j-1] :
            new += 1  # dp = sm[i-1][j-1] + 1
        else :
            new -= l1[j-1] # dp = 0
        l2 = new
        sm[i][j] = new

ans = (sm[-1][-1] + 1) % (10**9 + 7)

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()))

# 累積和参照のために0の行，列を追加
sm = [[0] * (M+1) for _ in range(N+1)]

for i in range(1,N+1) :
    l = sm[i-1][:]
    for j in range(1,M+1) :
        new = l[j] + sm[i][j-1]
        if S[i-1] == T[j-1] :
            new += 1  # dp = sm[i-1][j-1] + 1
        else :
            new -= l[j-1] # dp = 0
        sm[i][j] = new

ans = (sm[-1][-1] + 1) % (10**9 + 7)

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()))

# 累積和参照のために0の行，列を追加
sm = [[0] * (M+1) for _ in range(N+1)]

for i in range(1,N+1) :
    for j in range(1,M+1) :
        new = sm[i-1][j] + sm[i][j-1]
        if S[i-1] == T[j-1] :
            new += 1  # dp = sm[i-1][j-1] + 1
        else :
            new -= sm[i-1][j-1] # dp = 0
        sm[i][j] = new

ans = (sm[-1][-1] + 1) % (10**9 + 7)

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()))

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

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

ans = (sm[-1][-1] + 1) % (10**9 + 7)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7


def main(S, T):
  sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

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

  return (sdp[-1][-1] + 1)


if __name__ == '__main__':
  _, _ = map(int, input().strip().split())
  S = input().strip().split()
  T = input().strip().split()
  # S = range(1000)
  # T = range(1000)
  print(main(S, T))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

_, _ = map(int, input().strip().split())
S = list(map(int, input().strip().split()))
T = list(map(int, input().strip().split()))

sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

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

print(sdp[-1][-1] + 1)
# for row in sdp:
#  print(('{: 4d} ' * len(row)).format(*row))
## print(sdp)

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()))
	S.append(0)
	T.append(0)
	MOD = 10**9+7

	dp0 = [[0 for _ in range(M+2)] for _ in range(N+2)]
	dp1 = [[0 for _ in range(M+2)] for _ in range(N+2)]
	dp0[0][0] = 1
	for i in range(N+1):
		for j in range(M+1):
			dp0[i+1][j] += dp0[i][j]%MOD
			dp0[i+1][j] %= MOD
			dp1[i][j] += dp0[i][j]%MOD
			dp1[i][j] %= MOD
			dp1[i][j+1] += dp1[i][j]%MOD
			dp1[i][j+1] %= MOD

			if S[i] == T[j]:
				dp0[i+1][j+1] += dp1[i][j]
				dp0[i+1][j+1] %= MOD
	print(dp1[N][M])


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

md=10**9+7
n,m=map(int,input().split())
s=list(input().split())
t=list(input().split())
dp=np.zeros((n+1,m+1),dtype="i8")
dp[0][0]=1
for i,sk in enumerate(s):
    for j,tk in enumerate(t):
        if sk==tk:
            dp[i+1][j+1]=np.sum(dp[:i+1,:j+1])%md
print(np.sum(dp)%md)

Submission status: Time Limit Exceeded

Solution code:
md=10**9+7
n,m=map(int,input().split())
s=list(input().split())
t=list(input().split())
dp=[[0]*(m+3) for _ in range(n+3)]
dp[0][0]=1
for i,sk in enumerate(s):
    for j,tk in enumerate(t):
        if sk==tk:
            dp[i+1][j+1]=sum(sum(dpi[:j+1]) for dpi in dp[:i+1])
print(sum(sum(dpi) for dpi in dp)%md)

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 for _ in range(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
mod = 10**9 + 7
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])%mod
        else:
            dp[i + 1][j + 1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j]+mod) % mod
print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
s = inl()
t = inl()
dp = [ [0] * (m+1) for i in range(n) ]
dp[0][0] = 1 if s[0]==t[0] else 0
for i in range(1,n):
    dp[i][0] = dp[i-1][0] + (1 if s[i]==t[0] else 0)
for j in range(1,m):
    dp[0][j] = dp[0][j-1] + (1 if s[0]==t[j] else 0)

sh = defaultdict(list)
for i in range(1,n):
    sh[s[i]].append(i)

for j in range(1,m):
    x = 0
    acc = [0] * (n+1)
    for z in sh[t[j]]:  # s[z]==t[j]
        x = (x+dp[z-1][j-1]+1)%R  # z>0
        acc[z] = x
        if j==14:
            ddprint("dp {} z {} acc {}".format(dp[z-1][j-1], z, acc[z]))
    for i in range(1,n):
        acc[i] = (acc[i-1] if acc[i]==0 else acc[i])

    for i in range(1,n):
        x = dp[i][j-1]
        #for z in sh[t[j]]:  # s[z]==t[j]
        #  if z<=i:
        #    x = (x+dp[z-1][j-1]+1)%R  # z>0
        x += acc[i]
        if t[j]==s[0]:
            x += 1
        dp[i][j] = x%R
        if i==18 and j==14:
            ddprint("{}  {}  {}".format(dp[i][j-1], acc[i], t[j]==s[0]))
        ddprint("i {} j {} dpij {}".format(i,j,dp[i][j]))

if DBG:
    for i in range(n):
        print(dp[i])
print((dp[n-1][m-1]+1)%R)

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
s = inl()
t = inl()
dp = [ [0] * (m+1) for i in range(n) ]
dp[0][0] = 1 if s[0]==t[0] else 0
for i in range(1,n):
    dp[i][0] = dp[i-1][0] + (1 if s[i]==t[0] else 0)
for j in range(1,m):
    dp[0][j] = dp[0][j-1] + (1 if s[0]==t[j] else 0)

sh = defaultdict(list)
for i in range(1,n):
    sh[s[i]].append(i)

for j in range(1,m):
    for i in range(1,n):
        x = dp[i][j-1]
        for z in sh[t[j]]:  # s[z]==t[j]
          if z<=i:
            x = (x+dp[z-1][j-1]+1)%R  # z>0
        if t[j]==s[0]:
            x += 1
        dp[i][j] = x

if DBG:
    for i in range(n):
        print(dp[i])
print((dp[n-1][m-1]+1)%R)

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
s = inl()
t = inl()
dp = [ [0] * (m+1) for i in range(n) ]
dp[0][0] = 1 if s[0]==t[0] else 0
for i in range(1,n):
    dp[i][0] = dp[i-1][0] + (1 if s[i]==t[0] else 0)
for j in range(1,m):
    dp[0][j] = dp[0][j-1] + (1 if s[0]==t[j] else 0)

sh = defaultdict(list)
for i in range(1,n):
    sh[s[i]].append(i)

for i in range(1,n):
    for j in range(1,m):
        x = dp[i][j-1]
        for z in sh[t[j]]:  # s[z]==t[j]
          if z<=i:
            x = (x+dp[z-1][j-1]+1)%R  # z>0
        if t[j]==s[0]:
            x += 1
        dp[i][j] = x

if DBG:
    for i in range(n):
        print(dp[i])
print((dp[n-1][m-1]+1)%R)

Submission status: Time Limit Exceeded

Solution code:
"""
解説を参考に作成

考え方:
    Sのi文字目までとTのj文字目までで,
    Si と Tj がペアになる場合のパターン数を解く (dp)
    -> Si != Tj の場合,そもそもペアにできないので 0.
    -> それ以外の場合は以下の2通りが考えられる.
        Sのi-1文字目までとTのj-1文字目までの全パターンに対して Si と Tjを追加したパターン
        Si と Tj のみのパターン
    よって Si と Tj までで作成できるパターンの総合計も同時に求めておく必要がある (dp_sum)
"""


def solve():
    mod = 10 ** 9 + 7
    N, M = map(int, input().split())
    S = [int(i) for i in input().split()]
    T = [int(i) for i in input().split()]
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    dp_sum = [[0] * (M + 1) for _ in range(N + 1)]
    # ppprint(dp_sum)
    for i, Si in enumerate(S, 1):
        for j, Tj in enumerate(T, 1):
            if Si == Tj:
                # print(i, j)
                # print(dp_sum[i - 1])
                dp[i][j] = dp_sum[i - 1][j - 1] + 1
            dp_sum[i][j] = (dp_sum[i][j - 1] + dp_sum[i - 1][j] -
                            dp_sum[i - 1][j - 1] + dp[i][j]) % mod
    # print('include table')
    # ppprint(dp)
    # print('sum table')
    # ppprint(dp_sum)
    print((dp_sum[N][M] + 1) % mod)


def ppprint(itr_obj):
    for ite in itr_obj:
        print(ite)


if __name__ == '__main__':
    import datetime
    d = datetime.datetime.now()
    solve()
    # print(datetime.datetime.now() - d)

Submission status: Time Limit Exceeded

Solution code:
"""
解説を参考に作成

考え方:
    Sのi文字目までとTのj文字目までで,
    Si と Tj がペアになる場合のパターン数を解く (dp)
    -> Si != Tj の場合,そもそもペアにできないので 0.
    -> それ以外の場合は以下の2通りが考えられる.
        Sのi-1文字目までとTのj-1文字目までの全パターンに対して Si と Tjを追加したパターン
        Si と Tj のみのパターン
    よって Si と Tj までで作成できるパターンの総合計も同時に求めておく必要がある (dp_sum)
"""


def solve():
    mod = 10 ** 9 + 7
    N, M = map(int, input().split())
    S = [int(i) for i in input().split()]
    T = [int(i) for i in input().split()]
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    dp_sum = [[0] * (M + 1) for _ in range(N + 1)]
    # ppprint(dp_sum)
    for i, Si in enumerate(S, 1):
        for j, Tj in enumerate(T, 1):
            if Si == Tj:
                # print(i, j)
                # print(dp_sum[i - 1])
                dp[i][j] = dp_sum[i - 1][j - 1] + 1
            dp_sum[i][j] = (dp_sum[i][j - 1] + dp_sum[i - 1][j] -
                            dp_sum[i - 1][j - 1] + dp[i][j])
    # print('include table')
    # ppprint(dp)
    # print('sum table')
    # ppprint(dp_sum)
    print((dp_sum[N][M] + 1) % mod)


def ppprint(itr_obj):
    for ite in itr_obj:
        print(ite)


if __name__ == '__main__':
    solve()

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 = [[1]+[0]*(len(T))for i in range(len(S)+1)]
dp[0] = [1]*(len(T)+1)
dp_sum = [[1]+[0]*(len(T))for i in range(len(S)+1)]
dp_sum[0] = [1]*(len(T)+1)
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp_sum[i][j]
        dp_sum[i+1][j+1] = (dp[i+1][j+1]+dp_sum[i+1][j]+\
            dp_sum[i][j+1]-dp_sum[i][j])%(10**9+7)
print(dp_sum[-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 for _ in range(m)] for _ in range(n)]
sd = [[0 for _ in range(m)] for _ in range(n)]

ans = 1

if s[0] == t[0]:
    dp[0][0] = 1
    sd[0][0] = 1
    ans += 1

for i in range(1, n):
    if s[i] == t[0]:
        dp[i][0] = 1
        ans += 1
    sd[i][0] = dp[i][0] + sd[i-1][0]

for j in range(1, m):
    if s[0] == t[j]:
        dp[0][j] = 1
        ans += 1
    sd[0][j] = dp[0][j] + sd[0][j-1]

for i in range(1, n):
    for j in range(1, m):
        if s[i] == t[j]:
            dp[i][j] = (sd[i-1][j-1] + 1) % MOD
            ans = (ans + dp[i][j]) % MOD
        sd[i][j] = (sd[i-1][j] + sd[i][j-1] - sd[i-1][j-1] + dp[i][j]) % 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

dp = [[0 for _ in range(m)] for _ in range(n)]
sd = [[0 for _ in range(m)] for _ in range(n)]

if s[0] == t[0]:
    dp[0][0] = 1
    sd[0][0] = 1

for i in range(1, n):
    if s[i] == t[0]:
        dp[i][0] = 1
    sd[i][0] = dp[i][0] + sd[i-1][0]

for j in range(1, m):
    if s[0] == t[j]:
        dp[0][j] = 1
    sd[0][j] = dp[0][j] + sd[0][j-1]

for i in range(1, n):
    for j in range(1, m):
        if s[i] == t[j]:
            dp[i][j] = (sd[i-1][j-1] + 1) % MOD
        sd[i][j] = (sd[i-1][j] + sd[i][j-1] - sd[i-1][j-1] + dp[i][j]) % MOD

#for i in range(n): print(dp[i])
#for i in range(n): print(sd[i])

ans = 0
for i in range(n):
    ans = (ans + sum(dp[i])) % MOD

print((ans + 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def chk(num):
	return num % (10 ** 9 + 7)

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

S.append(0)
T.append(0)

dp0 = [[0 for _ in range(M+2)] for _ in range(N+2)]
dp1 = [[0 for _ in range(M+2)] for _ in range(N+2)]

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]

print(chk(dp1[N][M]))

Submission status: Time Limit Exceeded

Solution code:
def chk(num):
	return num % (10 ** 9 + 7)

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

S.append(0)
T.append(0)

dp0 = [[0 for _ in range(M+2)] for _ in range(N+2)]
dp1 = [[0 for _ in range(M+2)] for _ in range(N+2)]

dp0[0][0] = 1

for i in range(N+1):
	for j in range(M+1):
		dp0[i+1][j] += dp0[i][j]
		dp0[i+1][j] = chk(dp0[i+1][j])
		dp1[i][j] += dp0[i][j]
		dp1[i][j] = chk(dp1[i][j])
		dp1[i][j+1] += dp1[i][j]
		dp1[i][j+1] = chk(dp1[i][j+1])
		if S[i] == T[j]:
			dp0[i+1][j+1] += dp1[i][j]
			dp0[i+1][j+1] = chk(dp0[i+1][j+1])

print(dp1[N][M])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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

sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

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

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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

sdp = [[0] * (len(T)) for _ in range(len(S))]

for i, s in enumerate(S):
  for j, t in enumerate(T):
    sdp[i][j] = 1 if s == t else 0
    if i > 0: sdp[i][j] += sdp[i - 1][j]
    if j > 0: sdp[i][j] += sdp[i][j - 1]
    if s != t and i > 0 and j > 0: sdp[i][j] -= sdp[i - 1][j - 1]
    sdp[i][j] %= MOD

print(sdp[-1][-1] + 1)
# for row in sdp:
#  print(('{: 4d} ' * len(row)).format(*row))
## print(sdp)

Submission status: Time Limit Exceeded

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

import itertools

S_bubun = []
T_bubun = []
for i in range(N+1):
    S_bubun.extend(list(itertools.combinations(S,i)))
for i in range(M+1):
    T_bubun.extend(list(itertools.combinations(T,i)))

count = 0
for s in S_bubun:
    for t in T_bubun:
        if s == t:
            count += 1

print(count %(10**9 + 7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    S = [0] + list(map(int, input().split()))
    T = [0] + list(map(int, input().split()))

    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-1][j] + dp[i][j-1] - dp[i-1][j-1] + int(S[i] == T[j]) * (dp[i-1][j-1] + 1)) % MOD

    return (dp[N][M] + 1) % MOD


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

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    S = [0] + list(map(int, input().split()))
    T = [0] + list(map(int, input().split()))

    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-1][j] + dp[i][j-1] - dp[i-1][j-1]
            if S[i] == T[j]:
                dp[i][j] += dp[i-1][j-1] + 1
            dp[i][j] %= MOD

    return (dp[N][M] + 1) % MOD


if __name__ == '__main__':
    print(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()))
dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = (ndp[m] + dp[m+1]) % MOD
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = (ndp[m] + dpleft[m]) % MOD
        dp[m] = ndp[m]
    dp[-1] = ndp[-1]
print(dp[-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 = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = ndp[m] + dp[m+1]
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
        dp[m] = ndp[m]
    dp[M] = ndp[M]
print(dp[-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 = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = ndp[m] + dp[m+1]
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
    dp = ndp[:]
print(dp[-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 = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
for n in range(N):
    ndp = [1]
    for m in range(M):
        if S[n] == T[m]:
            ndp.append(ndp[-1] + dp[m+1])
            dpleft[m] = dp[m+1]
        else:
            ndp.append(ndp[-1] + dpleft[m])
    dp = ndp
print(dp[-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 = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7

for n in range(N):
    ndp = [1]
    for m in range(M):
        if S[n] == T[m]:
            ndp.append(ndp[-1] + dp[m+1])
            dpleft[m] = dp[m+1]
        else:
            ndp.append(ndp[-1] + dpleft[m])
    dp = ndp
print(dp[-1] % MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

dp=np.zeros((N+1, M+1), dtype=np.int)

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

Solution code:
n,m = map(int,input().split())
s = list(input().split())
t = list(input().split())
mod = int(1e9+7)
s.insert(0,0)
t.insert(0,0)

dp = [[0 for k in range(m+1)] for i in range(n+1)] #dp[i][k]:s_i,t_k

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

for i in range(1,n+1):
    for k in range(1,m+1):
        if s[i] == t[k]:
            dp[i][k] = dp[i-1][k] + dp[i][k-1] - dp[i-1][k-1] + dp[i-1][k-1] 
        else:
            dp[i][k] = dp[i-1][k] + dp[i][k-1] - dp[i-1][k-1]
        
print(dp[n][m]%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros(shape=(n, m))
wa = np.zeros(shape=(n, m))

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            if i == 0 and j == 0:
                dp[i, j] = 1
                wa[i, j] = dp[i, j]
            elif i == 0:
                dp[i, j] = 1
                wa[i, j] = wa[i, j-1] + dp[i, j]
            elif j == 0:
                dp[i, j] = 1
                wa[i, j] = wa[i-1, j] + dp[i, j]
            else:
                dp[i, j] = wa[i-1, j-1] + 1
                wa[i, j] = wa[i-1, j] + wa[i, j-1] - wa[i-1, j-1] + dp[i, j]
        else:
            dp[i, j] = 0
            if i == 0 and j == 0:
                wa[i, j] = 0
            elif i == 0:
                wa[i, j] = wa[i, j-1] + dp[i, j]
            elif j == 0:
                wa[i, j] = wa[i-1, j] + dp[i, j]
            else:
                wa[i, j] = wa[i-1, j] + wa[i, j-1] - wa[i-1, j-1] + dp[i, j]

print(int((wa[n-1, m-1] + 1) % mod))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros(shape=(n, m))

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            if i == 0:
                dp[i, j] = sum(dp[:i, :j]) + 1
            else:
                dp[i, j] = sum(sum(dp[:i, :j])) + 1
        else:
            dp[i, j] = 0

print(int((sum(sum(dp)) + 1) % mod))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
N,M = list(map(int,sys.stdin.readline().split()))
S = np.array(sys.stdin.readline().split())
#S = [0] + S
T = np.array(sys.stdin.readline().split())
#T = [0] + T
DP = np.zeros((M+1,N+1))
for n in range(N+1):
    DP[0][n] = 1
for m in range(M+1):
    DP[m][0] = 1
# s = 0
# for i in range(N+1):
#     for j in range(M+1):
#         if S[i] == T[j]:
#             for i2 in range(i):
#                 for j2 in range(j):
#                     dp[i][j] += dp[i2][j2]
#             s += dp[i][j]
# print(s)
mod = 10**9 + 7
for n in range(1,N+1):
    for m in range(1,M+1):
        num = DP[m-1][n-1] if S[n-1] == T[m-1] else 0
        DP[m][n] = (DP[m-1][n] + DP[m][n-1] + num - DP[m-1][n-1]) % mod
print(int(DP[M][N]))

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    S = [0] + list(map(int, input().split()))
    T = [0] + list(map(int, input().split()))

    dp = [[0] * (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-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

    return (dp[N][M] + 1) % MOD


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

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M = list(map(int,sys.stdin.readline().split()))
S = list(map(int,sys.stdin.readline().split()))
S = [0] + S
T = list(map(int,sys.stdin.readline().split()))
T = [0] + T
DP = [[0] * (N+1)  for _ in range(M+1)]
for n in range(N+1):
    DP[0][n] = 1
for m in range(M+1):
    DP[m][0] = 1
# s = 0
# for i in range(N+1):
#     for j in range(M+1):
#         if S[i] == T[j]:
#             for i2 in range(i):
#                 for j2 in range(j):
#                     dp[i][j] += dp[i2][j2]
#             s += dp[i][j]
# print(s)
mod = 10**9 + 7
for n in range(1,N+1):
    for m in range(1,M+1):
        num = DP[m-1][n-1] if S[n] == T[m] else 0
        DP[m][n] = (DP[m-1][n] + DP[m][n-1] + num - DP[m-1][n-1]) % mod
print(DP[M][N])

Submission status: Time Limit Exceeded

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