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:
#!/usr/bin/env python3
import sys
from pprint import pprint

MOD = 1000000007  # type: int

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

def __solve(n, m, s, t):
    #dp = [[1] * (m + 1)] + [[1] + [0] * m for _ in range(n)]

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

    for i in range(n):
        for j in range(m):
            #if s[i] == t[j]:
            #    dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
            #else:
            #    dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j]
            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
            if not s[i - 1] == t[j - 1]:
                dp[i + 1][j + 1] -= dp[i][j]

    #arr_s = [0] + s
    #arr_t = [0] + t
    #for c in range(1, n + 1):
    #    for r in range(1, m + 1):
    #        if arr_s[c] == arr_t[r]:
    #            dp[c][r] = dp[c-1][r] + dp[c][r-1]
    #        else:
    #            dp[c][r] = dp[c-1][r] + dp[c][r-1] - dp[c-1][r-1]
    #        dp[c][r] %= MOD
    pprint(dp)
    #ret = dp[m][n]
    ret = dp[n][m] % MOD
    print(ret)
    return
 




def _solve(N: int, M: int, S: "List[int]", T: "List[int]"):
    tmp = [0] * (N + M + 1)
    tmp[0] = 1
    for i in range(1, N + M + 1):
        tmp[i] = tmp[i - 1] * 2

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

    ret = 1
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            mx0 = max(dp[i - 1][j][0], dp[i][j - 1][0])
            mx1 = max(dp[i - 1][j][1], dp[i][j - 1][1])
            if S[i - 1] == T[j - 1]:
                dp[i][j] = [dp[i - 1][j - 1][0] + 1, dp[i - 1][j - 1][1] + mx1]
                #dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] * 1
                #dp[i][j] = 2 ** dp[i - 1][j - 1]
                #ret += 2 ** (dp[i][j] - 1)
                #print(i, j, ret)
            else:
                dp[i][j] = [mx0, mx1]
                #dp[i][j] = dp[i][j - 1]
    pprint(dp)
    ##ret = 1
    ##for i in range(1, N + 1):
    ##    for j in range(1, M + 1):
    ##        if S[i - 1] == T[j - 1] and dp[i][j] > 0:
    ##            #ret += tmp[dp[i][j] - 1]
    ##            ret += dp[i][j]
    ##            ret %= MOD
    ##            print(i, j)
    ##            print(tmp[dp[i][j] - 1])
    print(ret)
    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

print(Sum[N][M]+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=1000000007

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

for i in range(N):
	for j in range(M):
		if S[i]==T[j]:
			for k in range(i):
				for l in range(j):
					dp[i][j]+=dp[k][l]
			dp[i][j]+=1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
S = list(map(int, input().split()))
T = list(map(int, input().split()))
 
s = [[1] * (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]:
            s[i][j] = s[i - 1][j] + s[i][j - 1]
        else:
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]
 
print(s[i][j] % 1000000007)

Submission status: Time Limit Exceeded

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

s = [[1] * (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]:
            s[i][j] = s[i - 1][j] + s[i][j - 1]
        else:
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]

print(s[i][j] % 1000000007)

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([2, m + 1], dtype=np.int)
for i, si in enumerate(s):
    for j, tj in enumerate(t):
        idx = (i + 1) % 2
        dp[idx, j + 1] = (dp[idx, j] + dp[1 - idx, j + 1] - dp[1 - idx, j]) % MOD
        if si == tj:
            dp[idx, j + 1] += dp[1 - idx, j] + 1
        dp[idx, j + 1] %= MOD
print((dp[n % 2, -1] + 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 for j in range(m + 1)] for i in range(2)]
for i, si in enumerate(s):
    for j, tj in enumerate(t):
        idx = (i + 1) % 2
        dp[idx][j + 1] = (dp[idx][j] + dp[1 - idx][j + 1] - dp[1 - idx][j]) % MOD
        if si == tj:
            dp[idx][j + 1] += dp[1 - idx][j] + 1
        dp[idx][j + 1] %= MOD
print((dp[n % 2][-1] + 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 for j in range(m + 1)] for i in range(2)]
for i, si in enumerate(s):
    for j, tj in enumerate(t):
        idx = (i + 1) % 2
        dp[idx][j + 1] = dp[idx][j] + dp[1 - idx][j + 1] - dp[1 - idx][j]
        if si == tj:
            dp[idx][j + 1] += (dp[1 - idx][j] + 1)
        dp[idx][j + 1] %= MOD
print((dp[n % 2][-1] + 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 for j in range(m + 1)] for i in range(n + 1)]
for i, si in enumerate(s):
    for j, tj in enumerate(t):
        dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1] - dp[i][j]) % MOD
        if si == tj:
            dp[i + 1][j + 1] += (dp[i][j] + 1) % MOD
            dp[i + 1][j + 1] %= MOD
print((dp[-1][-1] + 1) % MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

print((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)]
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:
# -*- coding: utf-8 -*-

import sys

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

N,M=MAP()
S=[0]+LIST()
T=[0]+LIST()

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配列を2次元累積和にして、動的に更新していく
        # (+-する添字位置は、普通の区間取得の時とは違う。どうなってるかは自分のメモ参照)
        dp[i][j]=(dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1])%MOD
        # 今回増やす数値が一致するなら
        if S[i] == T[j]:
            # そこより手前の全部合計+1
            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,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def onem():
    return int(input())
def s(x):
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

n,m = m()

S = l()
T = l()

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

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

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

MOD = 10**9+7

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

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

print(a[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
ans=[1]*(1+M)
for i in range(1,1+N):
    ansc=ans.copy()
    for j in range(1,1+M):
        if S[i-1]==T[j-1]:
            ans[j]=(ansc[j]+ans[j-1])%mod
        else:
            ans[j]=(ansc[j]+ans[j-1]-ansc[j-1])%mod
print(ans[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
ans=[[0]*(1+M) for i in range(1+N)]
ans[0]=[1]*(1+M)
for i in range(1,1+N):
    ans[i][0]=ans[i-1][0]
    for j in range(1,1+M):
        if S[i-1]==T[j-1]:
            ans[i][j]=(ans[i-1][j]+ans[i][j-1])%mod
        else:
            ans[i][j]=(ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1])%mod
print(ans[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()))
dp=[[0]*(1+M) for i in range(1+N)]
dp[0][0]=1
mod=10**9+7
for i,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            dp[i+1][j+1]=1
ans=[[0]*(1+M) for i in range(1+N)]
ans[0][0]=dp[0][0]
for j in range(1,1+M):
    ans[0][j]=(ans[0][j-1]+dp[0][j])%mod
for i in range(1,1+N):
    ans[i][0]=(ans[i-1][0]+dp[i][0])%mod
    for j in range(1,1+M):
        ans[i][j]=(ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]*(1-dp[i][j]))%mod
print(ans[N][M])

Submission status: Time Limit Exceeded

Solution code:
MOD = pow(10, 9) + 7

n, m = map(int, input().split())
slist = list(map(int, input().split()))
tlist = list(map(int, input().split()))

dp = [[1 for _ in range(n+1)] for _ in range(m+1)]
for i, s in enumerate(slist):
  for j, t in enumerate(tlist):
    if s != t:
      dp[j+1][i+1] = ((dp[j+1][i] + dp[j][i+1]) % MOD - dp[j][i]) % MOD
    else:
      #if slist[i] == t and tlist[j] == s:
        dp[j+1][i+1] = (dp[j+1][i] + dp[j][i+1]) % MOD
      #else:
      #  dp[j+1][i+1] = ((dp[j+1][i] + dp[j][i+1]) % MOD - dp[j][i]) % MOD

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

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy as de
n,m =[int(i) for i in input().split()]
s=[int(i) for i in input().split()]
t=[int(i) for i in input().split()]
a=[1]*(m+1)
for i,b in enumerate(s):
  d=de(a)
  k=0
  for j,c in enumerate(t):
    d[j]=(k+d[j])%1000000007
    if b==c:
      k=(k+a[j])%1000000007
  d[-1]=(k+d[-1])%1000000007
  a=de(d)
print(a[-1]%1000000007)

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

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

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

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

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

Submission status: Time Limit Exceeded

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

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

import numpy as np
dp = np.zeros(M+1, dtype=np.int64)
for i, s in enumerate(S):
    dp2 = np.zeros(M+1, dtype=np.int64)
    dp2[1:] = dp[1:] - dp[:M]
    for j, t in enumerate(T):
        dp2[j+1] += dp2[j]
        if s == t:
            dp2[j+1] += dp[j] + 1
    dp = dp2

print(int(dp[M]+1) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

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

dp = [0] * (M+1)
for i, s in enumerate(S):
    dp2 = dp[:]
    cum = 0
    for j, t in enumerate(T):
        k = dp2[j] - dp[j]
        if s == t:
            k += dp[j] + 1
        dp2[j+1] += k
    dp = dp2

print((dp[M]+1) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

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

dp = [0] * (M+1)
for i, s in enumerate(S):
    dp2 = dp[:]
    for j, t in enumerate(T):
        dp2[j+1] += dp2[j] - dp[j]
        if s == t:
            dp2[j+1] += dp[j] + 1
    dp = dp2

print((dp[M]+1) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

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

import numpy as np
dp = np.zeros((N+1, M+1), dtype=np.int64)

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

print(int(dp[N, M]+1) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

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

import numpy as np
dp = np.zeros((N+1, M+1), dtype=np.uint32)

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

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

Submission status: Time Limit Exceeded

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

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

import numpy as np
dp = np.zeros((N+1, M+1), dtype=np.uint32)
for i, s in enumerate(S):
    for j, t in enumerate(T):
        dp[i+1, j+1] += dp[i, j+1] + dp[i+1, j]
        if s == t:
            dp[i+1, j+1] += 1
        else:
            dp[i+1, j+1] -= dp[i, j]
        dp[i+1, j+1] %= 1000000007

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

Submission status: Time Limit Exceeded

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

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

import numpy as np
dp = np.zeros((N+1, M+1), dtype=np.uint32)
for i in range(1, N+1):
    for j in range(1, M+1):
        dp[i, j] += dp[i-1, j] + dp[i, j-1]
        if S[i-1] == T[j-1]:
            dp[i, j] += 1
        else:
            dp[i, j] -= dp[i-1, j-1]
        dp[i, j] %= 1000000007

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

Submission status: Time Limit Exceeded

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

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

import numpy as np
dp = np.zeros((N+1, M+1), dtype=np.uint64)
for i in range(1, N+1):
    for j in range(1, M+1):
        dp[i, j] = dp[i-1, j] + dp[i, j-1]
        if S[i-1] == T[j-1]:
            dp[i, j] += 1
        else:
            dp[i, j] -= dp[i-1, j-1]
        dp[i, j] %= 1000000007

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

Submission status: Time Limit Exceeded

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

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

import numpy as np
dp = np.zeros((N+1, M+1), dtype=np.uint64)
for i in range(1, N+1):
    for j in range(1, M+1):
        dp[i, j] = dp[i-1, j] + dp[i, j-1]
        if S[i-1] == T[j-1]:
            dp[i, j] += 1
        else:
            dp[i, j] -= dp[i-1, j-1]

print(int(dp[N, M]+1) % 1000000007)

Submission status: Time Limit Exceeded

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

from itertools import accumulate

def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [0]*(M+1)
    for s in S:
        is_s = s.__eq__
        acc = [0]*(M+1)
        for i, t in enumerate(T):
            acc[i+1] = acc[i]+(dp[i] + 1 if is_s(t) else 0)
        *dp, = map(int.__add__, dp, acc)
    res = (dp[-1]+1)%(10**9+7)
    return str(res)

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

Submission status: Time Limit Exceeded

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

from itertools import accumulate


def solve():
    N, M = map(int, input().split())
    if N <=M :
        *T, = map(int, input().split())
        S = map(int, input().split())
        dp = [0]*(N+1)
    else:
        S = map(int, input().split())
        *T, = map(int, input().split())
        dp = [0]*(M+1)
    for s in S:
        *dp, = map(int.__add__, dp, accumulate(map(lambda d,t: (d+1 if s.__eq__(t) else 0), [0]+dp, T)))
    res = (dp[-1]+1)%(10**9+7)
    return str(res)

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

Submission status: Time Limit Exceeded

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

    # S, T のどちらかを見ていない場合、空整数列のみが等しい整数列となる
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1

    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                # S[i], T[j] までで作れた等しい整数列に対して
                # 1つ新しい要素を付け加えられる。よって次式のように和を取る
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
            else:
                # S[i], T[j] は付け加えられないので、その分引く
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + MOD
            dp[i + 1][j + 1] %= MOD
    return dp[N][M]

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

Submission status: Time Limit Exceeded

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

from itertools import accumulate


def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [0]*(M+1)
    for s in S:
        *dp, = map(int.__add__, dp, accumulate(map(lambda d,t: (d+1 if s.__eq__(t) else 0), [0]+dp, T)))
    res = (dp[-1]+1)%(10**9+7)
    return str(res)

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

Submission status: Time Limit Exceeded

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

from itertools import accumulate


def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [0]*(M+1)
    for s in S:
        *acc, = accumulate(map(lambda d,t: (d+1 if s.__eq__(t) else 0), dp, T))
        *dp, = map(int.__add__, dp, [0]+acc)
    res = (dp[-1]+1)%(10**9+7)
    return str(res)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % 1000000007
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % 1000000007
            i += i & -i


n, m = list(map(int, input().split()))
sss = list(map(int, input().split()))
ttt = list(map(int, input().split()))

sid = defaultdict(list)
for i, s in reversed(list(enumerate(sss))):
    sid[s].append(i)

bit = Bit(n + 1)
bit.add(1, 1)

for t in ttt:
    if t not in sid:
        continue
    for i in sid[t]:
        bit.add(i + 2, bit.sum(i + 1))

print(bit.sum(n + 1))

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % 1000000007
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % 1000000007
            i += i & -i


n, m = list(map(int, input().split()))
sss = list(map(int, input().split()))
ttt = list(map(int, input().split()))

bit = Bit(n + 1)
bit.add(1, 1)

for t in ttt:
    for i in range(n - 1, -1, -1):
        s = sss[i]
        if s != t:
            continue
        bit.add(i + 2, bit.sum(i + 1))

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

dp0 = [[0 for _ in range(2005)] for _ in range(2005)]
dp1 = [[0 for _ in range(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]
print(ans % MOD)

Submission status: Time Limit Exceeded

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

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

t = 0
for i in range(M):
  if S[0] == T[i]:
    t += 1
  DP[0][i] = t

for i in range(1, N):
  cnt = 0
  while cnt < M:
    if cnt == 0:
      DP[i][0] = DP[i - 1][0]
      if S[i] == T[0]:
        DP[i][0] += 1
    else:
      if S[i] == T[cnt]:
        DP[i][cnt] = (DP[i - 1][cnt] + 1 + DP[i][cnt - 1]) % MOD
      else:
        DP[i][cnt] = (DP[i - 1][cnt] + DP[i][cnt - 1] - DP[i - 1][cnt - 1]) % MOD
      while DP[i][cnt] < MOD:
        DP[i][cnt] += MOD
    cnt += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd

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

for i in range(N):
    dp[i + 1][1] = dp[i][1] + 1 if t[0] == s[i] else dp[i][1]

if N > 1 and M > 1:
    for i in range(1, N):
        for j in range(1, M):
            if s[i] == t[j]:
                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]
    
print((dp[N][M] + 1)%MOD)

Submission status: Time Limit Exceeded

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

def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [0]*(M+1)
    for s in S:
        dp_ = dp[:]
        for i, t in enumerate(T):
            dp[i+1] = dp_[i+1] + dp[i] - dp_[i] + (dp_[i]+1 if t==s else 0)
    res = (dp[-1]+1)%(10**9+7)
    return str(res)

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