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

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

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

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

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

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

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

    return

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
[N,M] = list(map(int,input().split()))
S = list(map(int,input().split()))
T = list(map(int,input().split()))

ta = np.zeros((N+1,M+1))
ta[0,0]=1
wa = np.zeros((N+1,M+1))
wa[0,:]=1
wa[:,0]=1
output = 1
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            ta[i,j]=wa[i-1,j-1]
            wa[i,j]=(wa[i-1,j]+wa[i,j-1])%(10**9+7)
        else:
            wa[i,j]=(wa[i-1,j]+wa[i,j-1]-wa[i-1,j-1]+(10**9+7))%(10**9+7)
output = wa[N,M]
print(int(output))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
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()

def main():
    N, M = LI()
    S = LI()
    T = LI()
    dp = [[1] * (M + 1)] + [[1] + [0] * M for _ in range(N)]
    for j in range(1, 1 + N):
        for i in range(1, 1 + M):
            if S[j - 1] == T[i - 1]:
                dp[j][i] = (dp[j][i - 1] + dp[j - 1][i]) % MOD
            else:
                dp[j][i] = (dp[j][i - 1] + dp[j - 1][i] - dp[j - 1][i - 1]) % MOD
    ans = dp[-1][-1]
    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy as de
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()]
a=[1]*(m+1)
for i,b in enumerate(s):
  d=de(a)
  k=0
  for j,c in enumerate(t):
    d[j]+=k
    if b==c:
      k+=a[j]
  d[-1]+=k
  a=de(d)
print(a[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
from bisect import bisect
from collections import defaultdict
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 n in range(N):
    for m in range(M):
        dp[n][m] = dp[n-1][m]+dp[n][m-1]-dp[n-1][m-1]
        if S[n]==T[m]:
            dp[n][m] += dp[n-1][m-1]+1
        dp[n][m] %= mod

print(dp[N-1][M-1]+1)

Submission status: Time Limit Exceeded

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

ta = [[0] * (M+1) for i in range(N+1)]
ta[0][0]=1
wa = [[0] * (M+1) for i in range(N+1)]
wa[0][:]=[1]*(M+1)
for i in range(N+1):
    wa[i][0]=1
output = 1
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            ta[i][j]=wa[i-1][j-1]
            wa[i][j]=wa[i-1][j]+wa[i][j-1]
        else:
            wa[i][j]=wa[i-1][j]+wa[i][j-1]-wa[i-1][j-1]
output = wa[N][M]%(10**9+7)
print(int(output))

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()))
assert len(S) == N
assert len(T) == M

modulo = 10 ** 9 + 7

# tab[j][i] = S[i] == T[j]
tab = [[s == t for s in S] for t in T]

# 番兵
for t in tab:
    t.append(1)
tab.append([1] * (len(S) + 1))

# 右下から計算
for j in range(M - 1, -1, -1):
    for i in range(N - 1, -1, -1):
        v  = tab[j + 1][i] + tab[j][i + 1]
        v -= 0 if tab[j][i] else tab[j + 1][i + 1]
        tab[j][i] = v % modulo

print(tab[0][0])

Submission status: Time Limit Exceeded

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

def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [[[0,0,0] for _ in range(M+1)] for _ in range(2)]
    k = 0
    for s in S:
        k ^= 1
        sum__ = 0
        for i, t in enumerate(T):
            sum_ = sum(dp[k^1][i+1])%(10**9+7)
            dp[k][i+1] = [sum_, sum(dp[k][i][1:])%(10**9+7), sum__ + 1 if t == s else 0]
            sum__ = sum_
    res = (sum(dp[k][-1]) + 1)%(10**9+7)

    return str(res)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    mod = 7 + 10 ** 9
    N, M = map(int, input().split())
    S = [int(s) for s in input().split()]
    T = [int(t) for t in input().split()]

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

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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(m + 1)] for j 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] = (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: Time Limit Exceeded

Solution code:
import numpy as np
[N,M] = list(map(int,input().split()))
S = list(map(int,input().split()))
T = list(map(int,input().split()))

ta = np.zeros((N+1,M+1))
ta[0,0]=1
wa = np.zeros((N+1,M+1))
wa[0,:]=1
wa[:,0]=1
output = 1
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            ta[i,j]=wa[i-1,j-1]%(10**9+7)
            wa[i,j]=(wa[i-1,j]+wa[i,j-1])%(10**9+7)
        else:
            wa[i,j]=(wa[i-1,j]+wa[i,j-1]-wa[i-1,j-1])%(10**9+7)
output = wa[N,M]
print(int(output))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
n, m = [int(item) for item in input().split()]
s = [int(item) for item in input().split()]
t = [int(item) for item in input().split()]

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

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

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

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



print(table[-1][-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
if N < M:
    N,M = M,N
    T = [int(x) for x in input().split()]
    S = [int(x) for x in input().split()]
else:
    S = [int(x) for x in input().split()]
    T = [int(x) for x in input().split()]

ans = 0
indl = ['#' for i in range(100001)]
sums = [0 for i in range(M)]

for i in range(N):
    a = S[i]
    if indl[a] == '#':
        indexes = [j for j, x in enumerate(T) if x == a]
        indl[a] = indexes
    else:   indexes = indl[a]
    
    for ind in indexes[::-1]:
        temp = 1 + sums[ind]
        ans += temp
        sums = sums[:ind+1] + [x + temp for x in sums[ind+1:]]
        
print((ans+1)%(1000000007))

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n, m = li()
s = list(li())
t = list(li())

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 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] + 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:
n, m = [int(item) for item in input().split()]
s = [int(item) for item in input().split()]
t = [int(item) for item in input().split()]

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M = map(int,input().split())
# N,M = 2*10**2,2*10**2
S = list(map(int,input().split()))
T = list(map(int,input().split()))
# S = [1 for i in range(N)]
# T = [1 for i in range(N)]

MOD = 1000000007

Ss = {}
Ts = {}

for n in range(N+1):
    for k in itertools.combinations(S, n):
        if k not in Ss:
            Ss[k] = 0
        Ss[k] += 1

for n in range(M+1):
    for k in itertools.combinations(T, n):
        if k not in Ts:
            Ts[k] = 0
        Ts[k] += 1

# print(Ss)
# print(Ts)

Ss[()] = 1
Ts[()] = 1


sm = 0
for k in Ss:
    if k in Ts:
        # print(k, Ss[k], Ts[k])
        sm += Ss[k]*Ts[k]

print(sm%MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
[N,M] = list(map(int,input().split()))
S = list(map(int,input().split()))
T = list(map(int,input().split()))

ta = np.zeros((N+1,M+1))
ta[0,0]=1
wa = np.zeros((N+1,M+1))
wa[0,:]=1
wa[:,0]=1
output = 1
for i in range(1,N+1):
    for j in range(1,M+1):
        if S[i-1]==T[j-1]:
            ta[i,j]=wa[i-1,j-1]
            wa[i,j]=wa[i-1,j]+wa[i,j-1]
        else:
            wa[i,j]=wa[i-1,j]+wa[i,j-1]-wa[i-1,j-1]
output = wa[N,M]%(10**9+7)
print(int(output))

Submission status: Time Limit Exceeded

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

def solve():
    N, M = map(int, input().split())
    *S, = map(int, input().split())
    *T, = map(int, input().split())
    dp = [[[0]*3 for _ in range(M+1)] for _ in range(2)]
    k,l = 0,1
    for j, s in enumerate(S, start=1):
        k,l = l,k
        for i, t in enumerate(T, start=1):
            dp[k][i] = [sum(dp[l][i]), sum(dp[k][i-1][1:]), sum(dp[l][i-1]) + 1 if t == s else 0]
    res = (sum(dp[N%2][-1]) + 1)%(10**9+7)

    return str(res)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000000)
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: Time Limit Exceeded

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

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

dp = [[0 for y in range(m + 1)] for x in range(n + 1)]
con = [[0 for y in range(m)] for x in range(n)]

MOD = 1000000007

dp[0][0] = 1
for i in range(1, n + 1):
	dp[i][0] = 1
	if s[i - 1] == t[0]:
		dp[i][1] = 2

for j in range(1, m + 1):
	dp[0][j] = 1
	if t[j - 1] == s[0]:
		dp[1][j] = 2

for i in range(n):
	for j in range(m):
		if s[i] == t[j]:
			con[i][j] = 1

for x in range(1, n + 1):
	for y in range(1, m + 1):
		tmp = 0
		for k in range(y - 1):
			if con[x - 1][k] > 0:
				tmp = tmp + dp[x - 1][k]
		for l in range(x - 1):
			if con[l][y - 1] > 0:
				tmp = tmp + dp[l][y - 1]
		tmp = tmp + dp[x - 1][y - 1]
		if con[x - 1][y - 1] > 0:
			tmp = tmp + dp[x - 1][y - 1]
		dp[x][y] = tmp % MOD

print(dp[n][m])

Submission status: Time Limit Exceeded

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

MOD = 10**9+7

dp = [[0]*M for _ in range(N)]
# dp[n][m] Sのn文字目，Tのm文字目までの場合の数

dp[0][0] = 1 + int(S[0] == T[0])

for i in range(1,N):
  dp[i][0] = dp[i-1][0] + int(S[i]==T[0])
  
for j in range(1,M):
  dp[0][j] = dp[0][j-1] + int(T[j]==S[0])
  
for n in range(1,N):
  for m in range(1,M):
    dp[n][m] = (dp[n-1][m] + dp[n][m-1] - dp[n-1][m-1] + dp[n-1][m-1]*int(S[n]==T[m]))%MOD
    

#print(dp)
print(dp[N-1][M-1])

Submission status: Time Limit Exceeded

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

def solve():
    N, M = map(int, input().split())
    *S, = map(int, input().split())
    *T, = map(int, input().split())
    dph = [[0]*(M+1), [0]*(M+1)]
    dpv = [[0]*(M+1), [0]*(M+1)]
    dpr = [[0]*(M+1), [0]*(M+1)]
    for j, s in enumerate(S, start=1):
        for i, t in enumerate(T, start=1):
            dph[j%2][i] = dph[(j-1)%2][i] + dpv[(j-1)%2][i] + dpr[(j-1)%2][i]
            dpv[j%2][i] = dpv[j%2][i-1] + dpr[j%2][i-1]
            dpr[j%2][i] = dph[(j-1)%2][i-1] + dpv[(j-1)%2][i-1] + dpr[(j-1)%2][i-1] + 1 if t == s else 0
    res = (dph[N%2][-1] + dpv[N%2][-1] + dpr[N%2][-1] + 1)%(10**9+7)


    return str(res)

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

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

waru=10**9+7

ans=1

dic_s={}
dic_t={}

for i in range(2**n):
    li=0
    for j in range(n):
        if (i>>j) & 1:
            li*=10
            li+=s[j]
    if li in dic_s.keys():
        dic_s[li]+=1
    else:
        dic_s[li]=1

for i in range(2**m):
    li=0
    for j in range(m):
        if (i>>j) & 1:
            li*=10
            li+=t[j]
    if li in dic_t.keys():
        dic_t[li]+=1
    else:
        dic_t[li]=1

count=0
for i in dic_s.keys():
    if i in dic_t.keys():
        count+=dic_s[i]*dic_t[i]

print(count%waru)

Submission status: Time Limit Exceeded

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

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

for x in range(1, N + 1):
    for y in range(1, M + 1):
        dp[x][y] = dp[x][y - 1] + dp[x - 1][y] - dp[x - 1][y - 1]
        if S[x - 1] == T[y - 1]:
            dp[x][y] += dp[x - 1][y - 1] + 1
ans = (dp[N][M] + 1) % (10 ** 9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
def add(a,b):#mod下の加算
    return (a+b)%mod

N,K = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
Slen = len(S);Tlen=len(T)
DP = [[0 for j in range(Tlen)] for i in range(Slen)]#DP[i][j]は、Sのi文字目、Tのj文字目までで一致する部分和
DP[0][0] = 1 + (S[0] == T[0])
for i,s in enumerate(S):
    for j,t in enumerate(T):
        if i==0 and j==0:continue
        if s == t:
            if i==0:
                DP[i][j]=DP[i][j-1]+1
            elif j==0:
                DP[i][j]=DP[i-1][j]+1
            else:
                DP[i][j]=(DP[i-1][j]+ DP[i][j-1])%mod
        else:
            if i==0:
                DP[i][j]=DP[i][j-1]
            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])%mod
print(DP[Slen-1][Tlen-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m = map(int, input().split())
lists = list(map(int,input().split()))
listt = list(map(int,input().split()))
c = 0
for i in range(min(n,m)+1):
    s = list(itertools.combinations(lists,i))
    t = list(itertools.combinations(listt,i))
    for j in range(len(s)):
        if s[j] in t:
            c = c+t.count(s[j])
print(c)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
if N < M:
    N,M = M,N
    T = [int(x) for x in input().split()]
    S = [int(x) for x in input().split()]
else:
    S = [int(x) for x in input().split()]
    T = [int(x) for x in input().split()]

ans = [0 for i in range(M)]
indl = ['#' for i in range(100001)]

for i in range(N):
    a = S[i]
    if indl[a] == '#':
        indexes = [j for j, x in enumerate(T) if x == a]
        indl[a] = indexes
    else:   indexes = indl[a]
    
    for ind in indexes[::-1]:
        ans[ind] += 1 + sum(ans[:ind])

print((sum(ans)+1)%(1000000007))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
N,M = map(int,input().split())
S = [0] + [int(x) for x in input().split()]
T = [0] + [int(x) for x in input().split()]

# 最後に(n,m)でとる
dp = [[0] * (M+1) for _ in range(N+1)]
# 2次元累積和、(n,m) inclusive. 
dp_cum = [[0] * (M+1) for _ in range(N+1)]

# empty
dp[0][0] = 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):
    if S[n] != T[m]:
      dp[n][m] = 0
    else:
      # (n-1, m-1)までで作れてるやつから飛んでくる
      dp[n][m] = 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] + dp[n][m]
    dp_cum[n][m] %= MOD

#print(dp)
#print(dp_cum)
answer = dp_cum[N][M]
print(answer)

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s = (s + self.tree[i]) % 1000000007
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = (self.tree[i] + x) % 1000000007
            i += i & -i


n, m = list(map(int, input().split()))
sss = list(map(int, input().split()))
ttt = list(map(int, input().split()))

bit = Bit(n + 1)

for t in ttt:
    for i in range(n - 1, -1, -1):
        s = sss[i]
        if s != t:
            continue
        bit.add(i + 2, bit.sum(i + 1) + 1)

print(bit.sum(n + 1) + 1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
MOD = 10**9 + 7
ns = len(S)
nt = len(T)
dp = [[0] * (nt + 1) for i in range(ns + 1)]
for i in range(1, ns + 1):
    for j in range(1, nt + 1):
        if (S[i - 1] == T[j - 1]):
            dp[i][j] = 1 + 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]
print((dp[ns][nt] + 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    T = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    result = solve(N, M, S, T)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 16 20:56:46 2019

@author: Yamazaki Kenichi
"""

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

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

Submission status: Time Limit Exceeded

Solution code:
import copy
N,M = list(map(int, input().split()))
S = list(map(int, input().split()))
T = list(map(int, input().split()))
ds={"":1}
dt={"":1}
for x in S:
    temp = ds.copy()
    for y in temp.keys():
        key = y+str(x)+" "
        if key not in ds:
            ds[key]=0
        ds[key]+=temp[y]
        #print(key,"increase",temp[y])
for x in T:
    temp = dt.copy()
    for y in temp.keys():
        key = y+str(x)+" "
        if key not in dt:
            dt[key]=0
        dt[key]+=temp[y]
        #print(key,"increase",temp[y])
answer=0
for x in dt.keys():
    if x in ds.keys():
        answer+=ds[x]*dt[x]
        #print(x,":",ds[x],"*",dt[x])
print(answer%(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()))
MOD = 10**9 + 7

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
S = [int(x) for x in input().split()]
T = [int(x) for x in input().split()]

ans = [0 for i in range(M)]

for i in range(N):
    indexes = [j for j, x in enumerate(T) if x == S[i]]
    for ind in indexes[::-1]:
        ans[ind] += 1 + sum(ans[:ind])

print((sum(ans)+1)%(1000000007))

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 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[0][j]=dp[0][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: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
from copy import copy
input = sys.stdin.readline
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):
    tmp = copy(dS)
    for key in tmp:
        dS[key+S[i]] += tmp[key]

for i in range(M):
    tmp = copy(dT)
    for key in tmp:
        dT[key+T[i]] += tmp[key]
    
ans = 0
for key in dS:
    ans += dS[key]*dT[key]%mod

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M =  map(int, input().split())
s = [int(x) for x in input().split()]
t = [int(x) for x in input().split()]
import itertools
hoges = []
for i in range(N+1):
	hoges.extend(list(itertools.combinations(s,i)))
hoget = []
for j in range(M+1):
	hoget.extend(list(itertools.combinations(t,j)))
sm = 0
for i in range(len(hoges)):
	for j in range(len(hoget)):
		if hoges[i] == hoget[j]:
			sm += 1
print(sm%(1000000007))