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:
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)
for i in range(1,p+1):
  for j in range(1,p+1):
    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
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10 ** 20
MOD = 10**9 + 7
def combmod(n, k, mod=MOD):
    if k == 0:
        return 1
    if k == 1:
        return n
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret


class Segtree_op():
    def __init__(self, n):
        self.size = 1
        while (n >= 1):
            self.size = self.size << 1
            n = n // 2

        self.arr = [self.unit() for i in range(self.size * 2)]

    def op(self, lch, rch):
        # update min with holding index
        return lch + rch

    def unit(self):
        return 0

    def update(self, k, val):
        k += self.size - 1
        self.arr[k] = val
        while (k):
            k = (k - 1) // 2
            self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])

    def query(self, l, r):
        L = l + self.size
        R = r + self.size
        s = self.unit()
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.arr[R - 1])

            if L & 1:
                s = self.op(s, self.arr[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

def update_daikou(st, k):
    st.update(k, (st.query(0,k+1)) % MOD)
    # print(st.arr)

def main():
    n,m = getList()
    snums = getList()
    snums.reverse()
    tnums = getList()

    index = {}
    for i, snum in enumerate(snums):
        if snum not in index:
            index[snum] = [n - i]
        else:
            index[snum].append(n-i)

    st = Segtree_op(n)
    st.update(0,1)
    for tnum in tnums:
        if tnum in index:
            for num in index[tnum]:
                update_daikou(st, num)

    print(st.query(0, n + 1) % MOD)

    # st = Segtree_op(4)
    # update_daikou(st, 3)
    # update_daikou(st, 1)
    # update_daikou(st, 4)
    # update_daikou(st, 2)
    # update_daikou(st, 3)
    #
    # print(st.arr)
    # # print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10 ** 20
MOD = 10**9 + 7
def combmod(n, k, mod=MOD):
    if k == 0:
        return 1
    if k == 1:
        return n
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret


class Segtree_op():
    def __init__(self, n):
        self.size = 1
        while (n >= 1):
            self.size = self.size << 1
            n = n // 2

        self.arr = [self.unit() for i in range(self.size * 2)]

    def op(self, lch, rch):
        # update min with holding index
        return lch + rch

    def unit(self):
        return 0

    def update(self, k, val):
        k += self.size - 1
        self.arr[k] = val
        while (k):
            k = (k - 1) // 2
            self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])

    def query(self, l, r):
        L = l + self.size
        R = r + self.size
        s = self.unit()
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.arr[R - 1])

            if L & 1:
                s = self.op(s, self.arr[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

def update_daikou(st, k):
    st.update(k, (st.query(0,k+1)) % MOD)
    # print(st.arr)

def main():
    n,m = getList()
    snums = getList()
    tnums = getList()

    index = {}
    for i, snum in enumerate(snums[::-1]):
        if snum not in index:
            index[snum] = [n - i]
        else:
            index[snum].append(n-i)

    st = Segtree_op(len(snums))
    st.update(0,1)
    for tnum in tnums:
        if tnum not in index:
            pass
        else:
            for num in index[tnum]:
                update_daikou(st, num)

    print(st.query(0, len(snums) + 1) % MOD)



    # st = Segtree_op(4)
    # update_daikou(st, 3)
    # update_daikou(st, 1)
    # update_daikou(st, 4)
    # update_daikou(st, 2)
    # update_daikou(st, 3)
    #
    # print(st.arr)
    # # print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,m = map(int,input().split())
    s = list(map(int,input().split()))
    t = list(map(int,input().split()))
    dp = [[0]*(m+2) for i in range(n+2)]
    sdp = [[0]*(m+2) for i in range(n+2)]
    dp[0][0] = 1
    sdp[1][1] = 1
    for i in range(n+1):
        for j in range(m+1):
            if i == 0 and j == 0:continue
            if i>=1 and j >= 1 and s[i-1] == t[j-1]:
                dp[i][j] = sdp[i][j]%Mod
            sdp[i+1][j+1] = (sdp[i+1][j] + sdp[i][j+1] - sdp[i][j] + dp[i][j])%Mod

    print(sdp[n+1][m+1]%Mod)

if __name__ == "__main__":
    main() 
    
#endline===============================================

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

Submission status: Time Limit Exceeded

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

dp = [[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] = (dp[i+1][j] + dp[i][j+1] + 1) % MOD
    else:
      dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j]) % MOD

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

Submission status: Time Limit Exceeded

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


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

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

print(sum([sum(x) % MOD for x in dp]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import collections

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

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

ans_s=[0]
for i in range(N):
    temp=[]
    for j in range(len(ans_s)):
        ans_s.append(ans_s[j]*10+S[i])
#print(ans_s)


ans_t=[0]
for i in range(M):
    temp=[]
    for j in range(len(ans_t)):
        #print(ans_t[j],T[i])
        ans_t.append(ans_t[j]*10+T[i])
#print(ans_t)

cand_s=collections.Counter(ans_s)
cand_t=collections.Counter(ans_t)

ans=0
for item in cand_s:
    ans+=cand_s[item]*cand_t[item]

print(ans%(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()))

M = 10**9+7

dp = [[1]*(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] = 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] %= M

#print(dp)
print(dp[-1][-1]%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 = 1000000007

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

for i, si in enumerate(s):  
  for j, tj in enumerate(t):
    if i > 0:
      dp[i][j] += dp[i-1][j]
      
    if j > 0:
      dp[i][j] += dp[i][j-1]

    if si == tj:
      dp[i][j] += 1
    elif i > 0 and j > 0:
      dp[i][j] -= dp[i-1][j-1]
    
    dp[i][j] %= MOD

print((dp[n-1][m-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 = 1000000007

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

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

    if j > 0:
      dp[i][j] += dp[i][j-1]
      dp[i][j] %= MOD

    if si == tj:
      dp[i][j] += 1
      dp[i][j] %= MOD
    elif i > 0 and j > 0:
      dp[i][j] -= dp[i-1][j-1]
      dp[i][j] %= MOD

print((dp[n-1][m-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 = 1000000007

sum = [[0] * m for _ in range(n)] 

for i, si in enumerate(s):  
  for j, tj in enumerate(t):
    sum[i][j] += sum[i-1][j] if i > 0 else 0
    sum[i][j] %= MOD
    sum[i][j] += sum[i][j-1] if j > 0 else 0
    sum[i][j] %= MOD

    if si == tj:
      sum[i][j] += 1
    else:
      sum[i][j] -= sum[i-1][j-1] if i > 0 and j > 0 else 0
      sum[i][j] %= MOD

    sum[i][j] %= MOD


print((sum[n-1][m-1] + 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    S = tuple(map(int, input().split()))
    T = tuple(map(int, input().split()))
    l = [[0] * (M + 1) for _ in range(N + 1)]
    l[0] = [1] * (M + 1)
    for i in range(N + 1):
        l[i][0] = 1
    r = 1
    for i in range(1, N+1):
        for j in range(1, M+1):
            if S[i-1] == T[j-1]:
                r += l[i-1][j-1]
                l[i][j] = l[i][j-1] + l[i-1][j]
            else:
                l[i][j] = l[i][j-1] + l[i-1][j] - l[i-1][j-1]
    print(r % MOD)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    S = tuple(map(int, input().split()))
    T = tuple(map(int, input().split()))
    l = [[0] * (M + 1) for _ in range(N + 1)]
    r = [[0] * (M + 1) for _ in range(N + 1)]
    r[0][0] = 1
    l[0] = [1] * (M + 1)
    for i in range(N + 1):
        l[i][0] = 1
    for i in range(1, N+1):
        for j in range(1, M+1):
            if S[i-1] == T[j-1]:
                r[i][j] = l[i-1][j-1]
            l[i][j] = r[i][j] + l[i][j-1] + l[i-1][j] - l[i-1][j-1]
    print(sum(sum(i) for i in r) % MOD)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    S = list(map(int, input().split())) + [0]
    T = list(map(int, input().split())) + [0]
    dp0 = [[0] * (M + 5) for _ in range(N + 5)]
    dp1 = [[0] * (M + 5) for _ in range(N + 5)]
    MOD = 10 ** 9 + 7
    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] % MOD
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    s = LI()
    t = LI()
    a = [[1 if i==j else 0 for j in t] for i in s]
    u = [0] * m
    for i in range(n):
        c = a[i]

        for j in range(1,m):
            if c[j] == 1:
                c[j] += u[j-1]

        e = c[:]
        for j in range(1,m):
            e[j] += e[j-1]
            e[j] %= mod

        if i > 0:
            for j in range(m):
                e[j] += u[j]
                e[j] %= mod
        u = e

    r = sum(map(lambda x: sum(x) % mod, a)) + 1

    return r % mod


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    s = LI()
    t = LI()
    a = [[0] * m for _ in range(n)]
    u = [[0] * m for _ in range(n)]
    for i in range(n):
        b = s[i]
        c = a[i]
        d = u[i-1]
        for j in range(m):
            if b != t[j]:
                continue
            k = 1
            if i>0 and j>0:
                k += d[j-1]
            c[j] = k
        e = u[i] = c[:]
        for j in range(1,m):
            e[j] += e[j-1]
            e[j] %= mod
        if i > 0:
            for j in range(m):
                e[j] += d[j]
                e[j] %= mod

    r = sum(map(lambda x: sum(x) % mod, a)) + 1
    r %= mod

    return r


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    s = LI()
    t = LI()
    a = [[0] * m for _ in range(n)]
    u = [[0] * m for _ in range(n)]
    for i in range(n):
        b = s[i]
        c = a[i]
        d = u[i-1]
        for j in range(m):
            if b != t[j]:
                continue
            k = 1
            if i>0 and j>0:
                k += d[j-1]
            c[j] = k
        e = u[i] = c[:]
        for j in range(1,m):
            e[j] += e[j-1]
            e[j] %= mod
        if i > 0:
            for j in range(m):
                e[j] += d[j]
                e[j] %= mod

    r = sum(map(sum, a)) + 1
    r %= mod

    return r


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    s = LI()
    t = LI()
    sc = collections.defaultdict(lambda: collections.defaultdict(int))
    sc[0][(0,0)] = 1
    for i in range(n):
        c = s[i]
        for j in range(i,-1,-1):
            for k,v in sc[j].items():
                nk = ((k[0] * 997 + c) % mod, (k[1] * 991 + c) % mod)
                sc[j+1][nk] += v

    tc = collections.defaultdict(lambda: collections.defaultdict(int))
    tc[0][(0,0)] = 1
    for i in range(m):
        c = t[i]
        for j in range(i,-1,-1):
            for k,v in tc[j].items():
                nk = ((k[0] * 997 + c) % mod, (k[1] * 991 + c) % mod)
                tc[j+1][nk] += v

    r = 0
    for i in range(min(n,m)+1):
        for k,v in tc[i].items():
            r += sc[i][k] * v
            r %= mod

    return r


print(main())

Submission status: Time Limit Exceeded

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

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            sumdp = 0
            for k in range(i):
                for l in range(j):
                    sumdp += dp[k][l]
            dp[i][j] = (sumdp + 1) % mod
res = 1
for i in range(n):
    for j in range(m):
        res += dp[i][j]
        res %= mod
print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def f():
    import sys
    input=sys.stdin.readline
    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()]
    mod=10**9+7
    dp=[[0]*(m+1) for i in range(2)]
    dp[0][0]=1
    for i in range(n+1):
        for j in range(m+1):
            if i!=0:
                dp[i%2][j]=dp[(i-1)%2][j]
            if j!=0:
                dp[i%2][j]+=dp[i%2][j-1]
            if i!=0 and j!=0:
                if s[i-1]!=t[j-1]:
                    dp[i%2][j]-=dp[(i-1)%2][j-1]
            dp[i%2][j]%=mod
    print(dp[n%2][m])


f()

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] * n for _ in range(m)]

t0 = T[0]
count = 0
for i in range(n):
    if S[i] == t0:
        count += 1
    DP[0][i] = count

s0 = S[0]
count = 0
for j in range(m):
    if T[j] == s0:
        count += 1
    DP[j][0] = count

for j in range(1, m):
    for i in range(1, n):
        total = DP[j-1][i] + DP[j][i-1] - DP[j-1][i-1]
        if T[j] == S[i]:
            total += DP[j-1][i-1] + 1
        total %= mod
        DP[j][i] = total

ans = DP[m-1][n-1] + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f():
    import sys
    input=sys.stdin.readline
    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()]
    mod=10**9+7
    dp=[[0]*(m+1) for i in range(n+1)]
    dp[0][0]=1
    for i in range(n+1):
        for j in range(m+1):
            if i!=0:
                dp[i][j]+=dp[i-1][j]
            if j!=0:
                dp[i][j]+=dp[i][j-1]
            if i!=0 and j!=0:
                if s[i-1]!=t[j-1]:
                    dp[i][j]-=dp[i-1][j-1]
            dp[i][j]%=mod
    print(dp[-1][-1])


f()

Submission status: Time Limit Exceeded

Solution code:
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()]
mod=10**9+7
dp=[[0]*(m+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n+1):
    for j in range(m+1):
        if i!=0:
            dp[i][j]+=dp[i-1][j]
        if j!=0:
            dp[i][j]+=dp[i][j-1]
        if i!=0 and j!=0:
            if s[i-1]!=t[j-1]:
                dp[i][j]-=dp[i-1][j-1]
        dp[i][j]%=mod
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

    MOD = 10 ** 9 + 7

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

    ans = dp1[N][M] % MOD
    print (ans)
    return 

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    MOD = 10 ** 9 + 7

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

    ans = dp1[N][M]
    print (ans)
    return 

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

MOD = 10 ** 9 + 7

dp0 = [[0] * 2005 for _ in range(2005)]
dp1 = [[0] * 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 i < N and j < M and S[i] == T[j]:
            dp0[i + 1][j + 1] += dp1[i][j]
        dp0[i][j] %= MOD
        dp1[i][j] %= MOD
        
ans = dp1[N][M]
print (ans)

Submission status: Time Limit Exceeded

Solution code:
MOD=1000000007
n,m=map(int,input().split())

S=[int(_) for _ in input().split()]
T=[int(_) for _ in input().split()]

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):
        if S[i]!=T[j]:
            dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]-dp[i][j]
            dp[i+1][j+1]%=MOD
        else:
            dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]
            dp[i+1][j+1]%=MOD
print((dp[n][m])%MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    n,m=map(int,input().split())
    s=list(map(int,input().split()))
    t=list(map(int,input().split()))
    dp=np.zeros((n+1,m+1),dtype=np.int32)
    dp[:,m]=1
    dp[n,:]=1
    for i in range(n-1,-1,-1):
        temp=s[i]
        for j in range(m-1,-1,-1):
            if t[j]!=temp:
                dp[i,j]=(dp[i+1,j]+dp[i,j+1]-dp[i+1,j+1])%(10**9+7)
            else:
                dp[i,j]=(dp[i+1,j]+dp[i,j+1])%(10**9+7)
    print(dp[0,0])
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

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

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