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:
MOD = 10**9 + 7
class SegTree():
    def segfunc(self, x, y):
        return x + y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, m = map(int, input().split())
    s = list(map(int, input().split()))
    t = list(map(int, input().split()))
    a = [0]*m
    seg = SegTree(0, m, a)
    for i in range(n):
        x = s[i]
        for j in reversed(range(m)):
            if x == t[j]:
                y = seg.query(0, j+1)
                seg.update(j, y+1)
    print((seg.query(0, m) + 1) % MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
class SegTree():
    def segfunc(self, x, y):
        return (x + y) % MOD

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, m = map(int, input().split())
    s = list(map(int, input().split()))
    t = list(map(int, input().split()))
    a = [0]*m
    seg = SegTree(0, m, a)
    for i in range(n):
        x = s[i]
        for j in reversed(range(m)):
            if x == t[j]:
                y = seg.query(0, j+1)
                seg.update(j, y+1)
#        for j in range(m):
#            print(seg.query(j, j+1), end=" ")
#        print("")
    print((seg.query(0, m) + 1) % MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    MOD = 10**9 + 7

    N, M = map(int, input().split())
    Ss = list(map(int, input().split()))
    Ts = list(map(int, input().split()))

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

    for i, S in enumerate(Ss, start=1):
        for j, T in enumerate(Ts, start=1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
            if S == T:
                dp[i][j] += dp[i-1][j-1]
            dp[i][j] %= MOD

    print(dp[N][M])


solve()

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7

N,M=map(int,input().split())
slist=list(map(int,input().split()))
tlist=list(map(int,input().split()))

dp,dp_sum=[],[]
for i in range(N+1):
  dp.append([0]*(M+1))
  dp_sum.append([1]*(M+1))
dp[0][0]=1
#print(dp)

for i in range(1,N+1):
  for j in range(1,M+1):
    if slist[i-1]==tlist[j-1]:
      dp[i][j]=dp_sum[i-1][j-1]      
    dp_sum[i][j]=(dp[i][j]+dp_sum[i-1][j]+dp_sum[i][j-1]-dp_sum[i-1][j-1])%MOD
#print(dp)
#print(dp_sum)

print(dp_sum[-1][-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7

N,M=map(int,input().split())
slist=list(map(int,input().split()))
tlist=list(map(int,input().split()))

dp=[]
for i in range(N+1):
  dp.append([0]*(M+1))
dp[0][0]=1
#print(dp)

answer=1
for i in range(1,N+1):
  for j in range(1,M+1):
    if slist[i-1]==tlist[j-1]:
      for ii in range(i):
        for jj in range(j):
          dp[i][j]+=dp[ii][jj]
          answer+=dp[ii][jj]
          answer%=MOD

#print(dp)
print(answer)

Submission status: Time Limit Exceeded

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

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

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

    dp = [[0] * (M + 1) for _ in range(N + 1)]  # (i,j)で丁度終わる文字列数
    dp[0][0] = 0
    dp[0][1] = 0
    dp[1][0] = 0

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

    for i, si in enumerate(s, 1):
        for j, ti in enumerate(t, 1):
            if si == ti:
                dp[i][j] = acc[i - 1][j - 1] + 1
            else:
                dp[i][j] = 0
            acc[i][j] = (acc[i - 1][j] + acc[i][j - 1] + dp[i][j] - acc[i - 1][j - 1]) % MOD

    ans = acc[N][M] + 1  # ("","")のケース

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
from collections import defaultdict

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

MOD = 10 ** 9 + 7

# (i, j): S[:i]とT[:j]での共通部分列の個数
dp = defaultdict(int)

# 初期条件
for i in range(N + 1):
    dp[(i, 0)] = 1
for j in range(M + 1):
    dp[(0, j)] = 1

# 貰うDP
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)] += dp[(i, j)]
        
        # ダブルカウントを除く
        dp[(i + 1, j + 1)] -= dp[(i, j)]

        dp[(i + 1, j + 1)] %= MOD

print(dp[(N, M)])

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
from collections import defaultdict

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

MOD = 10 ** 9 + 7

# dp[i][j]: S[:i]とT[:j]での共通部分列の個数
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

# 貰うDP
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] += dp[i][j]
        
        # ダブルカウントを除く
        dp[i + 1][j + 1] -= dp[i][j]

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

print(dp[N][M])

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
s=input().split()
t=input().split()
dp=[[1]*(m+1)]+[[1]+[0]*m for _ in range(n)]
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]*(s[i]!=t[j]))%(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()))
PR = 1000000007

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

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

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

for i in range(n):
	for j in range(m):
		#aa
		sumI = 0
		
		for jj in range(0,j):
			if s[i] == t[jj]:
				sumI=(sumI + dp[i][jj]) % PR
		
		sumJ = 0
		for ii in range(0,i):
			if t[j] == s[ii]:
				sumJ=(sumJ + dp[ii][j]) % PR
		
		if s[i] == t[j]:
			dp[i+1][j+1] = (sumI + sumJ + dp[i][j] + dp[i][j]) % PR
		else:
			dp[i+1][j+1] = (sumI + sumJ + dp[i][j]) % PR
#		print("i: %d j: %d  sumI: %d sumJ:%d dp[i][j]:%d" % (i+1,j+1,sumI,sumJ,dp[i+1][j+1]))

#print(dp)
print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


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

# dp[i][j] : Sの左からi文字目までと Tの左からj文字目まででの 共通部分文字列の数
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N+1):
    for j in range(M+1):
        if 0<=i-1 and 0<=j-1 and S[i-1]==T[j-1]:
            dp[i][j] += dp[i-1][j-1]
        if 0<=i-1:
            dp[i][j] += dp[i-1][j]
        if 0<=j-1:
            dp[i][j] += dp[i][j-1]
        # 重複カウント部分を減算する
        if 0<=i-1 and 0<=j-1:
            dp[i][j] -= dp[i-1][j-1]
        dp[i][j] %= mod

print(dp[N][M])

Submission status: Time Limit Exceeded

Solution code:
import sys
mod=10**9+7
input=sys.stdin.buffer.readline
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[ [0 for _ in range(m)] for _ in range(n)]
for i in range(0,n):
    for j in range(0,m):
        ret=0
        if i-1>=0:
            ret+=dp[i-1][j]
        if j-1>=0:
            ret+=dp[i][j-1]
        if i-1>=0 and j-1>=0:
            ret-=dp[i-1][j-1]
        if s[i]==t[j]:
            ret+=1
            if i-1>=0 and j-1>=0:
                ret+=dp[i-1][j-1]
        if ret>=mod:
            ret%=mod
        if ret<0:
            ret+=mod
        dp[i][j]=ret
print((dp[n-1][m-1]+1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6+32)
mod=10**9+7
input=sys.stdin.buffer.readline
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[ [0 for _ in range(m)] for _ in range(n)]
for i in range(0,n):
    for j in range(0,m):
        ret=0
        if i-1>=0:
            ret+=dp[i-1][j]
        if j-1>=0:
            ret+=dp[i][j-1]
        if i-1>=0 and j-1>=0:
            ret-=dp[i-1][j-1]
        if s[i]==t[j]:
            ret+=1
            if i-1>=0 and j-1>=0:
                ret+=dp[i-1][j-1]
        ret%=mod
        if ret<0:
            ret+=mod
        dp[i][j]=ret
print((dp[n-1][m-1]+1)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6+32)
mod=10**9+7
input=sys.stdin.buffer.readline
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[ [-1 for _ in range(m)] for _ in range(n)]
def solve(i,j):
    if i==0 and j==0:
        if s[i]==t[j]:
            return 1
        else:
            return 0
    if i<0 or j<0:
        return 0
    if dp[i][j]!=-1:
        return dp[i][j]
    ret=0
    ret=solve(i-1,j)+solve(i,j-1)-solve(i-1,j-1)
    ret%=mod
    if s[i]==t[j]:
        ret+=1+solve(i-1,j-1)
    dp[i][j]=ret%mod
    return dp[i][j]
print((solve(n-1,m-1)+1)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6+32)
from functools import lru_cache
mod=10**9+7
input=sys.stdin.buffer.readline
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
#dp=[ [0 for _ in range(m)] for _ in range(n)]
@lru_cache(None)
def solve(i,j):
    if i==0 and j==0:
        if s[i]==t[j]:
            return 1
        else:
            return 0
    if i<0 or j<0:
        return 0
    ret=0
    ret=solve(i-1,j)+solve(i,j-1)-solve(i-1,j-1)
    ret%=mod
    if s[i]==t[j]:
        ret+=1+solve(i-1,j-1)
    return ret%mod
print((solve(n-1,m-1)+1)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6+32)
from functools import lru_cache
mod=10**9+7
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
#dp=[ [0 for _ in range(m)] for _ in range(n)]
@lru_cache(None)
def solve(i,j):
    if i==0 and j==0:
        if s[i]==t[j]:
            return 1
        else:
            return 0
    if i<0 or j<0:
        return 0
    ret=0
    ret=solve(i-1,j)+solve(i,j-1)-solve(i-1,j-1)
    ret%=mod
    if s[i]==t[j]:
        ret+=1+solve(i-1,j-1)
    return ret%mod
print((solve(n-1,m-1)+1)%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
input = sys.stdin.readline
def main():
    n,m = map(int,input().split())
    s = list(map(int,input().split()))
    t = list(map(int,input().split()))
    
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    if s[0] == t[0]:
        dp[1][1] = 1
    else:
        dp[1][1] = 0
    for i in range(n):
        for j in range(m):
            if i == j == 0:
                continue
            if s[i] == t[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[-1][-1] + 1)%MOD)

if __name__ =='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n,m = map(int,input().split())
    s = list(map(int,input().split()))
    t = list(map(int,input().split()))
    
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    if s[0] == t[0]:
        dp[1][1] = 1
    else:
        dp[1][1] = 0
    for i in range(n):
        for j in range(m):
            if i == j == 0:
                continue
            if s[i] == t[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[-1][-1] + 1)

if __name__ =='__main__':
    main()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

memo = [[0] * M for _ in range(N)]
def dfs(i, j):
    if i < 0 or j < 0:
        return 1
    if memo[i][j] != 0:
        return memo[i][j]
    if S[i] == T[j]:
        memo[i][j] = (dfs(i-1, j) + dfs(i, j-1)) % mod
    else:
        memo[i][j] = (dfs(i-1, j) + dfs(i, j-1) - dfs(i-1, j-1)) % mod
    return memo[i][j]

print(dfs(N-1, 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 = 10 ** 9 + 7

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


for i, es in enumerate(s, 1):
    for j, et in enumerate(t, 1):
        if es == et:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

        dp[i][j] %= mod

ans = dp[n][m]
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()))

data=[[0 for i in range(0,M)] for j in range(0,N)]
for i in range(0,N):
    if S[i]==T[0]:
        data[i][0]=1

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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_cum = [[0] * (M+1) for _ in range(N+1)]

for x in range(N):
    for y in range(M):
        if S[x] == T[y]:
            dp[x + 1][y + 1] += dp_cum[x][y] + 1
            dp[x + 1][y + 1] %= MOD

        dp_cum[x + 1][y + 1] = (dp_cum[x+1][y] % MOD) \
            + (dp_cum[x][y + 1] % MOD) \
            - (dp_cum[x][y] % MOD) \
            + (dp[x + 1][y + 1] % MOD)

        dp_cum[x + 1][y + 1] %= MOD

        #print("---x,y", x, y, "----")
        #print("dp:", dp)
        #print("dp_cum", dp_cum)


ans = dp_cum[N][M] + 1
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10**9+7

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

X = [0]*(N+1)
X[0] = 1

for t in T:
    x = 1
    
    for i in range(N):
        prevX = X[i+1]

        if t == S[i]:
            X[i+1] = (X[i+1] + x)%MOD

        x =  (x + prevX)%MOD


print(sum(X)%MOD)

Submission status: Time Limit Exceeded

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

MOD = 10**9+7

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

X = [0]*(N+1)
X[0] = 1

for t in T:
    x = 1
    
    for i in range(N):
        prevX = X[i+1]

        if t == S[i]:
            X[i+1] += x

        x += prevX
        x %= MOD

print(sum(X)%MOD)

Submission status: Time Limit Exceeded

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

MOD = 10**9+7

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

X = [0]*(N+1)
X[0] = 1

for t in T:
    x = 1
    
    for i, s in enumerate(S):
        prevX = X[i+1]

        if t == s:
            X[i+1] += x

        x += prevX
        x %= MOD

print(sum(X)%MOD)

Submission status: Time Limit Exceeded

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

MOD = 10**9+7

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

X = [0]*(N+1)
X[0] = 1

for t in T:
    Y = X[:]
    x = 1
    
    for i, s in enumerate(S):
        if t == s:
            Y[i+1] += x

        x += X[i+1]
        x %= MOD

    X = Y

print(sum(Y)%MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import copy
n,m = map(int,input().split())
s = list(map(int,input().split()))
t = list(map(int,input().split()))
dp = [0 for i in range(max(n,m))]
mod = 10**9+7
if n > m:
    a = s
    b = t
else:
    a = t
    b = s
    c = copy.copy(n)
    n = copy.copy(m)
    m = copy.copy(c)
l = []
for i in range(m):
    now = b[i]
    bl = []
    for j in range(n):
        if now == a[j]:
            bl.append(j)
    l.append(bl)
for i in range(m):
    if len(l[i]) > 0:
        dp2 = copy.copy(dp)
        now1 = 0
        k = 0
        k1 = len(l[i])
        count = 0
        while k < k1:
            if now1 == l[i][k]:
                dp[now1] += 1
                dp[now1] += count
                dp[now1] %= mod
                k += 1
            count += dp2[now1]
            count %= mod
            now1 += 1
        #print(dp)
print((sum(dp)+1)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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:
    N, M = M, N
    S, T = T, S

idxs = {}
for t in T:
    arr = [i for i, x in enumerate(S) if x == t]
    idxs[t] = arr


@lru_cache(maxsize=None)
def solve(i, j):
    arr1 = S[i:]
    arr2 = T[j:]

    if len(arr1) == 0 or len(arr2) == 0:
        return 1

    ans = 0
    t = arr2[0]

    t_idxs = idxs[t]
    l = bisect.bisect_left(t_idxs, i)
    # print(idxs)

    for idx in t_idxs[l:]:
        ans += solve(idx + 1, j + 1)
        ans %= MOD

    ans += solve(i, j + 1)
    ans %= MOD

    #print("i,j,ans", i, j, ans)

    return ans


r = solve(0, 0)

print(r)

Submission status: Time Limit Exceeded

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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:
    N, M = M, N
    S, T = T, S


@lru_cache(maxsize=None)
def solve(i, j):
    arr1 = S[i:]
    arr2 = T[j:]

    if len(arr1) == 0 or len(arr2) == 0:
        return 1

    ans = 0
    t = arr2[0]

    idxs = [i for i, x in enumerate(arr1) if x == t]
    # print(idxs)

    for idx in idxs:
        ans += solve(i + idx + 1, j + 1)
        ans %= MOD

    ans += solve(i, j + 1)
    ans %= MOD

    #print("i,j,ans", i, j, ans)

    return ans


r = solve(0, 0)

print(r)

Submission status: Time Limit Exceeded

Solution code:
#common subsequence
n,m=map(int,input().split())
mod=10**9+7
a=list(map(int,input().split()))
b=list(map(int,input().split()))
dp=[[0 for i in range(m+1)] for j in range(n+1)]
#dp[i][j]=aのi番目、bのj番目まででの個数
#求めたいのはdp[n][m]
for i in range(m+1):
    dp[0][i]=1
for i in range(n+1):
    dp[i][0]=1
dp[0][0]=1
for i in range(1,n+1):
    for j in range(1,m+1):
        if a[i-1]==b[j-1]:
            dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod
        else:
            dp[i][j]=(dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1])%mod
print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
mod = 10 ** 9 + 7

def main():
	n, m = map(int, input().split())
	*s, = map(int, input().split())
	*t, = map(int, input().split())
	dp = [[1] * (m + 1)] + [[1] + [0] * m for _ in range(n)]
	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] * (s[i] != t[j])) % mod
	print(dp[n][m])

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N, M = lr()
S = [0] + lr()
T = [0] + lr()
dp = [[0] * (M+1) for _ in range(N+1)]
dp_cum = [[0] * (M+1) for _ in range(N+1)]
dp[0][0] = 1; dp_cum[0][0] = 1
for i in range(N+1):
    dp_cum[i][0] = 1
for j in range(M+1):
    dp_cum[0][j] = 1

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

answer = dp_cum[N][M] % MOD
print(answer)
# 02

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
def main():
    t = [int(t)for t in input().split()]
    n,m = t[0],t[1]

    s = [int(z)for z in input().split()]
    t = [int(z)for z in input().split()]
    
    dp = [[0]*(m+1)for _ in range(n+1)]
    dpsum = [[0]*(m+1) for _ in range(n+1)]

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

    print((dpsum[n][m]+1) % (10**9+7))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
def main():
    t = [int(t)for t in input().split()]
    n,m = t[0],t[1]

    s = [int(z)for z in input().split()]
    t = [int(z)for z in input().split()]
    
    dp = [[0]*(m+1)for _ in range(n+1)]
    dpsum = [[0]*(m+1) for _ in range(n+1)]

    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i+1][j+1] = (dpsum[i][j]+1) % (10**9+7)
            else:
                dp[i+1][j+1] = 0
            
            dpsum[i+1][j+1] = dpsum[i+1][j] + dpsum[i][j+1] - dpsum[i][j] + dp[i+1][j+1]

    print((dpsum[n][m]+1) % (10**9+7))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import defaultdict
  import bisect
  n,m = map(int,input().split())
  s = list(map(int,input().split()))
  t = list(map(int,input().split()))
  mod = 10**9+7
  p = max(n,m)
  if n>m:
    t.extend((0,)*(n-m))
  else:
    s.extend((0,)*(m-n))
  dcs = defaultdict(list)
  dct = defaultdict(list)
  dp = [[1 for i in range(p+1)] for j in range(p+1)]
  for i in range(p):
    if s[i] != 0:
      dcs[s[i]].append(i)
    if t[i] != 0:
      dct[t[i]].append(i)
  def update(i,j):
    val = dp[i-1][j-1]
    x = s[i-1]
    y = t[j-1]
    if dct[x]:
      k = bisect.bisect_left(dct[x],j-1)
      if k != 0:
        val += dp[i][dct[x][k-1]+1]-dp[i-1][dct[x][k-1]+1]
    if dcs[y]:
      l = bisect.bisect_left(dcs[y],i-1)
      if l != 0:
        val += dp[dcs[y][l-1]+1][j]-dp[dcs[y][l-1]+1][j-1]
    if x == y:
      val += dp[i-1][j-1]
    dp[i][j] = val%mod

  for i in range(1,p+1):
    for j in range(1,p+1):
      update(i,j)
  print(dp[-1][-1])
main()