Problem:


Score : 700 points

Problem Statement

There are N stones arranged in a row. The i-th stone from the left is painted in the color C_i.

Snuke will perform the following operation zero or more times:

Choose two stones painted in the same color. Repaint all the stones between them, with the color of the chosen stones.

Find the number of possible final sequences of colors of the stones, modulo 10^9+7.

Constraints

1 \leq N \leq 2\times 10^5

1 \leq C_i \leq 2\times 10^5(1\leq i\leq N)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
C_1
:
C_N

Output

Print the number of possible final sequences of colors of the stones, modulo 10^9+7.

Sample Input 1

5
1
2
1
2
2

Sample Output 1

3

We can make three sequences of colors of stones, as follows:

(1,2,1,2,2), by doing nothing.

(1,1,1,2,2), by choosing the first and third stones to perform the operation.

(1,2,2,2,2), by choosing the second and fourth stones to perform the operation.

Sample Input 2

6
4
2
5
4
2
4

Sample Output 2

5

Sample Input 3

7
1
3
1
2
3
3
2

Sample Output 3

5



Sample input:
5
1
2
1
2
2


Sample output:
3

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([-1*random.randint(1,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

n=I()
a=[int(input()) for i in range(n)]
dp=[1]+[0]*n
p=[-1]*(1+2*10**5)
for i in range(1,n+1):
    dp[i]+=dp[i-1]
    c=a[i-1]
    if p[c]!=-1 and p[c]!=i-1:
        dp[i]+=dp[p[c]]
    p[c]=i
    dp[i]%=mo

print(dp[-1]%mo)

Submission status: Accepted

Solution code:
# dp
import sys
from collections import defaultdict

stdin = sys.stdin
 
ni = lambda:int(ns())
na = lambda:list(map(int,stdin.readline().split()))
ns = lambda:stdin.readline().rstrip()  # ignore trailing spaces

MOD = 10 ** 9 + 7
d = dict()

N = ni()
C = [ni() for _ in range(N)]
dp = [1] * N
d[C[0]] = 0

for i in range(1, N):
    c = C[i]
    dp[i] = dp[i-1]
    if c in d:
        if d[c] != i-1:
            dp[i] += dp[d[c]]
    d[c] = i
    dp[i] %= MOD

print(dp[N-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
mod = 10**9+7

N = int(input())
dp = [0] * (N+1)
dp[0] = 1
prev = defaultdict(lambda: -1)
for i in range(1, N+1):
    c = int(input())
    dp[i] = dp[i-1]
    if prev[c] >= 0:
        if prev[c] != i-1:
            dp[i] = (dp[i] + dp[prev[c]]) % mod
    prev[c] = i

print(dp[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    n = int(input())
    cc = [int(input()) for _ in range(n)]
    dp = [0] * (n + 1)
    dp[0] = 1
    ll = defaultdict(int)
    pc = -1
    for r, c in enumerate(cc):
        dp[r + 1] = dp[r]
        if c == pc: continue
        dp[r + 1] = (dp[r + 1] + ll[c]) % md
        ll[c] = (ll[c] + dp[r]) % md
        pc = c
    print(dp[n])

main()

Submission status: Accepted

Solution code:
n=int(input())
c=[int(input()) for _ in [0]*n]
l=[-1]*200001
dp=[1]*n
l[c[0]]=0
mod=10**+9+7
for i in range(1,n):
	ci=c[i]
	if l[ci] not in [-1,i-1]:
		dp[i]=(dp[i-1]+dp[l[ci]])%mod
	else:
		dp[i]=dp[i-1]
	l[ci]=i
print(dp[n-1])

Submission status: Accepted

Solution code:
n = int(input())
C = [int(input()) for i in range(n)]
nc = 2 * 10 ** 5 + 3
mod = 10**9+7

A = [0] * n
B = [-1] * nc

A[-1] = 1
B[C[-1]] = n-1
# print(B)

for i in range(n-2, -1, -1):
    if B[C[i]] != -1 and B[C[i]] != i+1:
        A[i] = (A[i+1] + A[B[C[i]]]) % mod
    else:
        A[i] = A[i+1]
    B[C[i]] = i
    # print(A,B)

# print(A)
# print(B)
print(A[0])

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
arr=[int(input()) for _ in range(n)]
tmp=[arr[0]]
for i in range(1,n):
  if arr[i]!=tmp[-1]:
    tmp.append(arr[i])
n=len(tmp)
arr=tmp
dp=[0]*n
dp[0]=1
g=[[] for _ in range(max(arr)+1)]
for i in range(n):
  g[arr[i]].append(i)
cnt=[0]*(max(arr)+1)
lim=[0]*(max(arr)+1)
for i in range(max(arr)+1):
  lim[i]=len(g[i])
for i in range(n-1):
  dp[i+1]+=dp[i]
  dp[i+1]%=mod
  if cnt[arr[i]]+1<lim[arr[i]]:
    dp[g[arr[i]][cnt[arr[i]]+1]]+=dp[i]
    dp[g[arr[i]][cnt[arr[i]]+1]]%=mod
    cnt[arr[i]]+=1
print(dp[-1]%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict

N=int(input())
C=[int(input()) for _ in range(N)]

d = defaultdict(int)

ans=1
for i,c in enumerate(C):
    if i>=1 and C[i-1]==C[i]:
        continue
    else:
        ans+=d[c]
        d[c]=ans
        
        ans%=10**9+7
        d[c]%=10**9+7
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
MOD = 10**9+7
dp = [0]*(N+1)
dp[0] = 1
dic = defaultdict(int)
p = -1
for i in range(N):
  c = int(input())
  if c==p:
    dp[i+1] = dp[i]
    continue
  dic[c] += dp[i]
  dp[i+1] = dic[c]%MOD
  p = c
#  print(dp)

print(dp[-1]%MOD)

Submission status: Accepted

Solution code:

N = int(input())

C = []

for i in range(N):

    c = int(input())

    if len(C) == 0 or C[-1] != c-1:
        C.append(c-1)

lis = []
last = [-1] * (2 * (10**5))

for i in range(len(C)):

    if i == 0:
        lis.append(1)
    
    elif last[C[i]] == -1 or last[C[i]] == i-1:
        lis.append(lis[-1])

    else:
        lis.append(lis[-1]+lis[last[C[i]]])

    lis[-1] %= 10 ** 9 + 7
    last[C[i]] = i


print (lis[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)
r = 1
p = ""
for _ in range(int(input())):
  c = input()
  if c != p:
    r = (r + d[c]) % (10**9 + 7)
    d[c] = r
  p = c
print(r)

Submission status: Accepted

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
MOD = 10**9 + 7

dp = [0] * (N + 1)
colorToIndex = [-1] * (max(C) + 10)
colorToIndex[C[0]] = 0
dp[0] = 1

for i, color in enumerate(C[1:], start=1):
    prevIndex = colorToIndex[color]
    dp[i] = dp[i - 1]

    if prevIndex != i - 1:
        dp[i] += dp[prevIndex]

    dp[i] %= MOD
    colorToIndex[color] = i

ans = dp[N - 1]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
MOD = 10**9+7

# PreStore:先頭から順に見ていったとき、その色と同じ色の石が前回現れた位置。
PreStone = [-1 for _ in range(2*(10**5))]

# 先頭から順に見ていったとき、ある色が現れ、次に同じ色が現れたとき、
# 前者と後者の間の色を変えるパターンが追加されるわけだから、
# 追加されるパターンの数は、前者が現れた時点でのパターン数と同じ。
# ただし、前者と後者の間には1つ以上の石が存在する必要がある。
dp = [1 for _ in range(N)]
for i in range(N):
  if PreStone[C[i]-1] not in [-1, i-1]:
    dp[i] = dp[i-1] + dp[PreStone[C[i]-1]]
  else:
    dp[i] = dp[i-1]
  dp[i] %= MOD
  PreStone[C[i]-1] = i
print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())
C = dict()
i, cp, hist, ans = 0, 0, [0]*N, 0
for _ in range(N):
    c = int(input())
    if c != cp:
        if c in C.keys():
            temp = hist[C[c]] + 1
            hist[i] = hist[i-1] + temp
            ans += temp
        else:
            hist[i] += hist[i-1]
        C[c], cp = i, c
        i += 1
print((ans+1) % (10**9+7))

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
C = [int(input()) for i in range(N)]
MOD = 10 ** 9 + 7

dp = [0] * (N + 1)
dp[0] = 1

D = defaultdict(int)
for i, c in enumerate(C, start=1):
    dp[i] += dp[i - 1]
    if D[c] > 0 and D[c] != i - 1:
        dp[i] += dp[D[c]]
    dp[i] %= MOD
    D[c] = i

print(dp[-1] % MOD)

Submission status: Accepted

Solution code:
N=int(input())
C=[int(input()) for i in range(N)]
a=[0]*N
p={}
m=10**9+7
for i,c in enumerate(C):
    a[i]=a[i-1]
    if c in p and p[c]<i-1:
        a[i]=(a[i]+a[p[c]]+1)%m
    p[c]=i
print(a[-1]+1)

Submission status: Accepted

Solution code:
n = int(input())
a = []
ans = []
c = {}
for i in range(n):
    a.append(int(input()))
    ans.append(0)
ans[0] = 1
c[a[0]] = 0
for i in range(1,n):
    if a[i] not in c:
        c[a[i]] = i
    if a[i] == a[i-1]:
        ans[i] = ans[i-1]
    else:
        ans[i] = (ans[i-1] + ans[c[a[i]]]) % 1000000007
        c[a[i]] = i
print(ans[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
c=[]
tmp=0
num=0
for i in range(n):
    m=int(input())
    if m!=tmp:
        c.append(m)
        tmp=m
        num+=1
n=num
from collections import Counter
dp=Counter()
ans=1
mod=10**9+7
for i in range(n):
    dp[c[i]]=(dp[c[i]]+ans)%mod
    ans=dp[c[i]]
print(ans)

Submission status: Accepted

Solution code:
n = int(input(""))
mod = 1e9+7
maxn = 200000
x = []
f = []
sum = [0 for j in range(0,maxn+1)]
def add(a,b):
    s = (a+b)%mod
    return s
f.append(1)
x.append(-1)
for i in range(1,n+1):
    x.append(int(input()))
    if(x[i]==x[i-1]):
        f.append(f[i-1])
    else :
        f.append(add(f[i-1],sum[x[i]]))
        sum[x[i]]=f[i]
print(int(f[n]))

Submission status: Accepted

Solution code:
N=int(input())
L=[]
for i in range(N):
    n=int(input())
    L.append(n)

dp=[0 for i in range(N)]
dp[0]=1
mod=10**9+7
D=dict()
D[L[0]]=1
for i in range(1,N):
    if L[i]==L[i-1]:
        dp[i]=dp[i-1]
    elif L[i] not in D:
        D[L[i]]=dp[i-1]
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1]+D[L[i]]
        dp[i]%=mod
        D[L[i]]=dp[i]
    #print(dp)
print(dp[-1]%mod)
#print(D)

Submission status: Accepted

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]

dp = [0] * N
dp[0] = 1
d = {C[0]:0}

for i in range(1, N):
    if C[i] in d and C[i] != C[i-1]:
        dp[i] = (dp[i-1] + dp[d[C[i]]]) % (10**9+7)
    else:
        dp[i] = dp[i-1]
    d[C[i]] = i

print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
oth = [int(input()) for _ in range(n)]
mod = 10**9 + 7
l = list()
for x in oth:
    if l and l[-1] == x:
        continue
    l.append(x)
lenl = len(l)
last = [-1] * 200001
l2 = [-1] * 200001
for i, a in enumerate(l):
    l2[i] = last[a]
    last[a] = i

dp = [0] * lenl
dp[0] = 1
for i in range(1, lenl):
    prev = 0 if l2[i] < 0 else dp[l2[i]]
    dp[i] = (dp[i - 1] + prev) % mod
print(dp[-1])

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
c = [I() for _ in range(n)]
dp1,dp2 = [0]*(n+1),[0]*(max(c)+1)
dp1[0] = 1
for i in range(n):
    if dp2[c[i]] == 0:
        dp1[i+1] = dp1[i]
        dp2[c[i]] = dp1[i]
        dp2[c[i]] %= mod
    else:
        if c[i] == c[i-1]:
            dp1[i+1] = dp1[i]
            continue
        dp1[i+1] += dp2[c[i]]
        dp1[i+1] += dp1[i]
        dp2[c[i]] += dp1[i]
        dp2[c[i]] %= mod
        dp1[i+1] %= mod
print(dp1[-1] % mod)

Submission status: Accepted

Solution code:
MOD=1000000007
N=int(input())
d = {}
pairs=[-1]*N

for i in range(N):
    c = int(input())
    if c in d and i-d[c]>1:
        pairs[d[c]] = i
    d[c]=i
    
dp1,dp2=[0]*N,[0]*N
prev=1
for src in range(N):
    dp2[src]=(prev+dp1[src])%MOD
    dst = pairs[src]
    if dst>0:
        dp1[dst] = (dp1[dst]+dp2[src])%MOD
    prev=dp2[src]
print(dp2[-1])

Submission status: Accepted

Solution code:
#B問題
N = int(input())
C = [int(input()) for i in range(N)]
mod = 10**9+7
D = []

for i in range(N-1):
    if C[i] != C[i+1]:
        D.append(C[i])
D.append(C[-1])

M = len(D)
dp = [0 for i in range(M+1)]
dp[0] = 1
count = [0 for i in range(2*10**5+1)]

for i in range(1,M+1):
    dp[i] = dp[i-1]
    dp[i]+=count[D[i-1]]
    dp[i]%=mod
    count[D[i-1]]+=dp[i-1]
    count[D[i-1]]%=mod
    
print(dp[M])

Submission status: Accepted

Solution code:
#B問題
N = int(input())
C = [int(input()) for i in range(N)]
mod = 10**9+7
D = []

for i in range(N-1):
    if C[i] != C[i+1]:
        D.append(C[i])
D.append(C[-1])

M = len(D)
dp = [0 for i in range(M+1)]
dp[0] = 1
count = [0 for i in range(2*10**5+1)]

for i in range(1,M+1):
    dp[i] = dp[i-1]
    dp[i]+=count[D[i-1]]
    dp[i]%=mod
    count[D[i-1]]+=dp[i-1]
    count[D[i-1]]%=mod
    
print(dp[M])

Submission status: Accepted

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

MOD = 10**9 + 7

N = int(input())
C = [int(input()) for _ in range(N)]

dp = [0]*(N+1)
c_to_i = [-1]*(2*10**5+1)
dp[0] = 1
c_to_i[C[0]] = 0
for i,c in enumerate(C[1:],1):
    prev_i = c_to_i[c]
    dp[i] = dp[i-1]
    if prev_i != i-1:
        dp[i] += dp[prev_i]
        dp[i] %= MOD
    c_to_i[c] = i

answer = dp[N-1]
print(answer)

Submission status: Accepted

Solution code:
import sys

MOD = 10**9 + 7

N = int(input())
Cs = [int(sys.stdin.readline())-1 for _ in range(N)]

numCs = [0] * (2 * 10**5)
anss = [0] * N
numCs[Cs[0]] = 1
anss[0] = 1
for i, C in enumerate(Cs[1:], 1):
    if C == Cs[i-1]:
        anss[i] = anss[i-1]
    else:
        numCs[C] += anss[i-1]
        anss[i] = numCs[C] % MOD

print(anss[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    num = int(input())
    data = [int(input()) for i in range(num)]

    dic = defaultdict(int)
    mod = 10 ** 9 + 7
    dp = [1 for i in range(num + 1)]

    for i in range(num):
        if i != 0:
            if data[i] == data[i - 1]:
                dp[i + 1] = dp[i]
                continue

        now_num = data[i]
        dp[i + 1] = (dp[i] + dic[now_num]) % mod
        dic[now_num] += dp[i]
        dic[now_num] %= mod

    print(dp[num])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
n=int(input())
c=[0]+[int(input()) for i in range(n)]
d=collections.defaultdict(int)
mod=10**9+7
dp=[1 for i in range(n+1)]
for i in range(0,n):
    if c[i]==c[i+1]:
        dp[i+1]=dp[i]
    else:
        t=c[i+1]
        dp[i+1]=(dp[i]+d[t])%mod
        d[t]+=dp[i]
        d[t]%=mod
print(dp[n])

Submission status: Accepted

Solution code:

n = int(input())
ans_list = [ 1 for i in range(n) ]

color_list = [ -1 for i in range(2*(10**5))] 
for i in range(n):
    color = int(input()) - 1

    if color_list[color] not in [-1,i-1]:
        ans_list[i] = ans_list[i-1] + ans_list[color_list[color]]
    else:
        ans_list[i] = ans_list[i-1]
    ans_list[i] %= 10**9+7

    color_list[color] = i
print(ans_list[-1])

Submission status: Accepted

Solution code:
n = int(input())
c = [int(input()) for i in range(n)]
MOD = 10**9 + 7

dp = [0]*(n+1)
dp[0] = 1
memo = {}
for i in range(n):
    if c[i] not in memo:
        memo[c[i]] = i
        dp[i+1] = dp[i]
    else:
        if c[i]==c[i-1]:
            dp[i+1] = dp[i]
            memo[c[i]] = i
            continue
        # memo[c[i]]からiの区間を変えるとき
        dp[i+1] += dp[memo[c[i]]+1]
        # memo[c[i]]からiの区間を変えないとき
        dp[i+1] += dp[i]
        
        memo[c[i]] = i
        dp[i+1] %= MOD
print(dp[-1] % MOD)

Submission status: Accepted

Solution code:
n = int(input())
cs = []
for i in range(n):
    cs.append(int(input()))
dp = [0] * n
last_num = [-1] * 2 * 10**5
MOD = 10**9 + 7

for i, c in enumerate(cs):
    if i == 0:
        dp[i] = 1
        last_num[c-1] += 1
        continue
    # Fisrt color
    if(last_num[c-1] == -1):
        dp[i] += dp[i-1]
    # Previous color
    elif(last_num[c-1] == i-1):
        dp[i] += dp[i-1]
    # Reversi
    else:
        dp[i] += dp[i-1]
        dp[i] += dp[last_num[c-1]]
    dp[i] %= MOD
    last_num[c-1] = i
print(dp[n-1])

Submission status: Accepted

Solution code:
N = int( input())
C = [ int( input()) for _ in range(N)]
dp = [1]*(N+1)
colors = [1]*(2*10**5+1)
S = [-1]*(2*10**5+1)
Q = 10**9+7
for i in range(N):
    if i >= 1:
        if C[i] == C[i-1]:
            dp[i+1] = dp[i]
            continue
    if S[C[i]] == -1:
        dp[i+1] = dp[i]
        S[C[i]] = 1
        if i >= 1:
            S[C[i]] = dp[i]
        continue
    dp[i+1] = (dp[i] + S[C[i]])%Q
    S[C[i]] += dp[i]
    S[C[i]] %= Q
print(dp[N])

Submission status: Accepted

Solution code:
def solve():
    # 方針
    # 範囲で並べ方の個数を足し合わせるDP
    
    N = int(input())
    X = [int(input()) for _ in range(N)]
    MOD = int(1e9)+7
    
    colors = set()
    NoDouble = [-1]
    for x in X:
        colors.add(x)
        if x == NoDouble[-1]:
            continue
        NoDouble.append(x)
    del NoDouble[0]
    N = len(NoDouble)
    C = len(colors)

    ForIdxLastNum = [-1] * N # N番目の要素まで見たとき、その色は直前にどこに出現したか
    # 上記を作成するために、inplace な色の出現の位置を記憶
    Onetime_colors = [-1] * (2*10**5+1)

    for e,c in enumerate(NoDouble):
        if Onetime_colors[c] == -1:
            # その色は初出
            Onetime_colors[c] = e
        else:
            ForIdxLastNum[e] = Onetime_colors[c]
            Onetime_colors[c] = e
    
    
    DP = [0] * (N+1) # dp[i], i個目まで見たときの並べ方の個数
    DP[0] = 1

    for e,c in enumerate(NoDouble):
        if ForIdxLastNum[e] == -1:
            # その色は初出
            DP[e+1] = DP[e]
        else:
            lastIdx = ForIdxLastNum[e]
            DP[e+1] = (DP[lastIdx+1] + DP[e]) % MOD
    
    print(DP[N] % MOD)

            
    
    


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# input
n = int(input())

mod = pow(10, 9) + 7
c = []
dp = [0] * (n + 1)
stone_history = dict()
for i in range(n):
    stone = int(input())
    if len(c) == 0:
        dp[i + 1] = 1
    else:
        if stone in stone_history and c[-1] != stone:
            dp[i + 1] = dp[i] + stone_history[stone]
        else:
            dp[i + 1] = dp[i]

    stone_history[stone] = dp[i + 1]
    c.append(stone)

print(dp[-1] % mod)

Submission status: Accepted

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
mod = int(1e9+7)

from itertools import groupby
x = [0] + [k for k, g in groupby(C)]

dp = [0]*(len(x)) # i個目までで何通りあるか
dp[0] = 1
memo = {}

for i in range(1, len(x)):
    c = x[i]
    memo[c] = (memo.get(c,0) + dp[i-1])%mod
    dp[i] = memo[c]

print(dp[-1])

Submission status: Accepted

Solution code:
n=int(input())
arr=[int(input()) for _ in range(n)]
mod=10**9+7

dp=[0]*n
dp[0]=1

record={arr[0]:0}

for i,v in enumerate(arr):
  if i==0:
    continue
  dp[i]=dp[i-1]
  if v in record and record[v]<i-1:
    dp[i]+=dp[record[v]]
    dp[i]=dp[i]%mod
  record[v]=i
print(dp[-1])

Submission status: Accepted

Solution code:
mod=(10**9)+7
a=[0]*200005
dp=[0]*200005
s=[0]*200005
cnt=0

n=int(input())+1
for i in range (1, n):
	x=int(input())
	if x!=a[cnt]:
		cnt=cnt+1
		a[cnt]=x

cnt+=1

dp[0]=1
for i in range (1, cnt):
	dp[i]=dp[i-1]
	dp[i]=(dp[i]+s[a[i]])%mod
	s[a[i]]=(s[a[i]]+dp[i-1])%mod

print(dp[cnt-1])

Submission status: Accepted

Solution code:
N=int(input())
MOD=10**9+7
memo={}

#prev_numがその時点での組み合わせ数
prev_num=1
prev=None

for _ in range(N):
  c=int(input())
  if c==prev:
    continue
  tmp=prev_num
  if c in memo:
    tmp+=memo[c]
  tmp%=MOD
  #memo[c]にそれまでの組み合わせの数が入ることで、
  #次にcが出てきた時にどれぐらい通りが増えるかが分かる
  memo[c]=tmp
  prev_num=tmp
  prev=c
print(prev_num)

Submission status: Accepted

Solution code:
MOD = 10**9+7

n = int(input())

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

if(n == 1):
    print("1")
    exit()
if(n==2):
    print("1")
    exit()

dic = {}

ind = [0 for i in range(n+1)]

for i in range(1,n+1):
    c = int(input())
    if c in dic:
        ind[i] = dic[c][-1]
        dic[c].append(i)
    else:
        dic[c] = [i]

dp[0] , dp[1],dp[2] = 1,1,1

for i in range(3,n+1):
    dp[i] = (dp[i] + dp[i-1]) % MOD
    if(ind[i] == 0):continue
    if(ind[i] == i-1):continue
    dp[i] = (dp[i] + dp[ind[i]]) % MOD

print(dp[n])

Submission status: Accepted

Solution code:
MOD=10**9+7

N=int(input())
a=[int(input()) for i in range(N)]
last={}
tmp={}

ans=1
x=a[0]
last[x]=0
tmp[x]=1

for i in range(1,N):
    x=a[i]
    last.setdefault(x,i)
    tmp.setdefault(x,0)
    if last[x]!=i-1: ans+=tmp[x]
    last[x]=i
    tmp[x]=ans%MOD
    ans=ans%MOD
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

dp = [1 for i in range(0,n+1)]
c = list()
c.append(-1)
d = {}
for i in range(1,n+1):
    c.append(int(input()))

for i in range(1,n+1):
    if c[i] in d:
        j = d[c[i]]
        d[c[i]] = i
        if c[i-1] != c[i]:
            dp[i] = dp[i-1]+dp[j]
            continue
    else:
        d[c[i]] = i
    dp[i] = dp[i-1]
print(dp[-1]%(10**9+7))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
C=[int(input()) for i in range(N)]
M=max(C)+2
dp=[0]*(N+1)
co=[0]*M
co[C[0]]=1
for i in range(1,N+1):
    if i<N and C[i-1]==C[i]:
        continue
    dp[i]+=co[C[i-1]]
    if i<N:
        co[C[i]]+=dp[i]
        co[C[i]]%=mod
    #print(dp,co)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
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())

from collections import Counter, defaultdict

def compress(c: list) -> list:
    pre = 0
    ret = []
    for ci in c:
        if ci != pre:
            ret.append(ci)
            
        pre = ci
        
    return ret

def rem_alone(c: list) -> list:
    cnt = Counter(c)
    aln = set()
    for k, v in cnt.items():
        if v == 1:
            aln.add(k)
        
    ret = []
    for ci in c:
        if ci in aln:
            continue
        
        ret.append(ci)
        
    return ret

def find_prev_idx(c: list) -> dict:
    idx = defaultdict(list)
    prev = defaultdict(int)
    for i, ci in enumerate(c):
        prev[i+1] = idx[ci][-1] if len(idx[ci]) > 0 else -1
        idx[ci].append(i+1)

    
    return prev
 
n = ni()
c = [ni() for _ in range(n)]
mod = 10**9+7

c = rem_alone(compress(c))

prev = find_prev_idx(c)

dp = [0]*(len(c)+1)
dp[0] = 1
for i in range(1, len(c)+1):
    dp[i] = dp[i-1] if prev[i] == -1 else dp[i-1] + dp[prev[i]]
    dp[i] %= mod

    
print(dp[len(c)])

Submission status: Accepted

Solution code:
N = int(input())
C = [int(input()) for i in range(N)]
MOD = 10**9+7

dp = [0] * N
dp[0] = 1
bak = {C[0]:0}

for i,c in enumerate(C):
    if i==0: continue
    dp[i] = dp[i-1]
    if c in bak and bak[c] < i-1:
        dp[i] += dp[bak[c]]
        dp[i] %= MOD
    bak[c] = i
print(dp[-1])

Submission status: Accepted

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

MOD = 1000000007  # type: int
MAX_N = 200000

def solve(N, C):
    last = [-1] * MAX_N
    pairs = []
    for i, c in enumerate(C):
        try:
            prev = last[c - 1]
        except:
            if c >= N:
                return
            else:
                raise Exception()
        if prev >= 0 and prev < i - 1:
            pairs.append((prev, i))
        last[c - 1] = i
    pairs.sort()
    count = [0] * N
    count[0] = 1
    idx = 0
    for i in range(N):
        if i > 0:
            count[i] += count[i - 1]
            count[i] %= MOD
        while idx < len(pairs) and pairs[idx][0] == i:
            count[pairs[idx][1]] += count[i]
            count[pairs[idx][1]] %= MOD
            idx += 1
    print(count[N - 1])
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    C = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, C)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
 n = int(input())
 c = [int(input()) for _ in range(n)]
 mod = 10**9 +7
 dp = [1]*n
 dp[0] = 1
 place = [-1]*200001

 for i in range(n):    
    if place[c[i]-1] != -1:
      if place[c[i]-1] == i-1:
        dp[i] = dp[i-1]
      else:
        dp[i] = (dp[i-1]+dp[place[c[i]-1]])%mod
        
    else:
     dp[i] = dp[i-1]
    place[c[i]-1] = i
 #print(dp)
 #print(place)
 return dp[-1]%mod

print(solve())

Submission status: Accepted

Solution code:
import numpy as np

def main():
  mod = 10 ** 9 + 7

  n = int(input())
  nums = [-1]
  for _ in range(n):
      tmp = int(input())
      if nums[-1] != tmp:
          nums.append(tmp)
  #print(nums)

  m = len(nums)

  dp = [1 for _ in range(m)] # i番目の石までは操作を行い、i+1番目以降の石は操作をしない時の場合の数
  colors = [0 for _ in range(max(nums) + 1)] #その時各色が何個、i番目以前にあるのか

  for i in range(1, m):
    dp[i] = (dp[i - 1] + colors[nums[i]]) % mod #i番目の石を利用可能にすることで作れる数列の数は、i - 1番目まででできるものに、i番め以前の数列を利用したもの？
    colors[nums[i]] = dp[i]
    #print(dp, colors)


  print(dp[-1])
  

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
MOD = 10**9+7
N = int(input())
C = [int(input()) for i in range(N)]

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

color = {}
for c in C:
    color[c] = 0
color[C[0]] = 1

for i in range(1,N):
    dp[i] = dp[i-1]
    if C[i-1] != C[i]:
        dp[i] = (dp[i] + color[C[i]])%MOD
    color[C[i]] = dp[i]
print(dp[-1])

Submission status: Accepted

Solution code:
MOD = 10**9+7
N = int(input())
C = [int(input()) for i in range(N)]

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

color = {}
for c in C:
    color[c] = 0
color[C[0]] = 1

for i in range(1,N):
    dp[i] = dp[i-1]
    if C[i-1] != C[i]:
        dp[i] = (dp[i] + color[C[i]])%MOD
    color[C[i]] = dp[i]
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
c = [0] + [int(input()) for _ in range(n)]
dp = [0] * (200001)
num = 1
for i in range(n):
    if c[i]!=c[i+1]:
        num += dp[c[i+1]]
        dp[c[i+1]] = num
print(num%(10**9+7))

Submission status: Accepted

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

N = int(input())
c = []
for _ in range(N):
    c.append(int(input()))

dp = [0] * N
dp[0] = 1
dpc = [0] * (max(c) + 1)
dpc[c[0]] = 1

for i in range(1, N):
    dp[i] = dp[i - 1]
    if c[i] != c[i - 1]:
        dp[i] += dpc[c[i]]
        dpc[c[i]] += dp[i - 1]

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

Submission status: Accepted

Solution code:
N=int(input())
l=[]
l_value=[]
i=0
stack=-1
for i in range(N):
    if i < N:
        l.append(input())
list_simple=[]
for i in l:
    if stack != i:
        list_simple.append(i)
    stack = i
dp_dict=[0]*200001
dp=1
for i in list_simple:
    i=int(i)
    dp = dp_dict[i] +dp
    dp_dict[i] = dp
print(dp%(10**9+7))

Submission status: Accepted

Solution code:
sums = [1]  # pair number sum until index
csums = {}  # pair number sum of each color

N = int(input())
C = []      # color stone list
lastc = -1  # last color of input
for i in range(N):
    c = int(input())
    if(lastc == c):
        continue
    lastc = c
    C.append(c)

#print("C = " + str(C))

for i, c in enumerate(C, 1):
    if(c in csums):
        sums.append(sums[-1] + csums[c])
        csums[c] += sums[i - 1]
    else:
        sums.append(sums[-1])
        csums[c] = sums[i - 1]

#    print("i = {}, c = {}".format(i, c))
#    print("csums = " + str(csums))
#    print("sums = " + str(sums))

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

Submission status: Accepted

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

N = int(readline())
MOD = 10**9 + 7
last = [-1]*(3*10**5)
dp = [0]*(N+1)
dp[0] = 1
for i in range(1, N+1):
    c = int(readline())
    if last[c] != -1 and last[c]+1 < i:
        dp[i] = (dp[last[c]] + dp[i-1]) % MOD
    else:
        dp[i] = dp[i-1]
    last[c] = i
print(dp[N])

Submission status: Accepted

Solution code:
import sys
n=int(input())
c=[int(i) for i in sys.stdin]
#連続した数を除去したlist
d=[]
#前の数を保存する変数
stack=0
for i in c:
  if i!=stack:
    d.append(i)
  stack=i
#0で初期化
x=[0]*200001
sum=1
p=10**9+7
for i in range(0,len(d)):
  x[d[i]]= (x[d[i]]+sum)%p
  sum=x[d[i]]%p
print(sum)

Submission status: Accepted

Solution code:
import sys
n=int(input())
c=[int(i) for i in sys.stdin]
x=[0]*(200001)
c.append(0)
x[c[0]]+= 1
num=1
p=10**9 +7
for i in range(1,n):
  if c[i]-c[i-1]:
    x[c[i]]+= num
    x[c[i]]= x[c[i]]%p
  if c[i]-c[i+1]:
    num=x[c[i]]%p
  else:
    num=0
print(num)

Submission status: Accepted

Solution code:
N=int(input()) 
clist=[-1]
mod=10**9+7

for i in range(N):
  t=int(input())
  if t==clist[-1]:
    continue
  clist.append(t)

del clist[0]
N = len(clist)

# print(clist)
colorlast=[-1]*(3*10**5)
poslp=[-1]*(N+1)

for e,c in enumerate(clist,1):
  if  colorlast[c]  !=  -1:
    poslp[e]=colorlast[c]
    colorlast[c]=e
  else:
    colorlast[c]=e


dp=[0]*(N+100)
dp[0]=1

for e,c in enumerate(clist,1):
  if poslp[e]==-1:
    dp[e]=(dp[e-1])%mod
  else:
    dp[e]=(dp[e-1]+dp[poslp[e]])%mod

# print(dp[:len(clist)+1])
print(dp[len(clist)]%mod)

Submission status: Accepted

Solution code:
n = int(input())
c = [int(input()) for i in range(n)]
num,x = 1,[0]*(200001)
c.append(0)
x[c[0]]+=1
for i in range(1,n):
    if c[i]-c[i-1]: x[c[i]] = (x[c[i]]+num)%(10**9+7)
    if c[i]-c[i+1]: num = x[c[i]]
    else: num = 0
print(num)

Submission status: Accepted

Solution code:
n = int(raw_input())
s = [int(raw_input()) for _ in range(n)]
mod = int(1e9+7)

previous_idx = {}
dp = [1] * n
ans = 1

for i in range(n):
	c = s[i]
	if c in previous_idx and previous_idx[c] != i-1:
		ans += dp[previous_idx[c]]

	previous_idx[c] = i
	dp[i] = ans % mod

print(ans % mod)

Submission status: Accepted

Solution code:
N = int(input())
pre_stone = 0
div = 10**9+7
dp = 1
dp_dict = {}
for _ in range(N):
    c = int(input())
    if pre_stone != c:
        pre_stone = c
        if c not in dp_dict:
            dp_dict[c] = 0
        dp += dp_dict[c]
        dp_dict[c] = dp

print(dp%div)

Submission status: Accepted

Solution code:
#encoding: utf-8

n = int(input())
c = []
for i in range(n):
    c.append(int(input()))

dp = 1
prev = [0] * (max(c) + 1)
x = 0
for i in c:
    if x != i:
        dp += prev[i]
        prev[i] = dp
    x = i

print(dp % (10 ** 9 + 7))