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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 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 input()
from collections import defaultdict

n, m = LI()
ss = LI()
ts = LI()
ans += 1

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

for i in range(n):
    for j in range(m):
        dp[i][j] = 1 if ss[i] == ts[j] else 0

index_d = defaultdict(list)

for i in range(n):
    for j in range(m):
        if i != 0:
            x = dp[n-i+1][n-j] 
        else:
            x = 0
        if j != 0:
            y = dp[n-i][n-j+1] 
        else:
            y = 0
        dp[n-i][n-j] = dp[n-i][n-j] + x + y
print((dp[0][0] + 1) % MOD)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

p = 10**9 + 7

def LCS(S,T,n,m):
  #初期化
  dp=[[0 for i in range(m+1)] for j in range(n+1)]
  for i in range(m+1): dp[i][0] = 1
  for j in range(n+1): dp[0][j] = 1
    
  #DP
  for i in range(n):
    for j in range(m):
      dp[i+1][j+1] = dp[i][j+1]%p + dp[i+1][j]%p
      if S[i] != T[j]:
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1)%p
  return dp[n][m]%p

print(LCS(S,T,n,m))

Submission status: Runtime Error

Solution code:
inputa = list(map(int, input().split()))
inputb = list(map(int, input().split()))
inputc = list(map(int, input().split()))

seta = set(inputb) & set(inputc)

countb = []
countc = []
result = 0
for i in seta:
  countb.append(inputb.count(i))
  countc.append(inputc.count(i))
for i in range(len(countb)):
  for j in range(i)
  result += countb[i] * countc[j]

print(result)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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


def m():
    for s in range(len(S)):
        for t in range(len(T)):
            solve(s, t)
    res = solve(N, M)

    print(res+1)


@lru_cache(None)
def solve(s, t):
    if s == 0 or t == 0:
        return 1
    if s == 1:
        return T.count(S[s-1]) + 1
    if t == 1:
        return S.count(T[t-1]) + 1
    acc = 0
    acc += solve(s-1, t)
    a = [i for i, e in enumerate(T[:t]) if e == S[s-1]]
    for t2 in [i for i, e in enumerate(T[:t-1]) if e == S[s-1]]:
        acc += solve(s-1, t2)
    return acc


m()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 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 input()
from collections import defaultdict

n, m = LI()
ss = LI()
ts = LI()
ans += 1

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

for i in range(n):
    for j in range(m):
        dp[i][j] = 1 if ss[i] == ts[j] else 0

index_d = defaultdict(list)
for i, v in enumerate(ss):
    index_d[i][j for j, x in enumerate(ts) if x == v]

for i in range(n):
    for j in range(m):
        if i != 0:
            x = dp[n-i+1][n-j] 
        else:
            x = 0
        if j != 0:
            y = dp[n-i][n-j+1] 
        else:
            y = 0
        dp[n-i][n-j] = dp[n-i][n-j] + x + y
print((dp[0][0] + 1) % MOD)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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


def m():
    for s in range(len(S)):
        for t in range(len(T)):
            solve(s, t)
    res = solve(N, M)

    print(res)


@lru_cache(None)
def solve(s, t):
    if s == 0 or t == 0:
        return 1
    if s == 1:
        return T.count(S[s-1]) + 1
    if t == 1:
        return S.count(T[t-1]) + 1
    acc = 0
    acc += solve(s-1, t)
    a = [i for i, e in enumerate(T[:t]) if e == S[s-1]]
    for t2 in [i for i, e in enumerate(T[:t]) if e == S[s-1]]:
        acc += solve(s-1, t2)
    return acc

m()

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
s = na()
t = na()
mod = 10**9+7

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

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**10)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
s = na()
t = na()
mod = 10**9+7

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

Submission status: Runtime Error

Solution code:
def search(s_iti,t_iti_list,n,memo3,memo1,s):
     if s_iti==n-1:
          return 0
     else:
          tmp=memo3[memo1.index(s[s_iti+1])]
          tmp2=[]
          for i in tmp:
               if i-1 in t_iti_list:
                    tmp2.append(i)
          return search(s_iti+1,tmp2,n,memo3,memo1,s)+len(tmp2)
def main():
     n,m=map(int,input().split())
     s=list(map(int,input().split()))
     t=list(map(int,input().split()))
     memo1=[]#si
     memo2=[]#siとなるsiの位置
     memo3=[]#siとなるtiの位置
     for i in range(n):
          if s[i] not in memo1:
               memo2.append([i])
               memo1.append(s[i])
               tmp_ti=[]
               for j in range(m):
                    if t[j]==s[i]:
                         tmp_ti.append(j)
               memo3.append(tmp_ti)
          else:
               memo2[memo1.index(s[i])].append(i)
     cnt=0
     for i in range(len(memo1)):
          cnt+=len(memo2[i])*len(memo3[i])
          for j in memo2[i]:
               cnt+=search(j,memo3[i],n,memo3,memo1,s)
     print(cnt+1)
                    
     
     
if __name__=='__main__':
     main()

Submission status: Runtime Error

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: Runtime Error

Solution code:
mod = 10**9+7
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
memo = [[-1]*(M+1) for _ in range(N)]
List = [[]for _ in range(N)]

for i in range(N):
    for j in range(M):
        if S[i]==T[j]:
            List[i].append(j)
def dp(i, j):
    if i==N-1:
        cnt = 0
        for k in List[i]:
            if j<k:
                cnt+=1
        return (cnt+1)%mod
    res = 0
    for k in List[i]:
        if j<k:
            if memo[i+1][k]<0:
                memo[i+1][k]=dp(i+1, k)
            res+=memo[i+1][k]
    if memo[i+1][j]<0:
        memo[i+1][j]=dp(i+1, j)
    res+=memo[i+1][j]
    return res%mod
print(dp(0, -1)%mod)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
memo = [[-1]*(M+1) for _ in range(N)]
List = [[]for _ in range(N)]

for i in range(N):
    for j in range(M):
        if S[i]==T[j]:
            List[i].append(j)
def dp(i, j):
    if i==N-1:
        cnt = 0
        for k in List[i]:
            if j<k:
                cnt+=1
        return (cnt+1)%mod
    res = 0
    for k in List[i]:
        if j<k:
            if memo[i+1][k]<0:
                memo[i+1][k]=dp(i+1, k)
            res+=memo[i+1][k]
    if memo[i+1][j]<0:
        memo[i+1][j]=dp(i+1, j)
    res+=memo[i+1][j]
    return res%mod
print(dp(0, -1)%mod)

Submission status: Runtime Error

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)]
from collections import defaultdict
data=[defaultdict(int) for i in range(M+1)]
dp[0][0]=1
for j in range(1,1+M):
    dp[i][j]=dp[i][j-1]
for i in range(1,1+N):
    dp[i][0]=dp[i-1][0]
    data[0][S[i-1]]=(data[0][S[i-1]]+dp[i][0])%mod
    for j in range(1,1+M):
        data[j][S[i-1]]=(data[j][S[i-1]]+dp[i-1][j])%mod
        dp[i][j]=(data[j-1][T[j-1]]+dp[i][j-1])%mod
print(dp[N][M])

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
s = na()
t = na()
mod = 10**9+7

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

Submission status: Runtime Error

Solution code:
w,h,x,y = map(int, input().split())

# 横
men1 = w * y
men2 = w * (h-y)

# 縦
men3 = x * h
men4 = (w-x) * h


#print("{0} {1} {2} {3}".format(str(men1), str(men2), str(men3), str(men4)))
out1 = max(min(men1, men2), min(men3, men4))
if min(men1, men2) == min(men3, men4):
    out2 = 1
elif (h / w) == (y / x):
    out2 = 1
else:
    out2 = 0

print("{0} {1}".format(out1, out2))