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: Accepted

Solution code:
from collections import defaultdict
def solve():
  ans = 0
  mod = 10**9+7
  s = defaultdict(lambda: -1)
  t = defaultdict(lambda: -1)
  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)]
  for j in range(M+1):
    dp[0][j] = 1
  for i in range(1,N+1):
    dp[i][0] = 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]
      dp[i][j]%= mod
  ans = dp[-1][-1]%mod
  return ans
print(solve())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    S = tuple(map(int, input().split())) #1行ベクトル
    T = tuple(map(int, input().split()))
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

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

    for i in range(1,N+1):
        for j in range(1,M+1):
            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]+=dp[i-1][j-1]
            dp[i][j]%=mod
    print(dp[-1][-1])
    #printe(dp)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def count_cs(str1, str2, MOD):
    """文字列str1, str2の共通部分列(Common Subsequence, CS)を数え上げる。
    添字が異なる場合は異なる部分列として考える。
    計算量 O(|str1||str2|)
    """
    dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] + 1
            else:
                dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j]
            dp[i + 1][j + 1] %= MOD
    return (dp[len(str1)][len(str2)] + 1) % MOD


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


print(count_cs(s, t, MOD))

Submission status: Accepted

Solution code:
from numpy import*
N,M,*U= map(int,open(0).read().split())
p=ones(M+1)
for s in U[:N]:p[1:]=((p[:-1]*(s==array(U[N:]))).cumsum()+p[1:])%(10**9+7)
print(int(p[-1]))

Submission status: Accepted

Solution code:
from numpy import*
N,M,*U= map(int,open(0).read().split())
T=array(U[N:])
p=ones(M+1)
for s in U[:N]:p[1:]=((p[:-1]*(s==T)).cumsum()+p[1:])%(10**9+7)
print(int(p[-1]))

Submission status: Accepted

Solution code:
from numpy import*
N,M,*U= map(int,open(0).read().split())
T=array(U[N:])
p=ones(M+1,dtype="i8")
for s in U[:N]:p[1:]=((p[:-1]*(s==T)).cumsum()+p[1:])%(10**9+7)
print(p[-1])

Submission status: Accepted

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

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m = mi()
    s = lmi()
    t = lmi()
    
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n+1):
        dp[i][0] = 1
    for j in range(m+1):
        dp[0][j] = 1

    for i in range(n):
        for j in range(m):
            # print(dp)
            if s[i] == t[j]:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1]) % mod
            else:
                # 片方使う or 両方使わない                   だぶりを 1 回減らす
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j]) % mod
    print(dp[n][m])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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[i][j]:nからi番目までとtからj番目まで取ったときの共通部分整数列の組み合わせ
dp=[[1]*(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]
        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[n][m])

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    S = read_list()
    T = read_list()

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

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

MOD = 10 ** 9 + 7

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

@njit
def solve(N, M, S, T):
    dp = np.ones((N+1, M+1), np.int64)
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
            if s != t:
                dp[i+1][j+1] -= dp[i][j]
            dp[i+1][j+1] %= MOD
    return dp[N][M]

print(solve(N, M, S, T))

Submission status: Accepted

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

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

print(dp[N][M])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
X=[[0]*(M+1) for i in range(N+1)]
DP=[[0]*M for i in range(N)]
DP[0][0]=0
mod=10**9+7
for i in range(N):
  for j in range(M):
    if S[i]==T[j]:
      DP[i][j]=(X[i][j]+1)%mod
    X[i+1][j+1]=(DP[i][j]+X[i+1][j]+X[i][j+1]-X[i][j])%mod
print((X[N][M]+1)%mod)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

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

print(dp[N][M])

Submission status: Accepted

Solution code:
N,M= map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
mod=10**9+7
ans=[[0 for e in range(M)] for f in range(N)]
rui=[[0 for e in range(M)] for f in range(N)]
for j in range(M):
 if j!=0:
  rui[0][j]=rui[0][j-1]
 if S[0]==T[j]:
  ans[0][j]=1
  rui[0][j]+=ans[0][j]
for i in range(1,N):
 rui[i][0]=rui[i-1][0]
 if S[i]==T[0]:
  ans[i][0]=1
  rui[i][0]+=ans[i][0]
for i in range(1,N):
 for j in range(1,M):
  rui[i][j]=rui[i][j-1]+rui[i-1][j]-rui[i-1][j-1]
  if S[i]==T[j]:
   ans[i][j]=(rui[i-1][j-1]+1)
   rui[i][j]+=ans[i][j]
  rui[i][j]%=mod
print((rui[N-1][M-1]+1)%mod)

Submission status: Accepted

Solution code:
import collections
n,m = map(int, raw_input().split(' '))
s,t = map(int, raw_input().split(' ')), map(int, raw_input().split(' '))
dp,prefix = [[0 for j in range(len(t))] for i in range(len(s))], [[0 for j in range(len(t))] for i in range(len(s))]
total = 1
mod = (10 ** 9) + 7
for ii in range(len(s)):
	for jj in range(len(t)):
		if s[ii] == t[jj]:
			dp[ii][jj] = 1+ (prefix[ii-1][jj-1] if ii-1>=0 and jj-1>=0 else 0)
			total += dp[ii][jj]
			total %= mod
		prefix[ii][jj] += prefix[ii - 1][jj] if ii - 1 >=0 else 0
		prefix[ii][jj] += prefix[ii][jj - 1] if jj - 1 >=0 else 0
		prefix[ii][jj] -= prefix[ii - 1][jj - 1] if (jj - 1 >=0) and (ii-1) >=0 else 0
		prefix[ii][jj] += dp[ii][jj]
		prefix[ii][jj] %= mod
		
print total

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, M = map(int, readline().split())
    #空の部分列を考えるために適当な値で0番目の要素を埋めてインデックスを調節している
    #dpの更新で考えるのは1番目以降であるから0番目の要素が同じ要素であろうとなかろうと影響しない
    S = [0] + [int(i) for i in readline().split()]
    T = [0] + [int(i) for i in readline().split()]
    
    #共通部分列の集合と共通部分列の数対応について考えるために補助的にDPを定義
    #DP(i, j):=Sのi文字目、Tのj文字目までの共通部分列の集合

    #実際に求める数を導くためのdpテーブル
    #dp(i, j):=Sのi文字目、Tのj文字目までの共通部分列の数

    #「受け継ぐ要素（変化しない共通部分列）」と「増える分の要素」に注目して考える
    #S_i+1 != T_j+1のとき、DP(i+1, j+1) = DP(i+1, j) ∩ DP(i, j+1) 
    #S_i+1 = T_j+1のとき、DP(i+1, j+1) = DP(i+1, j) ∩ DP(i, j+1) ∩ (操作によって増えた共通部分列の集合)
    #（操作によって増えた共通部分列の集合）の要素数はdp(i, j)である
    # ∵ DP(i, j)の各要素である共通部分列の最後にそれぞれS_iを追加してできた共通部分列の集合が（操作によって増えた共通部分の集合）である

    #DPをdpに対応付けながら実装していく

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

    #空の部分列が共通部分列となるので、dp[0][x]およびdp[x][0]の値は1として初期化する
    for i in range(N+1):
        dp[i][0] = 1
    for i in range(M+1):
        dp[0][i] = 1
    
    #dpの更新
    P = int(1e9)+7
    for i in range(N):
        for j in range(M):
            if S[i+1] != T[j+1]:
                #和集合の要素数を考えるとき、重複部分の要素数を引かなければならない
                #DP(i+1, j)とDP(i, j+1)の重複部分はDP(i, j)であり要素数はdp(i, j)である
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
                dp[i+1][j+1] %= P
            else:
                #下の式の最後のdp[i][j]は増えた共通部分列の数である
                #dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j] + dp[i][j] 
                #整理すると以下の式になる
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] 
                dp[i+1][j+1] %= P
    print(dp[N][M])
if __name__ == '__main__':
    main()

Submission status: Accepted

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, ei in enumerate(s, 1):
    for j, ej in enumerate(t, 1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
        if ei == ej:
            dp[i][j] += dp[i-1][j-1]

        dp[i][j] %= mod

ans = dp[n][m]
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
s = list(map(int, readline().split()))
t = list(map(int, readline().split()))
dp = [[0] * (n + 1) for _ in range(m + 1)]
cumsum = [[0] * (n + 1) for _ in range(m + 1)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i, tt in enumerate(t):
    i += 1
    for j, ss in enumerate(s):
        j += 1
        if tt == ss:
            dp[i][j] = cumsum[i - 1][j - 1] + 1
            dp[i][j] %= mod
        else:
            dp[i][j] = 0
        cumsum[i][j] = cumsum[i - 1][j] + cumsum[i][j - 1] - cumsum[i - 1][j - 1] + dp[i][j]
        cumsum[i][j] %= mod
print(cumsum[-1][-1] + 1)

Submission status: Accepted

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

dp1 = [[0] * (m + 1) for _ in range(n + 1)] # ends with (i, j)
dp2 = [[0] * (m + 1) for _ in range(n + 1)] # cumsum

dp1[0][0] = 1
for i in range(n + 1):
    dp2[i][0] = 1
for j in range(m + 1):
    dp2[0][j] = 1

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


print(dp2[-1][-1])

Submission status: Accepted

Solution code:

# start:2020-05-28 00:22:02
import sys
sys.setrecursionlimit(10**8)
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)]
rui = [[0]*(M+1) for _ in range(N+1)]
ans = 1
for i in range(N):
    for j in range(M):
        if S[i]==T[j]:
            dp[i+1][j+1] = rui[i][j] + 1
            dp[i+1][j+1] %= MOD
            ans += dp[i+1][j+1]
            ans %= MOD    
        rui[i+1][j+1] = rui[i+1][j] + rui[i][j+1] - rui[i][j] + dp[i+1][j+1]
        rui[i+1][j+1] %= MOD

print(ans)

Submission status: Accepted

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] * n
for tj in t:
    acc = 0
    for i, si in enumerate(s):
        acc = (acc + dp[i]) % 1000000007
        if si == tj:
            dp[i] = (acc + 1) % 1000000007
ans = 1
for x in dp:
    ans = (ans + x) % MOD
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

neq = (S[:, None] != T[None, :])
dp = np.ones(M + 1, dtype=np.int64)
for i in range(N):
    new_dp = dp.copy()
    new_dp[1:] -= dp[:-1] * neq[i]
    np.cumsum(new_dp, out=new_dp)
    dp = new_dp % MOD
print(dp[M])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = tuple(map(int, input().split()))
T = tuple(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]
        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: Accepted

Solution code:
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)]
accum = [[0]*(M+1) for _ in range(N+1)]
MOD = 10**9+7

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

ans = (sum(map(sum, dp))+1)%MOD
print(ans)

Submission status: Accepted

Solution code:
def main():
    mod = 10**9 + 7
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))
    V = [1] * N
    for t in T:
        p, q = 1, 1
        for i, (s, v) in enumerate(zip(S, V)):
            V[i] = q = v + q if s == t else v + q - p
            p = v
    return V[-1] % mod

print(main())

Submission status: Accepted

Solution code:
def main():
    mod = 10**9 + 7
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))
    u = [1] * (N + 1)
    v = [1] * (N + 1)
    for t in T:
        for i, s in enumerate(S, 1):
            if s == t:
                v[i] = v[i - 1] + u[i]
            else:
                v[i] = v[i - 1] + u[i] - u[i - 1]
        u, v = v, u
    return u[-1] % mod

print(main())

Submission status: Accepted

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

    print(dp[N][M])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ABC130E

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


M = 10**9+7
n,m = map(int, input().split())
s = input().split()
t = input().split()
n = len(s)
m = len(t)
dp = [[0] * (m+2) for _ in range(n+2)] # i-1, j-1で終わる部分列の組の個数
ss = [[0] * (m+2) for _ in range(n+2)] # sum(dp[0][0]+...+ dp[i-1][j-1])

for i in range(n+2):
    dp[i][0] = 0
    ss[i][0] = 0
for j in range(m+2):
    dp[0][j] = 0
    ss[0][j] = 0

for i in range(1, n+1):
    for j in range(1, m+1):
        if s[i-1]==t[j-1]:
            dp[i][j] += (ss[i][j] + 1)
            dp[i][j] %= M
        ss[i+1][j+1] = (-ss[i][j]+ss[i+1][j]+ss[i][j+1]+dp[i][j]) % M
print(ss[n+1][m+1]+1)

Submission status: Accepted

Solution code:
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):
    dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]
    if s[i]!=t[j]:dp[i+1][j+1]-=dp[i][j]
    dp[i+1][j+1]%=(10**9+7)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    mod = 10**9 + 7

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(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)]

    for i, val_s in enumerate(s, 1):
        for j, val_t in enumerate(t, 1):
            num = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
            if val_s == val_t:
                num += dp[i - 1][j - 1] + 1
            num %= MOD
            dp[i][j] = num

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = list(map(int, input().split()))
S.append(-1)
T = list(map(int, input().split()))
T.append(0)
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] % 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
ans = dp1[N][M] % mod
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    S=tuple(map(int,input().split()))
    T=tuple(map(int,input().split()))
    dp=[[0]*(M+1) for _ in range(N+1)]
    SUM=[[0]*(M+2) for _ in range(N+2)]
    ans=1
    for s in range(N):
        for t in range(M):
            if S[s]==T[t]:
                dp[s+1][t+1]=SUM[s+1][t+1]+1
                ans+=dp[s+1][t+1]
                ans%=MOD
            else:
                dp[s+1][t+1]=0
            SUM[s+2][t+2]=SUM[s+1][t+2]+SUM[s+2][t+1]-SUM[s+1][t+1]+dp[s+1][t+1]
            SUM[s+2][t+2]%=MOD
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
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)]
SUM = [[0 for i in range(M+1)] for j in range(N+1)]
mod = 10 ** 9 + 7

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

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

Submission status: Accepted

Solution code:
#ABC130-E Common Subsequence
"""
問題：
整数列のリストが与えられる
空であるものも含めて、sとtの部分列として等しいものの個数を求めよ
解法：
LCSのmaxではなくsumのバージョンでかつ、
数え上げなので重複をなくさなければならない。
具体的には、
dp[i][j]:sをi文字目迄見た時のtをj文字目迄見た時に、
dp0:横方向(j方向)を優先して遷移した後に、縦方向(i方向)への遷移を行った時の合計
dp1:縦方向、横方向への遷移を行った時の合計
として、dp1[-1][-1]が答え。

"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m = map(int,readline().split())
s = list(map(int,readline().split())) + [-1]
t = list(map(int,readline().split())) + [-2]
mod = 10**9+7

#dp table
dp0 = [[0]*(m+2) for _ in range(n+2)]
dp1 = [[0]*(m+2) for _ in range(n+2)]
dp0[0][0] = 1
#process1
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: Accepted

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

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

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

print(dp[N][M])