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:
# まずDPを使う理由はあるs[i]=t[j]の時 そのs[i],t[j]を追加した時に増える部分列の場合の数は前の部分列の場合の数+1増えるから
# 前の要素を利用するということはDPを疑う

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

dp = [[0] * (m+1) for i in range(n+1)]
S = [[0] * (m+1) for i in range(n+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
        else:
            dp[i+1][j+1] = 0 # i番目,j番目を追加すると増える場合の数 iとjが等しくないならば場合の数は増えないから0
        S[i+1][j+1] = S[i][j+1] + S[i+1][j] + dp[i+1][j+1] - S[i][j]
        S[i+1][j+1] %= mod

print(S[n][m]+1)

Submission status: Time Limit Exceeded

Solution code:
# まずDPを使う理由はあるs[i]=t[j]の時 そのs[i],t[j]を追加した時に増える部分列の場合の数は前の部分列の場合の数+1増えるから
# 前の要素を利用するということはDPを疑う

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

dp = [[0] * (m+1) for i in range(n+1)]
dp[0][0] = 0 # i番目,j番目を追加すると増える場合のかず
S = [[0] * (m+1) for i in range(n+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
        else:
            dp[i+1][j+1] = 0
        S[i+1][j+1] = S[i][j+1] + S[i+1][j] + dp[i+1][j+1] - S[i][j]
        S[i+1][j+1] %= mod

ans = 1
for i in range(n+1):
    for j in range(m+1):
        ans += dp[i][j]%mod

print(S[n][m]+1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
n,m=map(int,input().split()) #<=2*10**3
#n
s=list(map(int,input().split()))
#m
t=list(map(int,input().split()))
mod=10**9+7
ans=np.zeros(m,dtype="int64")

for u in s:
    h=np.zeros(m,dtype="int64")
    if u==t[0]:
        h[0]+=1
    for i in range(1,m):
        if t[i]==u:
            h[i]+=ans[i-1]+1
        h[i]+=h[i-1]
    ans=(ans+h)%mod
print(ans[-1]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
ans = int(0)

N, M = LI()
S = LI()
T = LI()
dp = [[0]*(M+1) for _ in range(N+1)]
sumdp = [[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-1]==T[j-1]:
            dp[i][j] = sumdp[i-1][j-1]+1
            sumdp[i][j] = sumdp[i - 1][j] + sumdp[i][j - 1] +1
#            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1] + dp[i][j]
        #累積和の更新
        else:
            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1]
#        sumdp[i][j] %=mod
#        ans += dp[i][j]
#print(dp)
#for row in dp:
#    ans+= sum(row)%mod
print((sumdp[N][M]+1)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
ans = int(0)

N, M = LI()
S = LI()
T = LI()
dp = [[0]*(M+1) for _ in range(N+1)]
sumdp = [[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-1]==T[j-1]:
            dp[i][j] = sumdp[i-1][j-1]+1
            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1] + dp[i][j]
        #累積和の更新
        else:
            sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1]
#        ans += dp[i][j]
#print(dp)
#for row in dp:
#    ans+= sum(row)%mod
print((sumdp[N][M]+1)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
ans = int(0)

N, M = LI()
S = LI()
T = LI()
dp = [[0]*(M+1) for _ in range(N+1)]
sumdp = [[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-1]==T[j-1]:
            dp[i][j] = sumdp[i-1][j-1]+1
        sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1] + dp[i][j]
        #累積和の更新
#        ans += dp[i][j]
#print(dp)
#for row in dp:
#    ans+= sum(row)%mod
print((sumdp[N][M]+1)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, M = LI()
S = LI()
T = LI()
dp = [[0]*(M+1) for _ in range(N+1)]
sumdp = [[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-1]==T[j-1]:
            dp[i][j] = sumdp[i-1][j-1]+1
        sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1] + dp[i][j]
        #累積和の更新
        ans += dp[i][j]
#print(dp)
#for row in dp:
#    ans+= sum(row)%mod
print((ans+1)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, M = LI()
S = LI()
T = LI()
cou = int(0)
dp = [[0]*(M+1) for _ in range(N+1)]
sumdp = [[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-1]==T[j-1]:
            dp[i][j] = sumdp[i-1][j-1]+1
        sumdp[i][j] = sumdp[i-1][j] + sumdp[i][j-1] - sumdp[i-1][j-1] + dp[i][j]
        #累積和の更新
#print(dp)
for row in dp:
    ans+= sum(row)%mod
print((ans+1)%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10 ** 9 + 7

    N, M = map(int, input().split())
    S = input().split()
    T = 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 1 <= i and 1 <= j and S[i - 1] == T[j - 1]:
                dp[i][j] += dp[i - 1][j - 1]
            if 1 <= i:
                dp[i][j] += dp[i - 1][j]
            if 1 <= j:
                dp[i][j] += dp[i][j - 1]
            if 1 <= i and 1 <= j:
                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:
mod = 10 ** 9 + 7

N, M = map(int, input().split())
S = input().split()
T = 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 1 <= i and 1 <= j and S[i - 1] == T[j - 1]:
            dp[i][j] += dp[i - 1][j - 1]
        if 1 <= i:
            dp[i][j] += dp[i - 1][j]
        if 1 <= j:
            dp[i][j] += dp[i][j - 1]
        if 1 <= i and 1 <= j:
            dp[i][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()))
MOD = 10**9 + 7

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

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

ans = (dp[M][N] + 1) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#editorial参照
#そもそもの漸化式
#2次元累積和
#dp累積和のdpを含む漸化式 & dp消せる
n,m = map(int, input().split( ))

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

mod = 10**9 + 7

dp_sum = [[0]*(m+1) for _ in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp_sum[i][j] = dp_sum[i-1][j] + dp_sum[i][j-1] + 1
            dp_sum[i][j] %= mod
        else:
            dp_sum[i][j] = dp_sum[i-1][j] + dp_sum[i][j-1] - dp_sum[i-1][j-1]
            dp_sum[i][j] %= mod
#print(dp_sum)
print(dp_sum[n-1][m-1]+1)#空集合で+1

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = d[i][j+1] + d[i+1][j] - (ss[i] != ts[j])*d[i][j]
print(d[n][m]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = d[i][j+1] + d[i+1][j] - (0 if ss[i] == ts[j] else d[i][j])
print(d[n][m]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = d[i][j+1] + d[i+1][j] - (0 if ss[i] == ts[j] else d[i][j])
print(d[n][m]%(10**9+7))

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

        cs[i][j] = cs[i-1][j] + cs[i][j-1] - cs[i-1][j-1] + dp[i][j]
        cs[i][j] %= MOD

print((cs[n][m] + 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
S = [int(x) for x in input().split()]
T = [int(x) for x in input().split()]
p = 10 ** 9 + 7
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
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]
    if S[i] == T[j]:
      DP[i + 1][j + 1] += DP[i][j]
    DP[i + 1][j + 1] %= p
print(DP[N][M])

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

dp = [[0] * m for i in s]
ans = [[0] * m for i in s]

for i in range(n):
    for j in range(m):
        ans[i][j] = (ans[i-1][j] if i > 0 else 0) + (ans[i][j-1] if j > 0 else 0) - (ans[i-1][j-1] if i > 0 and j > 0 else 0)
        if s[i] == t[j]:
            ans[i][j] += (ans[i-1][j-1] if i > 0 and j > 0 else 0) + 1

print((ans[-1][-1] + 1) % (1000000007))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

dp = [[0] * m for i in s]

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

# print(dp)
r = sum(sum(x) for x in dp)
print((r + 1) % (1000000007))

Submission status: Time Limit Exceeded

Solution code:
def main():
    e=enumerate
    n,m,*u=map(int,open(0).read().split())
    dp=[[1]*(m+1)for _ in range(n+1)]
    for i,s in e(u[:n]):
        for j,t in e(u[n:]):
            dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j]-dp[i][j]*(s!=t))%(10**9+7)
    print(dp[n][m])
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 =[[0]*m for i in range(n)]
sum_ = [[0]*m for i in range(n)]
mod = 10 ** 9 + 7

for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i][j] = 1
            if i!=0 and j !=0:
                dp[i][j] = dp[i][j] +sum_[i-1][j-1]
        else:
            dp[i][j] = 0
        if i!=0 and j !=0:
            sum_[i][j] = (dp[i][j] + sum_[i-1][j]+sum_[i][j-1]-sum_[i-1][j-1])%mod
        elif i==0 and j == 0:
            sum_[i][j]= dp[i][j]
        elif i==0:
            sum_[i][j] = dp[i][j] + sum_[i][j-1]
        else:
            sum_[i][j] = dp[i][j] + sum_[i-1][j]

print((sum_[n-1][m-1]+1)%mod)

Submission status: Time Limit Exceeded

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

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

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

print((dp_sum[N][M]+1) % mod)

Submission status: Time Limit Exceeded

Solution code:
source = raw_input()
input = source.split(" ")
n, m = int(input[0]), int(input[1])
s = [0] + [int(i) for i in raw_input().split(" ")]
t = [0] + [int(i) for i in raw_input().split(" ")]
MOD = 10**9 + 7

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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)]
SUM=[[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-1]==T[j-1]:
      DP[i][j]=1
      for k in range(i):
        for l in range(j):
          DP[i][j]+=DP[k][l]
          DP[i][j]%=mod
ans=1
for i in range(1,n+1):
  for j in range(1,m+1):
    ans=(ans+DP[i][j])%mod
print(ans)

Submission status: Time Limit Exceeded

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

dp=[([0]*(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])%mod
        if s[i]==t[j]:
            dp[i][j]=(dp[i][j]+1)%mod
        else:
            dp[i][j]=(dp[i][j]-dp[i-1][j-1]+mod)%mod

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

Submission status: Time Limit Exceeded

Solution code:

mod=10**9+7



n,m =(int(i) for i in input().strip().split() )
s=[0]+[int(i) for i in input().strip().split()]
t=[0]+[int(i) for i in input().strip().split()]

dp=[[0]*(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]+(1 if s[i]==t[j] else -dp[i-1][j-1]))%mod

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

Submission status: Time Limit Exceeded

Solution code:

mod=10**9+7


if __name__=='__main__':
    global n,m
    n,m =(int(i) for i in input().strip().split() )
    s=[0]+[int(i) for i in input().strip().split()]
    t=[0]+[int(i) for i in input().strip().split()]

    dp=[[0]*(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]+(1 if s[i]==t[j] else -dp[i-1][j-1]))%mod

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

Submission status: Time Limit Exceeded

Solution code:

mod=10**9+7


if __name__=='__main__':
    global n,m
    n,m =(int(i) for i in input().strip().split() )
    s=[0]+[int(i) for i in input().strip().split()]
    t=[0]+[int(i) for i in input().strip().split()]

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

    for i, ss in enumerate(s[1:]):
        for j, tt in enumerate(t[1:]):
            dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1]+(1 if ss==tt else -dp[i][j]))%mod

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10 ** 9 + 7
sum_dp = defaultdict(int)

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

print(sum_dp[(N-1, M-1)] + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys

N,M=map(int, sys.stdin.readline().split())
S=[None]+map(int, sys.stdin.readline().split())
T=[None]+map(int, sys.stdin.readline().split())

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

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

print dp[-1][-1]%(10**9+7)

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
if n<m:
    x=s
    aa=m
    m=n
    n=aa
    s=T
    T=x

dp=[0]*m 
buf=[[0]*m for i in range(2)]
count=0
t=1
for i in range(n):
    t=1-t
    for j in range(m):
        if s[i]==T[j]:
            dp[j]=1
            if j>0:
                dp[j]+=buf[t][j-1]
            count+=dp[j]
        else:
            dp[j]=0
        buf[1-t][j]=buf[t][j]+dp[j]
        if j>0:
            buf[1-t][j]+=(buf[1-t][j-1]-buf[t][j-1])
print((count+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 
buf=[[0]*m for i in range(2)]
count=0
t=1
for i in range(n):
    t=1-t
    for j in range(m):
        if j==0:
            flag=0
        else:
            flag=1
        if s[i]==T[j]:
            dp[j]=1
            dp[j]+=flag*buf[t][j-1]
            count+=dp[j]
        else:
            dp[j]=0
        buf[1-t][j]=buf[t][j]+dp[j]
        buf[1-t][j]+=flag*(buf[1-t][j-1]-buf[t][j-1])
print((count+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 
buf=[[0]*m for i in range(2)]
count=0
t=1
for i in range(n):
    t=1-t
    for j in range(m):
        if s[i]==T[j]:
            dp[j]=1
            if j!=0:
                dp[j]+=buf[t][j-1]
            count+=dp[j]
        else:
            dp[j]=0
        buf[1-t][j]=buf[t][j]+dp[j]
        if j>0:
            buf[1-t][j]+=buf[1-t][j-1]-buf[t][j-1]
print((count+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 
buf=[[0]*m for i in range(2)]
count=0
t=1
for i in range(n):
    t=1-t
    for j in range(m):
        if s[i]==T[j]:
            if i==0 or j==0:
                dp[j]=1
            else:
                dp[j]=buf[t][j-1]+1
            count+=dp[j]
        else:
            dp[j]=0
        buf[1-t][j]=buf[t][j]+dp[j]
        if j>0:
            buf[1-t][j]+=buf[1-t][j-1]-buf[t][j-1]
print((count+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 
ss=[0]*m
buf=[[0]*m for i in range(2)]
count=0
t=1
for i in range(n):
    t=1-t
    for j in range(m):
        if s[i]==T[j]:
            if i==0 or j==0:
                dp[j]=1
            else:
                dp[j]=buf[t][j-1]+1
            count+=dp[j]
            count=count%mod
        else:
            dp[j]=0
        buf[1-t][j]=buf[t][j]+dp[j]
        if j>0:
            buf[1-t][j]+=buf[1-t][j-1]-buf[t][j-1]
        #print(dp)
    #print(buf[t])
print(count+1)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
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 
ss=[0]*m
buf=[0]*m
count=0
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            if i==0 or j==0:
                dp[j]=1
            else:
                dp[j]=ss[j-1]+1
            count+=dp[j]
            count=count%mod
        else:
            dp[j]=0
        buf[j]=ss[j]+dp[j]
        if j>0:
            buf[j]+=buf[j-1]-ss[j-1]
    #ss=buf
    for i in range(m):
        ss[i]=buf[i]
print(count+1)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
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 
ss=[0]*m
buf=[0]*m
count=0
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            if i==0 or j==0:
                dp[j]=1
                count+=1
                count=count%mod
            else:
                dp[j]=ss[j-1]+1
                count+=dp[j]
                count=count%mod
            buf[j]=ss[j]+dp[j]
        else:
            buf[j]=ss[j]
        if j>0:
            buf[j]+=buf[j-1]-ss[j-1]
    #ss=buf
    ss=deepcopy(buf)
print(count+1)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
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 for i in range(n)]
ss=[0]*m
buf=[0]*m
count=0
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            if i==0 or j==0:
                dp[i][j]=1
                count+=1
                count=count%mod
            else:
                dp[i][j]=ss[j-1]+1
                count+=dp[i][j]
                count=count%mod
        if j>0:
            buf[j]=ss[j]+dp[i][j]+buf[j-1]-ss[j-1]
        else:
            buf[j]=ss[j]+dp[i][j]
    ss=deepcopy(buf)
print(count+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
import numpy as np
from copy import deepcopy
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 for i in range(n)]
ss=[0]*m
buf=[0]*m
count=0
for i in range(n):
    for j in range(m):
        #print(s[i],t[j])
        if s[i]==t[j]:
            if i==0:
                dp[i][j]=1
                count+=1
                count=count%mod
            else:
                if j>0 and i>0:
                    dp[i][j]=ss[j-1]+1
                else:
                    dp[i][j]=1
                count+=dp[i][j]
                count=count%mod
        if j>0:
            buf[j]=ss[j]+dp[i][j]+buf[j-1]-ss[j-1]
        else:
            buf[j]=ss[j]+dp[i][j]
    ss=deepcopy(buf)
    #print(ss)
#print(dp,ss,sep='\n')
print(count+1)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

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

dp = [[-1]*(M+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = 1
for j in range(1,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

ans = dp[N][M]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

mod = 10**9 + 7

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

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

def rec(i,j):
    if dp[i][j] != -1:
        return dp[i][j]
    res = 0
    if S[i-1] == T[j-1]:
        res = rec(i,j-1) + rec(i-1,j)
    else:
        res = rec(i,j-1) + rec(i-1,j) - rec(i-1,j-1)
    res %= mod
    dp[i][j] = res
    return res

ans = rec(N,M)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc():
  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)
calc()

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
S = [int(x) for x in input().split()]
T = [int(x) for x in input().split()]

dp = arr = [[0 for i in range(M+1)] for j 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][j-1] + dp[i-1][j] - dp[i-1][j-1] + dp[i-1][j-1]
        else:
            dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]

print(int(dp[N][M] % (10**9 + 7)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M = map(int, input().split())
S = [int(x) for x in input().split()]
T = [int(x) for x in input().split()]

dp = np.zeros((N+1,M+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][j-1] + dp[i-1][j] - dp[i-1][j-1] + dp[i-1][j-1]
        else:
            dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]

print(int(dp[N][M] % (10**9 + 7)))

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

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:
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
s1=0
for i in range(N):
  s1=s1+c[i]
  sm[i][0]=s1
s1=0
for i in range(M):
  s1=s1+d[i]
  sm[0][i]=s1
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)