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: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    x,n = LI()
    if x < n:
        print(0)
    else:
        print(10)
    return

#B
def B():
    n,x = LI()
    l = LI()
    d = 0
    ans = 1
    for i in range(n):
        d += l[i]
        if d <= x:
            ans += 1
    print(ans)
    return

#C
def C():
    w,h,x,y = LI()
    ans = w*h/2
    k = 0
    if x == w/2 and y == h/2:
        k = 1
    print(ans,k)
    return

#D
def D():
    n,k = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    b.insert(0,0)
    ans = 0
    for l in range(n):
        r = bisect.bisect_left(b,b[l]+k)
        ans += n-r+1
    print(ans)
    return

#E
def E():
    n,m = LI()
    s = LI()
    t = LI()
    dp = [[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    for j in range(m+1):
        dp[0][j] = 1
    for i in range(1,n+1):
        for j in range(1,m+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j]+dp[i][j-1]
            else:
                dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
            #ここでmodをとる
    print(dp[n][m])
    return

#F
def F():
    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    x,n = LI()
    if x < n:
        print(0)
    else:
        print(10)
    return

#B
def B():
    n,x = LI()
    l = LI()
    d = 0
    ans = 1
    for i in range(n):
        d += l[i]
        if d <= x:
            ans += 1
    print(ans)
    return

#C
def C():
    w,h,x,y = LI()
    ans = w*h/2
    k = 0
    if x == w/2 and y == h/2:
        k = 1
    print(ans,k)
    return

#D
def D():
    n,k = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    b.insert(0,0)
    ans = 0
    for l in range(n):
        r = bisect.bisect_left(b,b[l]+k)
        ans += n-r+1
    print(ans)
    return

#E
def E():
    n,m = LI()
    s = LI()
    t = LI()
    dp = [[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    for j in range(m+1):
        dp[0][j] = 1
    for i in range(1,n+1):
        for j in range(1,m+1):
            if s[i-1] == t[j-1]:
                dp[i][j] += dp[i-1][j]+dp[i][j-1]
            else:
                dp[i][j] += dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
            if dp[i][j] >= mod:
                dp[i][j] %= mod
    print(dp[n][m])
    return

#F
def F():
    n = I()
    x = [None for i in range(n)]
    y = [None for i in range(n)]
    f = [None for i in range(n)]
    for i in range(n):
        a,b,d = LS()
        a = int(a)
        b = int(b)
        x[i] = a
        y[i] = b
        if d == "R":
            f[i] = (1,0)
        elif d == "L":
            f[i] = (-1,0)
        elif d == "U":
            f[i] = (0,1)
        else:
            f[i] = (0,-1)
    dx = max(x)-min(x)
    dy = max(x)-min(y)
    ans = dx*dy
    if ans == 0:
        print(0)
        quit()
    l = 0
    r = 100000000
    while r-l > 0.5:
        m = (l+r)/2
        px = [x[i]+f[i][0]*m for i in range(n)]
        py = [y[i]+f[i][1]*m for i in range(n)]
        dx = max(x)-min(x)
        dy = max(x)-min(y)
        if dx*dy < ans:
            ans = dx*dy

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
used = dd(int)

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]

used[s[0]] = 1
if N > 1 and M > 1:
    for i in range(1, N):
        used[s[i]] = 1
        for j in range(1, M):
            if used[t[j]] == 1:
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
                used[t[j]] = 2
                if s[i] == t[j]:
                    dp[i+1][j+1] += 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
    
print((dp[N][M] + 1)%MOD)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
used = dd(int)

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]

used[s[0]] = 1
if N > 1 and M > 1:
    for i in range(1, N):
        used[s[i]] = 1
        for j in range(1, M):
            if used[t[j]] == 1:
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
                used[t[j]] = 2
                if s[i] == t[j]:
                    dp[i+1][j+1] += 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

mod = 10 ** 9 + 7
note = []
total = 1

for i in range(N):
	count = 1
	for j in range(M):
		if S[i] == T[j]:
			note.append((S[i], j))
			count += 1
	total = (total * count) % mod
	
print(total)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, M= LI()
    if N > M:
        S = LI()
        T = LI()
    else:
        T = LI()
        S = LI()
    # 以下、必ず S のほうが長い状態。

    # とりあえず愚直に組んでみる。
    import itertools
    counter = 0
    for i in range(len(T) + 1):   # 短いほうでループを回す
        for x in itertools.combinations(S, i):
            for y in itertools.combinations(T, i):
                if x == y: 
                    counter += 1
                    counter //= MOD

    print(counter)

main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, m = [int(item) for item in input().split()]
s = [int(item) for item in input().split()]
t = [int(item) for item in input().split()]

dp = [[0] * (n+1) for _ in range(m+1)]
for i, tt in enumerate(t):
    val = 0 
    for j, ss in enumerate(s):
        # Update Partial
        if ss == tt:
            val += dp[i][j] + 1
        # Keep prev
        dp[i+1][j+1] += dp[i][j+1] + val
print(dp[m][n]+1)

Submission status: Wrong Answer

Solution code:
def getlist():
	return list(map(int, input().split()))

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

L = [[1 for i in range(N + 1)] for j in range(M + 1)]
for i in range(1, N + 1):
	for j in range(1, M + 1):
		if S[i - 1] == T[j - 1]:
			L[j][i] = max(L[j - 1][i - 1] * 2, L[j - 1][i] + L[j][i - 1]) % 1000000007
		else:
			L[j][i] = (L[j - 1][i] + L[j][i - 1] - L[j - 1][i - 1])

print(L[M][N] % 1000000007)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = []
A = list(map(int, input().split()))
cnt = 0
for i in range(0, N):
  x = 0
  for j in range(i, N):
    x = x + A[j]
    if x >= K:
      cnt = cnt + 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
if n < m:
    Sh, Lo = S,T
else:
    Sh, Lo = T,S
p = len(Sh) #短い
q = len(Lo) #長い

Li = [[] for i in range(q)]
Li2 = []
for i in range(p):
    a = Sh[i]
    for j in range(i,q):
        if a == Lo[j]:
            Li[i].append((i,j))
    if i < q:
        b = Lo[i]
        for j in range(i+1,p):
            if b == Sh[j]:
                Li[i].append((j,i))
    Li2.append(len(Li[i]))
#print(Li)
ans = 0
for i in range(len(Li2)):
    ans += 2^(sum(Li2[i:])+1)+2
print(ans)

Submission status: Wrong Answer

Solution code:
def getlist():
	return list(map(int, input().split()))

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

L = [[1 for i in range(N + 1)] for j in range(M + 1)]
for i in range(1, N + 1):
	for j in range(1, M + 1):
		if S[i - 1] == T[j - 1]:
			L[j][i] = max(L[j - 1][i - 1] * 2, L[j - 1][i] + L[j][i - 1]) % 1000000007
		else:
			L[j][i] = (L[j - 1][i] + L[j][i - 1] - L[j - 1][i - 1]) % 1000000007

print(L[M][N])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

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

Ds = defaultdict(int)
Dt = defaultdict(int)

L = [[1 for i in range(N + 1)] for j in range(M + 1)]
for i in range(1, N + 1):
	for j in range(1, M + 1):
		if S[i - 1] == T[j - 1]:
			L[j][i] = max(L[j - 1][i - 1] * 2, L[j - 1][i] + L[j][i - 1]) % 1000000007
		else:
			L[j][i] = (L[j - 1][i] + L[j][i - 1] - L[j - 1][i - 1]) % 1000000007

print(L[M][N])

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split()))
alist = list(map(int, input().split()))

c = 0
while sum(alist) >= K :
    c += 1
    lst2 = alist[1:]
    while sum(lst2) >= K :
        c += 1
        del lst2[0]
    del alist[-1]

print(c)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


DIV = 10**9+7

def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


def main():
    ans =0
    N,M= ints_raw()
    Ss = ints_raw()
    Ts = ints_raw()

    """Ls =[]
    l=0
    for a in As:
        l+=a
        Ls.append(l)"""
    dp = [[0]*M for _ in range(N)]
    dp[0][0]=1 if Ss[0]!=Ts[0] else 2
    for idx in range(1,N):
        dp[idx][0] = dp[idx-1][0] if Ss[idx] != Ts[0] else dp[idx-1][0]+1

    for midx in range(1, M):
        dp[0][midx] = dp[0][midx-1] if Ss[0] != Ts[midx] else dp[0][midx-1]+1

    for m in range(1,M):
        for n in range(1,N):
            dp[n][m] = dp[n][m-1]+dp[n-1][m]-dp[n-1][m-1]
            if Ss[n] ==Ts[m]:
                dp[n][m] += dp[n-1][m-1]
                dp[n][m] = dp[n][m]%DIV

    return dp[-1][-1]

print(main())

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    x,n = LI()
    if x < n:
        print(0)
    else:
        print(10)
    return

#B
def B():
    n,x = LI()
    l = LI()
    d = 0
    ans = 1
    for i in range(n):
        d += l[i]
        if d <= x:
            ans += 1
    print(ans)
    return

#C
def C():
    w,h,x,y = LI()
    ans = w*h/2
    k = 0
    if x == w/2 and y == h/2:
        k = 1
    print(ans,k)
    return

#D
def D():
    n,k = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    b.insert(0,0)
    ans = 0
    for l in range(n):
        r = bisect.bisect_left(b,b[l]+k)
        ans += n-r+1
    print(ans)
    return

#E
def E():
    n,m = LI()
    s = LI()
    t = LI()
    dp = [[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    for j in range(m+1):
        dp[0][j] = 1
    for i in range(1,n+1):
        for j in range(1,m+1):
            if s[i-1] == t[j-1]:
                dp[i][j] += dp[i-1][j]+dp[i][j-1]
            else:
                dp[i][j] += dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
            if dp[i][j] > mod:
                dp[i][j] %= mod
    print(dp[-1][-1])
    return

#F
def F():
    n = I()
    x = [None for i in range(n)]
    y = [None for i in range(n)]
    f = [None for i in range(n)]
    for i in range(n):
        a,b,d = LS()
        a = int(a)
        b = int(b)
        x[i] = a
        y[i] = b
        if d == "R":
            f[i] = (1,0)
        elif d == "L":
            f[i] = (-1,0)
        elif d == "U":
            f[i] = (0,1)
        else:
            f[i] = (0,-1)
    dx = max(x)-min(x)
    dy = max(x)-min(y)
    ans = dx*dy
    if ans == 0:
        print(0)
        quit()
    l = 0
    r = 100000000
    while r-l > 0.5:
        m = (l+r)/2
        px = [x[i]+f[i][0]*m for i in range(n)]
        py = [y[i]+f[i][1]*m for i in range(n)]
        dx = max(x)-min(x)
        dy = max(x)-min(y)
        if dx*dy < ans:
            ans = dx*dy

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))

count = 0

if N<2:
    if A[0]>=K:
        count+=1

elif N<3:
    if A[0]>=K:
        count+=1
    if A[1]>=K:
        count+=1
    if sum(A)>=K:
        count+=1
else:
    for i in range(N-1):
        s = 0
        for j in range(i,N):
            s += A[j]
            if s >= K:
                count += (N-j)
#                print('!!!',A[i:j+1],sum(A[i:j+1]),count,(N-j))
                break
        
print(str(count))

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline

N, K = map(int, readline().split())
A = list(map(int, readline().split()))

P = 10 ** 9 + 7

summ = 0
ind = -1
for i,a in enumerate(A):
    summ += a
    if summ > K:
        ind = i
        break

if ind == -1:
    print(0)
    exit()

right = ind

count = len(A) - right
    
for left in range(1, len(A) + 1):
    summ -= A[left - 1]
    while summ < K:
        right += 1
        if right >= len(A):
            break
        summ += A[right]
    if right >= len(A):
        break
    count += (len(A) - right) % P

print(count % P)

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

print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    S = list(map(int, readline().split()))
    T = list(map(int, readline().split()))

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

    print(dp[N][M])
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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] = 1
    for i in range(n + 1):
        for j in range(m + 1):
            if i - 1 >= 0:
                dp[i][j] += dp[i - 1][j]
            if j - 1 >= 0:
                dp[i][j] += dp[i][j - 1]
            if i - 1 >= 0 and j - 1 >= 0:
                dp[i][j] -= dp[i - 1][j - 1]
                if S[i - 1] == T[j - 1]:
                    dp[i][j] += dp[i - 1][j - 1]
            dp[i][j] %= mod
    print(dp[-1][-1])


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

S.append(0)
T.append(0)
MAX = 2005
dp0 = [[0] * MAX for _ in range(MAX)]
dp1 = [[0] * MAX for _ in range(MAX)]

dp0[0][0] = 1
for i in range(N + 1):
    for j in range(M + 1):
        dp0[i + 1][j] += dp0[i][j] % MOD
        dp1[i][j] += dp0[i][j] % MOD
        dp1[i][j + 1] += dp1[i][j] % MOD
        if S[i] == T[j]: 
            dp0[i + 1][j + 1] += dp1[i][j] % MOD
print(dp1[N][M] % 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)]
dpsum = [[0] * (m + 1) for _ in range(n + 1)]
mod = pow(10, 9) + 7
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
            if not i == 1 and not j == 1:
                dp[i][j] += dpsum[i - 1][j - 1]
                dp[i][j] %= mod
        dpsum[i][j] = dpsum[i - 1][j] + dpsum[i][j - 1] - dpsum[i - 1][j - 1] + dp[i][j]
        dpsum[i][j] %= mod
ans = dpsum[n][m] + 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,m = map(int,ipt().split())
    s = [int(i) for i in ipt().split()]
    t = [int(i) for i in ipt().split()]
    ans = 0

    dp = [[1]*(m+1) for i in range(n+1)]
    for i,si in enumerate(s):
        for j,tj in enumerate(t):
            if si == tj:
                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]

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

    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M = list(map(int, input().split()))
S = np.array(list(map(int, input().split())))
T = np.array(list(map(int, input().split())))
mod = int(1e9+7)
"""
dp[i][j] : S の i 文字目までと T の j 文字目までを考慮し、
この 2 文字 (S[i] と T[j]）をペアにするときの場合の数とすると、

dp[i][j] = (sum(dp[1:i-1][1:j-1]) + 1 if S[i] == T[j] else 0)
このsumの部分をどうもとめるか。

最終的な答えはsum(dp[:][:])。

2-D cumsumをつかう
i,j = 0のときにきをつけて
DS[i][j] = DS[i-1][j] + DS[i][j-1] - DS[i-1][j-1] + dp[i][j]
"""

#dp = [[ 0 for _ in range(M)] for _ in range(N)]
dp = np.zeros((N,M))
# -1のIndexAccessをゼロにしたいので、ひとつ大きめに取っておく。
DS = np.zeros((N+1,M+1))

for i in range(N):
  for j in range(M):
    if S[i] != T[j]:
      dp[i, j] = 0
    else:
      dp[i, j] += 1
    ## 愚直ループを2次元部分和でなんとかする
    #for k in range(i):
    #  for l in range(j):
    #    dp[i][j] += dp[k][l]
    ## 愚直ループnp版。
      #dp[i,j] += np.sum(dp[:i, :j])
      dp[i,j] += DS[i-1,j-1]
      dp[i,j] %= mod
    DS[i,j] = DS[i-1,j] + DS[i,j-1] - DS[i-1,j-1] + dp[i,j]
    DS[i,j] %= mod
print(int(DS[-2][-2])+1)
#print(dp)
#print(DS)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M = list(map(int, input().split()))
S = np.array(list(map(int, input().split())))
T = np.array(list(map(int, input().split())))
mod = int(1e9+7)
"""
dp[i][j] : S の i 文字目までと T の j 文字目までを考慮し、
この 2 文字 (S[i] と T[j]）をペアにするときの場合の数とすると、

dp[i][j] = (sum(dp[1:i-1][1:j-1]) + 1 if S[i] == T[j] else 0)
このsumの部分をどうもとめるか。

最終的な答えはsum(dp[:][:])。

2-D cumsumをつかう
i,j = 0のときにきをつけて
DS[i][j] = DS[i-1][j] + DS[i][j-1] - DS[i-1][j-1] + dp[i][j]
"""

#dp = [[ 0 for _ in range(M)] for _ in range(N)]
dp = np.zeros((N,M), dtype = int)
# -1のIndexAccessをゼロにしたいので、ひとつ大きめに取っておく。
DS = np.zeros((N+1,M+1), dtype = int)

for i in range(N):
  for j in range(M):
    if S[i] != T[j]:
      dp[i, j] = 0
    else:
      dp[i, j] += 1
    ## 愚直ループを2次元部分和でなんとかする
    #for k in range(i):
    #  for l in range(j):
    #    dp[i][j] += dp[k][l]
    ## 愚直ループnp版。
      #dp[i,j] += np.sum(dp[:i, :j])
      dp[i,j] += DS[i-1,j-1]
      dp[i,j] %= mod
    DS[i,j] = DS[i-1,j] + DS[i,j-1] - DS[i-1,j-1] + dp[i,j]
    DS[i,j] %= mod
print(DS[-2][-2]+1)
#print(dp)
#print(DS)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M = list(map(int, input().split()))
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = int(1e9+7)
"""
dp[i][j] : S の i 文字目までと T の j 文字目までを考慮し、
この 2 文字 (S[i] と T[j]）をペアにするときの場合の数とすると、

dp[i][j] = (sum(dp[1:i-1][1:j-1]) + 1 if S[i] == T[j] else 0)
このsumの部分をどうもとめるか。

最終的な答えはsum(dp[:][:])。

2-D cumsumをつかう
i,j = 0のときにきをつけて
DS[i][j] = DS[i-1][j] + DS[i][j-1] - DS[i-1][j-1] + dp[i][j]
"""

#dp = [[ 0 for _ in range(M)] for _ in range(N)]
dp = np.zeros((N,M), dtype = int)
# -1のIndexAccessをゼロにしたいので、ひとつ大きめに取っておく。
DS = np.zeros((N+1,M+1), dtype = int)

for i in range(N):
  for j in range(M):
    if S[i] != T[j]:
      dp[i, j] = 0
    else:
      dp[i, j] += 1
    ## 愚直ループを2次元部分和でなんとかする
    #for k in range(i):
    #  for l in range(j):
    #    dp[i][j] += dp[k][l]
    ## 愚直ループnp版。
      #dp[i,j] += np.sum(dp[:i, :j])
      dp[i,j] += DS[i-1,j-1]
      dp[i,j] %= mod
    DS[i,j] = DS[i-1,j] + DS[i,j-1] - DS[i-1,j-1] + dp[i,j]
    DS[i,j] %= mod
print(DS[-2][-2]+1)
#print(dp)
#print(DS)

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 = int(1e9+7)
"""
dp[i][j] : S の i 文字目までと T の j 文字目までを考慮し、
この 2 文字 (S[i] と T[j]）をペアにするときの場合の数とすると、

dp[i][j] = (sum(dp[1:i-1][1:j-1]) + 1 if S[i] == T[j] else 0)

2-D cumsumをつかう
i,j = 0のときにきをつけて
DS[i][j] = DS[i-1][j] + DS[i][j-1] - DS[i-1][j-1] + dp[i][j]
"""

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

  
for i in range(N):
  for j in range(M):
    #dp[i][j] = (sum(dp[:i-1][:j-1]) + 1 if S[i-1] == T[j-1] else 0)
    if S[i] != T[j]:
      continue
    dp[i][j] += 1
    for k in range(i):
      for l in range(j):
        #if i==k and j==l:
          #continue
        dp[i][j] += dp[k][l]
    #ii = i+1 if i>0 else 0
    #jj = j+1 if j>0 else 0
    #Sumpart = DS[ii][j] + DS[i][jj] - DS[ii][jj] + dp[ii][jj]
    #dp[i][j] += (Sumpart + 1 if S[i] == T[j] else 0)
    #DS[i][j] = DS[i][j-1] + dp[i][j]
    
ans = 1 # 何も選ばない
for p in dp:
  ans += sum(p)
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class cumsum2D:
    def __init__(self, data):
        self.N = len(data)
        self.M= len(data[0])
        self.cum = [[0] * (self.M + 1) for _ in range(self.N + 1)]
        for i in range(self.N):
            for j in range(self.M):
                self.cum[i + 1][j + 1] = self.cum[i][j + 1] + self.cum[i + 1][j] - self.cum[i][j] + data[i][j]

    def get(self,x1,y1,x2,y2):
        """
        長方形の領域 [x1,x2)*[y1,y2) の範囲内にインプットされた数字の和を取る
        """
        return self.cum[x2][y2] - self.cum[x1][y2] - self.cum[x2][y1] + self.cum[x1][y1]

########################################################################################################
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [[0]*(M+1) for _ in range(N+1)]
cum = [[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][j] += cum[i][j] + 1
        cum[i + 1][j + 1] = cum[i][j + 1] + cum[i + 1][j] - cum[i][j] + dp[i][j]
print((cum[N][M]+1)%MOD)