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
mod = 10**9+7
N, M = map(int, input().split())
S = "".join(input().split())
T = "".join(input().split())
dS = defaultdict(int)
dT = defaultdict(int)
dS[""] += 1
dT[""] += 1
for i in range(N):
    newkey = []
    for key in dS:
        newkey.append((key+S[i], dS[key]))
    
    for key, c in newkey:
        dS[key] += c

for i in range(M):
    newkey = []
    for key in dT:
        newkey.append((key+T[i], dT[key]))

    for key, c in newkey:
        dT[key] += c

    

ans = 0
for key in dS:
    ans += dS[key]*dT[key]%mod

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def CommomSubsequencesCount(s, t): 
  
    n1 = len(s) 
    n2 = len(t)
    dp=[[0 for i in range(n2+1)] for j in range(n1+1)] ; h= int(1e9+7)
    for i in range(1, n1 + 1): 
        for j in range(1, n2 + 1): 
            if (s[i - 1] == t[j - 1]): 
                dp[i][j] = (1 + dp[i][j - 1] + dp[i - 1][j])% h
            else: 
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] -dp[i - 1][j - 1])% h         
          
    return dp[n1][n2]

ll= lambda : list(map(int,input().split()))
testcases=1
# testcases=int(input())
for testcase in range(testcases):
	[n,m]=ll()
	s=ll()
	t=ll()
	h= int(1e9+7)
	print((CommomSubsequencesCount(s,t)+1)%h)

Submission status: Time Limit Exceeded

Solution code:
N,M = (int(x) for x in input().split())
S_arr = [int(x) for x in input().split()]
T_arr = [int(x) for x in input().split()]

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

mod = 1000000007
for n in range(N):
    for m in range(M):
        if S_arr[n] == T_arr[m]:
            dp[n+1][m+1] = (dp[n+1][m]+dp[n][m+1]) % mod
        else:
            dp[n+1][m+1] = (dp[n+1][m]+dp[n][m+1]-dp[n][m]) % mod
print(dp[N][M])

Submission status: Time Limit Exceeded

Solution code:
def CommomSubsequencesCount(s, t): 
  
    n1 = len(s) 
    n2 = len(t) 
    dp = [[0 for i in range(n2 + 1)]  
             for i in range(n1 + 1)] 
  
    for i in range(1, n1 + 1): 
  
        for j in range(1, n2 + 1): 
  
            # if character are same in both  
            # the string 
            if (s[i - 1] == t[j - 1]): 
                dp[i][j] = (1 + dp[i][j - 1] + dp[i - 1][j])% ((10**9) + 7)
            else: 
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] -dp[i - 1][j - 1])%((10**9) + 7)          
          
    return dp[n1][n2]

ll= lambda : list(map(int,input().split()))
testcases=1
# testcases=int(input())
for testcase in range(testcases):
	[n,m]=ll()
	s=ll()
	t=ll()
	print((CommomSubsequencesCount(s,t)+1)%((10**9)+7))

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7
P = []
for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            P.append((i, j))
P.sort(key=lambda x: (x[0], -x[1]))

data = [0]*(M+2)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s % MOD
def add(k, x):
    while k <= M:
        data[k] = (data[k] + x) % MOD
        k += k & -k

s = 0
for p, q in P:
    v = get(q+1) + 1
    add(q+2, v); s += v
print((s + 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
mod = int(1e9+7)

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

dp = []
for i in range(len(s)+1):
  dp.append([0] * (len(t)+1))

for i in range(1, len(s)+1):
  for j in range(1, len(t)+1):
    if s[i-1] == t[j-1]:
      dp[i][j] = (1 + dp[i-1][j] + dp[i][j-1]) % mod
    else:
      dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % mod
ans = dp[-1][-1] + 1 % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

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

# dp[i][j] = Sのi文字目、Tのj文字目まで見たときの組み合わせ総数
# dp[i][j] に対してはdp[i - 1][j - 1]の数がdp[i - 1][j]からきた数とdp[i][j - 1]から来たのでダブルカウントされている
# 従い、
# dp[i][j] += dp[i][j - 1]
# dp[i][j] += dp[i - 1][j]
# をした後で、ダブルカウント分を
# dp[i][j] -= dp[i - 1][j - 1]
# 引く(i > 0 and j > 0)
# S[i] == T[j]の場合、dp[i - 1][j - 1]から直接遷移することが出来るので、この通り数を足したうえでダブルカウントを引く
# ので、結局S[i] == T[j]の場合はダブルカウント分を引かないのと同じ挙動になる

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

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

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq

n,m = ma()
s = ips()
t = ips()
dp = [[0]*(m+1) for i in range(n+1) ] # dp[i][j]は s[i],t[j]まで見た時初めて一致する整数列の個数 0idx
tot = [[0]*(m+1) for i in range(n+1) ] #tot[n][m] n,mまで見た時に一致するもの全部, sum dp[0:i+1][0:j+1]
mod=10**9+7
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i][j]=tot[i-1][j-1]+1
        else:
            dp[i][j]=0
        tot[i][j] = (dp[i][j] + tot[i][j-1]+tot[i-1][j] -tot[i-1][j-1])%mod

print((tot[n-1][m-1]+1)%mod)
#print(tot)
#print(dp)

Submission status: Accepted

Solution code:
"""
愚直に全探索すると、O(2**N+2**M)かかる
制約的にはDPっぽいかな。
あ、これ部分文字列DPの発想に近いな。
dp[i][j] => Sのインデックスi、Tのインデックスjまでみる。インデックスi、インデックスjは使う。
nt[i][j] => Tのi項以降で数字jが出てくるインデックス。
"""
N,M = map(int,input().split())

N += 1
M += 1

S = list(map(int,input().split()))
S = [0]+S
T = list(map(int,input().split()))
T = [0]+T

dp = [[0]*M for _ in range(N)]
mod = 10**9 +7
for j in range(M):
    dp[0][j] = 1

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

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

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,M = MI()
S = [0] + LI()
T = [0] + LI()
mod = 10**9+7

dp = [[0]*(M+1) for _ in range(N+1)]
# dp[i][j] = S[:i+1] と T[:j+1] に対する答え

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

print(dp[N][M]+1)  # 空列を追加

Submission status: Accepted

Solution code:
import math
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N, M = read_ints()
    S = read_ints()
    T = read_ints()
    dp = [
        [0 for _ in range(M+1)] for _ in range(N+1)
    ]
    dp[0][0] = 1
    for i in range(1, N+1):
        dp[i][0] = 1
    for j in range(1, M+1):
        dp[0][j] = 1
    modulo = 10**9+7
    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])%modulo
            if S[i-1] == T[j-1]:
                dp[i][j] = (dp[i][j]+dp[i-1][j-1])%modulo
    return dp[N][M]


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

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 = [1]*(m+1)#Tをiまで見た時のSとの部分列のも場合の数
for i in range(n):
    tmp = dp[:]
    for j in range(m):
        if S[i]==T[j]:
            dp[j+1] = (tmp[j+1] + dp[j])%mod
        else:
            dp[j+1] =(tmp[j+1]+dp[j]-tmp[j])%mod
print(dp[-1])

Submission status: Accepted

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 = [1] * (M + 1)

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

    print(dp[M])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

    print(sdp[N][M])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    print(dp[N][M])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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 = [0] + list(map(int, input().split()))
T = [0] + list(map(int, input().split()))
 
dp_cum = [[0] * (M+1) for _ in range(N+1)]
dp_cum[0][0] = 1
for n in range(N+1):
    dp_cum[n][0] = 1
for m in range(M+1):
    dp_cum[0][m] = 1
  
for n in range(1,N+1):
    for m in range(1,M+1):
        now = 0
        if S[n] == T[m]:
            now = dp_cum[n-1][m-1]
        dp_cum[n][m] = dp_cum[n-1][m] + dp_cum[n][m-1] - dp_cum[n-1][m-1] + now
        dp_cum[n][m] %= MOD
print(dp_cum[N][M])

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

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

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):
    dp[i+1][j+1] = (dp[i+1][j]+dp[i][j+1]-dp[i][j]*int(S[i]!=T[j]))%MOD

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

Submission status: Accepted

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

    print(dp[n][m])

    return None

if __name__ == '__main__':
    main()