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 collections import defaultdict

M = 10**9 + 7
N = int(input())
C = [0]*N
for i in range(N):
    C[i] = int(input())

P = [0]*N
Q = [0]*N
QS = defaultdict(int)
Q[0] = QS[C[0]] = 1
for i in range(1,N):
    if C[i] == C[i-1]:
        Q[i] = 0
    else:
        Q[i] = (P[i-1] + Q[i-1]) % M

    P[i] = QS[C[i]]
    QS[C[i]] = (QS[C[i]] + Q[i]) % M

print((P[N-1]+Q[N-1]) % M)

Submission status: Accepted

Solution code:
import sys
DBG =  not True
R = 1000000007
MAXN = 200000
n = int(input())
c = []
for i in range(n):
    c.append(int(input()))
tot = 1
s = [0] * (MAXN+1)
for i in range(n):
    if i > 0 and c[i] == c[i-1]:
        continue
    x = s[c[i]]
    tot = (tot + x) % R
    s[c[i]] = tot
    if DBG:
        print("i {} sci {} tot {} newt {}".format(i,x,s[c[i]],tot))
        print(s)
print(tot)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  value = 1
  skips = {}
  prev = -1

  for _ in range(int(input())):
    n = int(input())

    if n == prev:
      continue

    prev = n

    if n in skips:
      value += skips[n]

    skips[n] = value

  print(value % int(1e+9 + 7), flush=True)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())
K = []
for i in range(N):
  K.append(int(input()))
L = [K[0]]
for j in range(1,N):
  if K[j] != L[len(L)-1]:
    L.append(K[j])
dp = [0]*len(L)
dp[0] = 1
used = [-1]*(max(L)+1)
used[L[0]] = 0
for i in range(1,len(L)):
  if used[L[i]] == -1:
    dp[i] = dp[i-1]
  else:
    dp[i] = (dp[i-1]+dp[used[L[i]]])%(10**9+7)
  used[L[i]] = i
print(dp[len(L)-1])

Submission status: Accepted

Solution code:
import sys
N = int(input())
C = [0]
n = N
for i in range(1, n + 1):
    c = int(sys.stdin.readline())
    if c == C[-1]:
        N -= 1
    else:
        C.append(c)
dp = [0] * (N + 2)
dp[0] = 1
dp[1] = 1
cumsum = [0] * (2 * (10 ** 5) + 2)
cumsum[C[1]] = 1
for i in range(2, N+1):
    dp[i] = dp[i - 1] + cumsum[C[i]]
    cumsum[C[i]] += dp[i-1]
    dp[i] %= (10 ** 9 + 7)
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
C = [-1]

for _ in range(N):
    c = int(input())
    if c == C[-1]:
        continue
    else:
        C.append(c)

MOD = 10**9+7
dp = 1
prev = [0]*(max(C)+1)

for c in C[1:]:
    dp = (dp+prev[c]) % MOD
    prev[c] = dp
print(dp)

Submission status: Accepted

Solution code:
n=int(input())

latest_dic = {}
array   = []
answers = []

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

for i,c in enumerate(array):
    if i==0:
        answers.append(1)
        latest_dic[c] = 1
    else:
        cnt = answers[i-1]
        if (c in latest_dic) and (c!=array[i-1]):
            cnt += latest_dic[c]
            answers.append(cnt)
        else:
            answers.append(cnt)
        latest_dic[c]=cnt

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

Submission status: Accepted

Solution code:
def solve(N, Cs):
    dp = [-1 for _ in Cs]
    latest_c = {}
    ans = 1
    d = 10 ** 9 + 7
    for i, c in enumerate(Cs):
        if c not in latest_c:
            latest_c[c] = i
            dp[i] = ans
        else:
            previous_i = latest_c[c]
            if previous_i != i - 1:
                ans += dp[previous_i]
            latest_c[c] = i
            dp[i] = ans
    return ans % d


if __name__ == "__main__":
    N = int(input())
    Cs = [int(input()) for _ in range(N)]
    print(solve(N, Cs))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
pos=[0]*(200005)
ind=0
for i in range(int(input())):
	x=int(input())
	if x!=pos[ind]:
		ind+=1
		pos[ind]=x
ans=[0]*(ind+1)
per=[0]*200005
ans[0]=1
for i in range(1,ind+1):
	per[pos[i]]=(per[pos[i]]+ans[i-1])%1000000007
	ans[i]=per[pos[i]]
print(ans[i])

Submission status: Accepted

Solution code:
from collections import defaultdict
mod = 10**9+7
n = int(input())
c = [0]
d = defaultdict(list)
r = defaultdict(int)

idx = 1
for i in range(n):
    tmp = int(input())
    if c[-1] != tmp:
        if d[tmp]:
            r[idx] = d[tmp][-1]
        d[tmp].append(idx)
        c.append(tmp)
        idx += 1

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

Submission status: Accepted

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

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

last = {}

for i in range(N) :
    if i == 0 :
        last[L[i]] = i
    else :
        if L[i] not in last :
            dp[i] = dp[i-1]
        elif L[i] == L[i-1] :
            dp[i] = dp[i-1]
        else :
            j = last[L[i]]
            dp[i] = dp[i-1] + dp[j]
        
        last[L[i]] = i

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    c = []
    mod = 10 ** 9 + 7
    state = [0 for i in range(n+200000)]
    dp = [0 for i in range(n+1)]
    dp[0] = 1
    for i in range(n):
        c_i = int(input())

        if state[c_i] >= 1 and state[c_i] != i:
            dp[i+1] = (dp[state[c_i]] + dp[i]) % mod
        else:
            dp[i+1] = dp[i] % mod

        state[c_i] = i + 1
    print(dp[-1] % mod)

main()

Submission status: Accepted

Solution code:
n=int(input())
c=list(int(input()) for i in range(n))
dp=[0]*n
rec=[0]*(2*10**5+1)
dp[0]=1
rec[c[0]]=1
for i in range(1,n):
	if c[i]==c[i-1]:
		dp[i]=dp[i-1]
		continue
	dp[i]=(dp[i-1]+rec[c[i]])%(10**9+7)
	rec[c[i]]=dp[i]
print(dp[-1])

Submission status: Accepted

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

# 現時点で最も左の、色C_iの石が存在する負のインデックス（0は存在しないことを表す）
k = [0 for _ in range((2 * 10**5) + 1)]

# 動的計画法により解を求める
dp = [0 for _ in range(N)]
k[C[-1]] = -1
dp[-1] = 1
for i in range(2, N + 1):
    if k[C[-i]] == 0 or k[C[-i]] == -i + 1:
        dp[-i] = dp[-i + 1]
    else:
        dp[-i] = (dp[-i + 1] + dp[k[C[-i]]]) % (10**9 + 7)
    k[C[-i]] = -i
ans = dp[0]

# 出力
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

@mt
def slv(N, C):
    C_ = [-1]
    for c in C:
        if C_[-1] == c:
            continue
        C_.append(c)
    
    C = C_

    mod = 10**9 + 7
    S = defaultdict(lambda: 0)
    ans = 1
    for c in C:
        ans = (ans + S[c]) % mod
        S[c] = ans

    return ans


def main():
    N = read_int()
    C = [read_int() for _ in range(N)]
    print(slv(N, C))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

MOD = 10 ** 9 + 7

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

dp = [0 for _ in range(N + 1)]
dp[0] = 1
# dp[index] = 場合の数
# 1-indexed

d = defaultdict(lambda: -1)
# d[色] = index
# 指定色が直前に出現した位置
# 1-indexed

for i, cc in enumerate(c, 1):
    dp[i] = dp[i - 1]
    # 手前までの塗り方に
    # i番目の石をつなげたパターン
    # dp[i - 1] = 手前までの色の塗り方
    if 1 <= d[cc] < i - 1:
        # 指定色が出現している場合
        # （出現なし -> -1）
        dp[i] += dp[d[cc]]
        # 直前の指定色からi番目の石までの区間を色変更したパターン
        # dp[d[cc]] = 直前の指定色までの色の塗り方
    dp[i] %= MOD
    d[cc] = i
    # print(d)
    # print(dp)
print(dp[N])

Submission status: Accepted

Solution code:
N=int(input())
lst=[0]
mod=10**9+7
for i in range(N):
  a=int(input())
  if lst[-1]==a:
    continue
  else:
    lst.append(a)
length=len(lst)
L=[0]*(2*10**5+1);DP=[0]*(length-1)
DP.insert(0,1)
for i in range(1,length):
  if L[lst[i]]==0:
    DP[i]=DP[i-1]%mod
    L[lst[i]]=i
  else:
    j=L[lst[i]]
    DP[i]=(DP[i-1]+DP[j])%mod
    L[lst[i]]=i
print(DP[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
MOD = 10**9 + 7
N = int(input())
C = [int(input()) for _ in range(N)]

dic = dict()
dp = [None] * N
for i, x in enumerate(C):
    if x in dic:
        dp[i] = dic[x]
    dic[x] = i

dp2 = [0] * N
dp2[0] = 1
for i in range(1, N):
    dp2[i] = dp2[i - 1]
    if dp[i] is not None and i - 1 != dp[i]:
        dp2[i] = (dp2[i] + dp2[dp[i]]) % MOD

print(dp2[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
c2 = [int(input()) for _ in range(N)]
mod = 10**9+7
#圧縮
c = [c2[0]-1]
n = N
for i in range(1,N):
    if c2[i] == c2[i-1]:
        n -= 1
        continue
    c.append(c2[i]-1)

#used[i]:色iが最後に登場したindex
#初期値:-1
used = [-1]*(max(c)+1)
used[c[0]] = 0
#dp[i]:i番目まででの場合の数
dp = [0]*n
dp[0] = 1
for i in range(1,n):
    if used[c[i]] == -1:
        dp[i] = dp[i-1]
    else:
        dp[i] = (dp[i-1]+dp[used[c[i]]])%mod
    used[c[i]] = i

print(dp[-1])

Submission status: Accepted

Solution code:
import sys


def tran(A):
    temp = []
    for i in range(len(A)):
        if i == 0:
            temp += [A[i]]
        elif A[i] != A[i - 1]:
            temp += [A[i]]
    return temp


def find(A):
    # assume consecutive elements
    dp = [1] * len(A) + [1]

    current_dic = {}

    MOD = 10**9 + 7

    for i in range(len(A)):

        if i == 0:
            current_dic[A[i]] = 1
        else:
            temp = dp[i - 1]
            if A[i] in current_dic:
                temp += current_dic[A[i]]
                temp %= MOD
                current_dic[A[i]] += dp[i - 1]
                current_dic[A[i]] %= MOD
            else:
                current_dic[A[i]] = dp[i - 1]

            dp[i] = temp
    # print(dp)
    return dp[-2] % MOD


N = int(input())
A = []
for i in range(N):
    A += [int(input())]



print(find(tran(A)))

Submission status: Accepted

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

DP = [0] * (n + 1)
last = [0] * int(2e5 + 1)
DP[0] = 1

for i in range(n):
    if C[i + 1] == C[i]:
        DP[i + 1] = DP[i] % p
    else:
        DP[i + 1] = (DP[i] + last[C[i + 1]]) % p
    last[C[i + 1]] = DP[i + 1]

print(DP[n])

Submission status: Accepted

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
C = [x for x,y in zip(C[:-1],C[1:]) if x!=y] + [C[-1]]

DP = [1]
dic = {}

for i in range(len(C)):   
    DP.append((DP[-1]+dic.get(C[i],0))%(10**9+7))    
    dic[C[i]] = DP[-1]
print(DP[-1])

Submission status: Accepted

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
C = [x for (x,y) in zip(C[:-1], C[1:]) if x!=y] + [C[-1]]

SUM = 1
DP_dict = {}

for c in C:
  if c in DP_dict.keys():
    SUM += DP_dict[c]
  DP_dict[c] = SUM

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

Submission status: Accepted

Solution code:
N = int(input())
C = []
tmp_b = -1
for _ in range(N):
  tmp_n = int(input())
  if tmp_n != tmp_b:
    C.append(tmp_n)
    tmp_b = tmp_n

SUM = 1
DP_dict = {}

for c in C:
  if c not in DP_dict.keys():
    DP_dict[c] = SUM
  else:
    SUM += DP_dict[c]
    DP_dict[c] = SUM

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

Submission status: Accepted

Solution code:
from collections import defaultdict
 
mod = 10 ** 9 + 7
n = int(input())
C = [int(input()) for i in range(n)]
 
for i in range(n - 1, 0, -1):
    if C[i] == C[i - 1]:
        del C[i]
        #重複部分を圧縮したCを作成
        
D = defaultdict(int)
ans = 1
for c in C:
    ans += D[c]
    D[c] = ans
    #print(D, ans)

print(ans % mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
c2 = [int(input()) for _ in range(N)]
mod = 10**9+7
#圧縮
c = [c2[0]-1]
n = N
for i in range(1,N):
    if c2[i] == c2[i-1]:
        n -= 1
        continue
    c.append(c2[i]-1)

#used[i]:色iが最後に登場したindex
#初期値:-1
used = [-1]*(max(c)+1)
used[c[0]] = 0
#dp[i]:i番目まででの場合の数
dp = [0]*n
dp[0] = 1
for i in range(1,n):
    if used[c[i]] == -1:
        dp[i] = dp[i-1]
    else:
        dp[i] = (dp[i-1]+dp[used[c[i]]])%mod
    used[c[i]] = i

print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
C = []
MOD = 10 ** 9 + 7
pre = -1
for i in range(n):
    a = int(input())
    if a != pre:
        C.append(a)
    pre = a

N = len(C)
dp = [0] * (N + 1)
col = {}
pre = -1
dp[0] = 1
for i in range(1, N + 1):
    if C[i - 1] not in col:
        dp[i] = dp[i - 1]
        col[C[i - 1]] = dp[i]
    else:
        dp[i] = dp[i - 1]
        dp[i] += col[C[i - 1]]
        dp[i] %= MOD
        col[C[i - 1]] += dp[i - 1]

print(dp[N])

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
d = dd(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:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

memory = {}


def solve(N: int, C: "List[int]"):
    # print(dfs(tuple(C), N, 0))

    dp = [0]*N
    last = [-1]*(2*(10**5)+1)
    for i, s in enumerate(C):
        if i == 0:
            dp[i] = 1
        else:
            dp[i] = dp[i-1]
            if last[s] != -1 and last[s] < i-1:
                dp[i] = (dp[i] + dp[last[s]]) % MOD
        last[s] = i
    # print(dp, souwa, pre)
    print(dp[-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:
from collections import deque
mod = 10**9 + 7
N = int(input())
C = [int(input()) for i in range(N)]
dq = deque()
dq.append(C[0])
for c in C:
    if c != dq[-1]:
        dq.append(c)
C = list(dq)
N = len(C)
dp = [0]*(N+1)
dp[0] = 1
acc = [0]*(2*pow(10,5)+1)
for i in range(1,N+1):
    dp[i] = dp[i-1]
    dp[i] += acc[C[i-1]]
    dp[i] %= mod
    acc[C[i-1]] += dp[i-1]
    acc[C[i-1]] %= mod
ans = dp[N]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
stones = []
last = None
n_stone = 0
for i in range(N):
    stone = int(input())
    if stone != last:
        stones.append(stone)
        last = stone

count = defaultdict(int)
seq = 1
for i, c in enumerate(stones):
      prev = count[c]
      count[c] = prev + seq
      seq += prev

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import Counter, defaultdict

INF = float('inf')
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 LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    C = [II() for _ in range(n)]

    dp = [0] * (n + 1)
    dp[0] = 1
    color_index = defaultdict(int)
    for i, c in enumerate(C):
        if not color_index[c]:
            color_index[c] = i + 1
            dp[i + 1] = dp[i]
        else:
            if color_index[c] == i:
                dp[i + 1] = dp[i]
            else:
                dp[i + 1] = dp[i] + dp[color_index[c]]
                dp[i + 1] %= MOD
            color_index[c] = i + 1

    return dp[-1]


print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict

MOD = 10 ** 9 + 7

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

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

d = defaultdict(lambda: -1)

for i, cc in enumerate(c, 1):
    dp[i] = dp[i - 1]
    if 0 <= d[cc] < i - 1:
        dp[i] += dp[d[cc]]
    dp[i] %= MOD
    d[cc] = i
    # print(d)
    # print(dp)
print(dp[N])

Submission status: Accepted

Solution code:
from collections import defaultdict

MOD = 10 ** 9 + 7

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

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

d = defaultdict(lambda: -1)

for i, cc in enumerate(c, 1):
    if c[i - 1] == c[i - 2]:
        dp[i] = dp[i - 1]
    elif d[cc] == -1:
        # 初めて出現した色
        dp[i] = dp[i - 1]
    else:
        dp[i] = dp[i - 1] + dp[d[cc]]
    dp[i] %= MOD
    d[cc] = i
    # print(d)
    # print(dp)
print(dp[N])

Submission status: Accepted

Solution code:
import sys

N = int(input())
C = [int(sys.stdin.readline()) for _ in range(N)]
MOD = 10**9 + 7
A = []
for c in C:
    if A and A[-1] == c:
        continue
    A.append(c)
NA = len(A)
last = [-1] * 200001
B = [-1] * 200001
for i, a in enumerate(A):
    B[i] = last[a]
    last[a] = i

dp = [0] * NA
dp[0] = 1
for i in range(1, NA):
    prev = 0 if B[i] < 0 else dp[B[i]]
    dp[i] = (dp[i - 1] + prev) % MOD
print(dp[-1])

Submission status: Accepted

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] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    s = S()
    d = defaultdict(int)
    for i in s:
        d[i] += 1
    ans = 1
    for i in d.keys():
        ans *= d[i]+1
        ans %= mod
    print(ans-1)
#B
def B():
    n = I()
    c = IR(n)
    v = [[i+1] for i in range(n-1)]
    v.append([])
    d = defaultdict(deque)
    for i in range(n):
        d[c[i]].append(i)
    for i in d.keys():
        x = None
        while d[i]:
            y = d[i].popleft()
            if x != None and y != x+1:
                v[x].append(y)
            x = y
    path = [0]*(n)
    path[0] = 1
    q = [0]
    for x in range(n-1):
        for y in v[x]:
            path[y] += path[x]
            path[y] %= mod
    print(path[-1])
#C
def C():
    sys.setrecursionlimit(100000)
    n,a,b = LI()
    def dfs(l,q,f):
        if len(l) == po2[n]:
            if l[-1] == b:
                print("YES")
                print(*l)
                quit()
        x = l[-1]
        m = -1
        k = -1
        for i in po2[:-1]:
            y = x^i
            if f[y] > m:
                m = f[y]
                k = y
        if m != -1:
            for i in po2[:-1]:
                y = x^i
                if f[y] == m:
                    q.append(y)
            for y in q:
                dfs(l+[y],[],f[:y]+[-1]+f[y+1:])
    po2 = [1]*(n+1)
    for i in range(1,n+1):
        po2[i] = po2[i-1]*2
    ans = [a]
    f = [0]*po2[n]
    for i in range(po2[n]):
        k = b^i
        c = 0
        while k > 0:
            c += k%2
            k//= 2
        f[i] = c
    if not f[a] in [1,3,5,7,9,11,13,15,17,19]:
        print("NO")
        quit()
    f[a] = -1
    l = [a]
    dfs(l,[],f)
    print("NO")
#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Accepted

Solution code:
n = int(input())
cc = [int(input()) for i in range(n)]
c = [cc[0]]
for i in range(1,n):
  if cc[i] != cc[i-1]:
    c.append(cc[i])

n = len(c)
dp = [0 for i in range(n)]
pos_dp = [-1 for i in range(2*10**5+1)]

dp[0] = 1
pos_dp[c[0]] = 0
     
for i in range(1,n):
  if pos_dp[c[i]]!=-1:
    dp[i] = (dp[i-1] + dp[pos_dp[c[i]]])%1000000007
  else:
    dp[i] = dp[i-1] 
  pos_dp[c[i]] = i

print(dp[n-1])

Submission status: Accepted

Solution code:
n,*c=map(int,open(0).readlines())
l=[-1]*2**18
b=[]
for i in range(n):
  b.append(l[c[i]])
  l[c[i]]=i
dp=[1]+[0]*n
for i in range(1,n):
  dp[i]=dp[i-1]
  if c[i]!=c[i-1]and b[i]>-1:
    dp[i]=(dp[i]+dp[b[i]])%(10**9+7)
print(dp[-2])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

N = int(input())
C = [0]
for _ in range(N):
    c = int(sys.stdin.readline())
    if C[-1] != c:
        C.append(c)

ans = 1
dic = defaultdict(lambda: 0)
mod = 10 ** 9 + 7
for c in C:
    a = dic[c]
    dic[c] += ans
    ans = (ans + a) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
N=int(input())
C=[int(input())-1 for i in range(N)]
mod=10**9+7
pre_dp=[0]*(max(C)+1)
dp=[0]*(N+1)
dp[0]=1
dp[1]=1
pre_dp[C[0]]=1
for i in range(1,N):
  if C[i]!=C[i-1]:
    dp[i+1]=(dp[i]+pre_dp[C[i]])%mod
    pre_dp[C[i]]=(pre_dp[C[i]]+dp[i])%mod
  else:
    dp[i+1]=dp[i]
    
print(dp[N])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

N = int(input())
C = [0]
for _ in range(N):
    c = int(sys.stdin.readline())
    if C[-1] == c:
        continue
    else:
        C.append(c)

ans = 1
dic = defaultdict(lambda: 0)
mod = 10 ** 9 + 7
for c in C:
    a = dic[c]
    dic[c] += ans
    ans = (ans + a) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
C = [int(input()) for _ in range(N)]
dic = defaultdict(list)
for i in range(N):
    dic[C[i]].append(i)
es = [[] for _ in range(N)]
for i in range(N - 1):
    es[i].append(i + 1)
for key in dic:
    if len(dic[key]) == 1:
        continue
    i, L, v1, v2 = 1, len(dic[key]) - 1, dic[key][0], dic[key][1]
    while True:
        if v1 + 1 != v2:
            es[v1].append(v2)
        v1 = v2
        if i < L:
            i += 1
            v2 = dic[key][i]
        else:
            break
dp = [0 for _ in range(N)]
dp[0], MOD = 1, 10**9 + 7
for i in range(N - 1):
    for j in es[i]:
        dp[j] = (dp[j] + dp[i]) % MOD
print(dp[N - 1])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

N = int(input())
C = [0]
for _ in range(N):
    c = int(sys.stdin.readline())
    if C[-1] == c:
        continue
    else:
        C.append(c)

ans = 1
dic = defaultdict(lambda: 0)
for c in C:
    a = dic[c]
    dic[c] += ans
    ans += a

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
p = 10 ** 9 + 7
C = [0] * (N + 1)
D = defaultdict(lambda: -1)
DP = [[0, 0] for i in range(N + 1)]
DP[0] = [1, 0]
for i in range(1, N + 1):
  C[i] = int(input())
  DP[i][0] = sum(DP[i - 1]) % p
  if C[i] != C[i - 1]:
    DP[i][1] = sum(DP[D[C[i]]]) if D[C[i]] != -1 else 0
    D[C[i]] = i
print(sum(DP[N]) % p)

Submission status: Accepted

Solution code:
import sys

N = int(input())
C = [0]
for line in sys.stdin:
    c = int(line)
    if C[-1] == c:
        continue
    else:
        C.append(c)

ans = 1
dic = {}
for c in C:
    if c in dic.keys():
        a = dic[c]
        dic[c] += ans
        ans += a
    else:
        dic[c] = ans

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

Submission status: Accepted

Solution code:
import sys

N = int(input())
C = []
pre = 0
for _ in range(N):
    c = int(sys.stdin.readline())
    if pre == c:
        continue
    else:
        C.append(c)
        pre = c

ans = 1
dic = {}
for c in C:
    if c in dic.keys():
        a = dic[c]
        dic[c] += ans
        ans += a
    else:
        dic[c] = ans

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

Submission status: Accepted

Solution code:
mod=7+10**9
n=int(input())
c=['$']+[int(input()) for _ in [0]*n]
data=[1]+[0]*n
s={}

for i in range(1,n+1):
  if c[i] in s.keys():
    if c[i]!=c[i-1]:
      s[c[i]]+=data[i-1]
      s[c[i]]%=mod
  else:
    s[c[i]]=data[i-1]
  data[i]=s[c[i]]%mod
        
print(data[n])

Submission status: Accepted

Solution code:
n = int(input())
l = [0 for i in range(2*(10**5)+1)]
a = [1]
co = 0
for i in range(n):
    k = int(input())
    b = a[-1]
    if l[k] != i and l[k] != 0:
        b += a[l[k]]
    l[k] = i+1
    a.append(b%(10**9+7))
print(a[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
from __future__ import division, print_function

import itertools
import os
import sys
from atexit import register
from cStringIO import StringIO

range = xrange

sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = StringIO(os.read(0, os.fstat(0).st_size)).readline

MOD = 10**9 + 7
MODF = float(MOD)

MAGIC = 6755399441055744.0
SHRT = 65536.0

MODF_INV = 1.0 / MODF
SHRT_INV = 1.0 / SHRT

fround = lambda x: (x + MAGIC) - MAGIC
fmod = lambda a: a - MODF * fround(MODF_INV * a)


def main():
    n = int(input())
    c = [int(input()) for _ in range(n)]

    c = [x[0] for x in itertools.groupby(c)]
    n = len(c)

    res, prev = [1.0] * (n + 1), [0] * (2 * 10**5 + 1)
    for i in range(n):
        res[i + 1] = res[i] if prev[c[i]] == 0 else fmod(res[i] + res[prev[c[i]]])
        prev[c[i]] = i + 1

    print(int(res[-1]) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

N = int(input())
C = []

prev = -1

for _ in range(N):
    tmp = int(input())
    if tmp != prev:
        C.append(tmp)
    prev = tmp

dp = [0]*(len(C)+1)
place = {}
dp[0] = 1

for i in range(len(C)):
    if place.get(C[i]) != None:
        dp[i+1] = dp[i] + dp[place.get(C[i])]
    else:
        dp[i+1] = dp[i]
    place[C[i]] = i+1
    
print(dp[-1]%(10**9+7))

Submission status: Accepted

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

MOD = 1e9 + 7

C2 = []
re = ""
L = {}
LL = [-1] * N
for i in C:
  if i != re:
    if i in L:
      LL[L[i]] = len(C2)
      L[i] = len(C2)
    else:
      L[i] = len(C2)
    C2.append(i)
  re = i


DP = [-1] * (len(C2) + 1)

DP[-1] = 1
for i in range(len(C2) - 1, -1, -1):
  DP[i] = DP[i + 1]
  if LL[i] != -1:
    DP[i] += DP[LL[i]] % MOD
print(int(DP[0] % MOD))

Submission status: Accepted

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

def main():
    N = II()
    C = []
    for _ in range(N):
        c = II()
        if len(C) == 0 or c != C[-1]:
            C.append(c)
    global ans
    ans = 0
    dp = [1] + [0] * N
    from collections import defaultdict
    cnt_clr = defaultdict(int)
    for i, c in enumerate(C):
        ret = dp[i]
        ret += cnt_clr[c]
        cnt_clr[c] = ret
        dp[i + 1] = ret % MOD

    ans = dp[len(C)]

    return ans % MOD

print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect, bisect_left
from collections import defaultdict

def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
N = int(input())
C = [-1]
for i in range(N):
    c = int(input())
    if c != C[-1]:
        C.append(c)
C = C[1:]
N = len(C)
DP = [1]*N

ixs = defaultdict(lambda: [-1])
ixs[C[0]].append(0)

for i, c in enumerate(C[1:], start=1):
    l = ixs[c][bisect_left(ixs[c], i) - 1]
    if l != -1:
        DP[i] = (DP[i-1] + DP[l])%(MOD)
    else:
        DP[i] = DP[i-1]
    ixs[c].append(i)
print(DP[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict

d = defaultdict(int)
D = defaultdict(lambda:1)
N = int(input())

ans = 1
C = int(input())
d[C] += 1
c = C

for i in range(N - 1):
	C = int(input())
	d[C] += 1
	if C == c:
		pass
	else:
		if d[C] >= 2:
			ans = (ans + D[C]) % 1000000007
	D[C] = ans
	c = C

print(ans)

Submission status: Accepted

Solution code:
#B
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
mod=10**9+7
n=int(input())
C=[int(input()) for _ in range(n)]
A=[0]*(2*10**5+1) #A[i]:色iが最後にあった場所(1-indexed)
B=[1]
for i,c in enumerate(C):
    #print(A[c])
    tmp=B[-1]
    if A[c]!=i and A[c]!=0:
        tmp+=B[A[c]]
    A[c]=i+1
    B.append(tmp%mod)
#print(B)
print(B[-1])

Submission status: Accepted

Solution code:
a = int(input())
C = list()
last = [-1] * 2 * 100002
for i in range(a):
    C.append(int(input()))

ans = [1] * a
last[C[0]] = 0
# print(last,ans)
for i in range(1, a):
    ans[i] = ans[i - 1]
    if C[i] == C[i - 1]:
        continue
    if last[C[i]] != -1:
        ans[i] += ans[last[C[i]]]
    last[C[i]] = i

print(ans[a - 1] % 1000000007)

Submission status: Accepted

Solution code:
from collections import defaultdict


def search(colors):
    dp = [1] * len(colors)
    c_dict = defaultdict(list)
    c_sum = defaultdict(int, {colors[0]:1})
    for i in range(1, len(colors)):
        color = colors[i]
        dp[i] = dp[i-1]
        if color != colors[i-1]:
            dp[i] += c_sum[color]
            c_sum[color] = dp[i]
    print(dp[-1] % (10**9 + 7))

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

search(colors)

Submission status: Accepted

Solution code:
N = int(input())
C = [int(input())]
cindex = {C[0]: 0}
mod = 7 + 10 ** 9
counter = 0
for _ in range(N-1):
    c = int(input())
    if c != C[-1]:
        C.append(c)
        counter += 1
        if c not in cindex:
            cindex[c] = counter

DP = [[0, 1] for i in range(len(C))]
for i in range(1, len(C)):
    if cindex[C[i]] == i:
        DP[i][1] = DP[i-1][1]
    else:
        DP[i][0] = DP[cindex[C[i]]][1] 
        DP[i][1] = DP[i][0] + DP[i-1][1]
        DP[i][1] %= mod
        cindex[C[i]] = i
print(DP[-1][1])