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: Wrong Answer

Solution code:

N = int(input())
c = []
time = 0
timememo = []
for i in range(N):
    c.append(input().split)

def search(N, j, c, time, timememo):
    if j >= N - 2:
        return
    string = c[j]
    for k in range(N-j-1):
        memo = []
        if c[k+j+1] == string:
            if k != 0:
                time += 1
            memo.append(j+k+2)
            timememo.append(time)
            
    for m in range(len(memo)):
        search(N, memo[m], c, time, timememo)
    return

for j in range(N):
    search(N, j, c, time, timememo)

s = sum(timememo)

s = s % 1000000007

print(s)

Submission status: Wrong Answer

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

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

print(ans[a-1])

Submission status: Wrong Answer

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

from collections import defaultdict
dl = defaultdict(int)
dr = defaultdict(int)
ans = 1
cc = [c[0]]
for i in range(1, n):
  if c[i-1]==c[i]:
    continue
  cc.append(c[i])

n = len(cc)
a = [[0, 0] for i in range(n)]
for i in range(0, n):
  if i!=0:
    a[i][0] = dl[cc[i]]
    a[n-i-2][1] = a[n-i-1][1] + dr[cc[n-i-1]]
  dl[cc[i]] += 1
  dr[cc[n-i-1]] += 1
a[n-1][1] = 0

ans = 1
for ele in a:
  if ele[0]>0:
    ans = (ans+ele[0]%MOD*(ele[1]%MOD+1))%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
color=[]
for i in range(n):
    color.append(int(input()))
    
ans=1
color_index=[]
color_set=list(set(color))
for j in range(len(color_set)):
    tem=[i for i, x in enumerate(color) if x == color_set[j]]
    tem_2=1
    for k in range(len(tem)-1):
        if len(tem)>1:
            if tem[k]!=tem[k+1]-1:
                tem_2+=1
    if tem_2>1:
        ans+=math.factorial(tem_2)/(math.factorial(tem_2-2)*math.factorial(2))
    tem_2=1


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

Submission status: Wrong Answer

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


def main():
  n = int(input())
  prev = -1
  nums = []
  table = {}

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

    if v != prev:
      nums.append(v)
      prev = v

  for i, n in enumerate(nums):
    if n not in table:
      table[n] = []

    table[n].append(i)

  values = [0] * len(nums)
  value = 1

  for i in range(len(nums)):
    values[i] += value

    for j in table[nums[i]]:
      if i == j:
        continue

      values[j] += value

    value = values[i]

  print(value, flush=True)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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]
        cindex[C[i]] = i
print(DP[-1][1])

Submission status: Wrong Answer

Solution code:

N = int(input())
c = []
time = 0
timememo = []
for i in range(N):
    c.append(input().split)

def search(N, j, c, time, timememo):
    if j >= N - 2:
        return
    string = c[j]
    for k in range(N-j-1):
        memo = []
        if c[k+j+1] == string:
            if k != 0:
                time += 1
            memo.append(j+k+2)
            timememo.append(time)
            
    for m in range(len(memo)):
        search(N, memo[m], c, time, timememo)
    return

for j in range(N):
    search(N, j, c, time, timememo)

sum = 0
for r in range(len(timememo)):
    sum += timememo[r]
sum = sum % 1000000007

print(sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
C = [0] * N
mod = 10 ** 9 + 7
dic = [-1]*(2*(10**5)+1)
prevIdx = [0] * N
for i in range(N):
    C[i] = int(input())
    if i > 0 and C[i] == C[i-1]:
        continue
    prevIdx[i] = dic[C[i]]
    dic[C[i]] = i

dp = [0] * N
dp[0] = 1
acc = [0] * N
acc[0] = 1
for i in range(1,N):
    dp[i] = dp[i-1] % mod
    if C[i] == C[i-1] or prevIdx[i] == -1:
        acc[i] = 1
        continue
    
    dp[i] += acc[prevIdx[i]]
    acc[i] = acc[prevIdx[i]] + dp[i-1]
    acc[i] %= mod
    dp[i] %= mod

print(dp[N-1] % mod)

Submission status: Wrong Answer

Solution code:
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
C = [I() for i in range(N)]

dic = {}

ans = 0
tmp = "None"
for i in C:
  if i == tmp:
    continue
  else:
    tmp = i
    if i not in dic:
      dic[i] = ans
    else:
      ans += dic[i] + 1
      dic[i] = ans

print(ans+1)

Submission status: Wrong Answer

Solution code:
def reversi(N: int, C: list)->int:
    dp = [0] * (N+1)
    dp[0] = 1
    lefts = {}
    for i, c in enumerate(C):
        if c in lefts and lefts[c] != i:
            dp[i+1] = dp[i] + dp[lefts[c]]
        else:
            dp[i+1] = dp[i]
        lefts[c] = i+1
    return dp[N]


if __name__ == "__main__":
    N = int(input())
    C = [int(input()) for _ in range(N)]
    ans = reversi(N, C)
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def search(colors):
    dp = [1] * len(colors)
    c_dict = defaultdict(list)
    c_dict[colors[0]].append(0)
    for i in range(1, len(colors)):
        color = colors[i]
        dp[i] = dp[i-1]
        continue_flag = color == colors[i-1]
        if len(c_dict[color]) > 0 and not continue_flag:
            for index in c_dict[color]:
                dp[i] += dp[index]
        if not continue_flag:
            c_dict[color].append(i)
    print(dp[-1] % (10**9 + 7))

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

search(colors)

Submission status: Wrong Answer

Solution code:
import copy

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

C2 = []
re = ""
L = {}
for i in C:
  if i != re:
    if i in L:
      L[i].insert(0, len(C2))
    else:
      L[i] = []
    C2.append(i)
  re = i

LL = [-1] * len(C2)
for i in range(len(C2)):
  if L[C2[i]] != []:
    LL[i] = copy.deepcopy(L[C2[i]])
    L[C2[i]].pop()

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:
    for j in LL[i]:
      DP[i] += DP[j + 1]

print(DP[0])

Submission status: Wrong Answer

Solution code:
r=range(int(input()))
A=[int(input()) for i in r]
S=[0 for i in r]
E=[0 for i in r]
C=[1 for i in r]
s=set()
for i in range(1,len(A)+1):
  a=A[-i]
  if a in s and a !=an:
    S[-i]=1
  s |= {a}
  an=a
s=set()

for i in r:
  a=A[i]
  if a in s and a !=an:
    E[i]=1
  s |= {a}
  an=a
er=0
c=1
for i in r:
  s=S[i]
  e=E[i]
  if e:
    c += 1
  if s and c !=1:
    c *= 2 
    c -= 1
    
print(c)

Submission status: Wrong Answer

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

from collections import defaultdict
dl = defaultdict(int)
dr = defaultdict(int)
ans = 1
cc = [c[0]]
for i in range(1, n):
  if c[i-1]==c[i]:
    continue
  cc.append(c[i])

n = len(cc)
a = [[0, 0] for i in range(n)]
for i in range(0, n):
  if i!=0:
    a[i][0] = dl[cc[i]]
    a[n-i-2][1] = a[n-i-1][1] + dr[cc[n-i-1]]
  dl[cc[i]] += 1
  dr[cc[n-i-1]] += 1
a[n-1][1] = 0

ans = 1
for ele in a:
  if ele[0]>0:
    ans += ele[0]*(ele[1]+1)%MOD
print(ans)

Submission status: Wrong Answer

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

D = {}


ans = 1

for i in range(N) :
    if str(L[i]) not in D :
        D[str(L[i])] = 0
    else :
        if L[i] == L[i-1] :
            continue
        else :
            D[str(L[i])] += 1
            ans += D[str(L[i])]
            
            
#print(D)
#print(ans)

ignore = []
for d in D :
    if D[d] == 0 :
        ignore.append(d)


for i in range(N) :
    if D[str(L[i])] >= 1 :
        D[str(L[i])] -= 1
    else :
        if str(L[i]) in ignore :
            continue
        ans += sum(list(D.values()))
        #print(D)
        ignore.append(str(L[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
C = []
mod = 10**9+7
for i in range(N):
	C.append(int(input()))
D = [C[0]]
for i in range(1,N):
	if C[i] != C[i-1]:
		D.append(C[i])
num = [0] * (max(D)+1)
for i in range(len(D)):
	num[D[i]] += 1
ans = 0
# print(num)
for i in range(1,len(num)):
	if num[i] >= 2:
		ans += 2**(num[i]-1)
if ans == 0:
	print(1)
else:
	print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
mod = 10**9+7
N = int(input())
S = ''
s = ''
for i in range(N):
    c = input()
    if s != c:
        S = S+c
    s = c

d = defaultdict(lambda:[])
dd = defaultdict(lambda:{})
dcum = defaultdict(lambda:[0])
for i in range(len(S)):
    d[S[i]].append(i)
    dd[S[i]][i] = len(d[S[i]])-1
    dcum[S[i]].append(0)
n = len(S)
dp = [0]*(n+1)
dp[-1]=1

for i in range(n-1,-1,-1):
    l = d[S[i]]
    j = dd[S[i]][i]+1
    dp[i] += dp[i+1]
    dp[i] += dcum[S[i]][j]
    dp[i] %= mod
    dcum[S[i]][j-1] += dp[i+1]+dcum[S[i]][j]
print(dp[0])

Submission status: Wrong Answer

Solution code:
def f(n):
    return n * (n-1) // 2

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

C.append(-1)
lst = []
for i in range(N):
    if C[i] == C[i+1]:
        pass
    else:
        lst.append(C[i])

lst_uniq = list(set(lst))
cnt = []
for tmp in lst_uniq:
    cnt.append(lst.count(tmp))

for i in range(len(cnt)):
    cnt[i] = f(cnt[i])

ans = (sum(cnt) + 1) % (10**9 + 7)
print(ans)

Submission status: Wrong Answer

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

MOD = 1000000007  # type: int

memory = {}


def dfs(stones, N, depth):
    if N <= 2:
        # print(" "*depth, stones, "leaf")
        return 1
    # print(" "*depth, stones)
    if stones in memory:
        return memory[stones]

    # ans1 はじめの石使わない
    # print(" "*depth, "ans1")
    ans1 = dfs(stones[1:], N-1, depth+1)

    # ans2 はじめの石を使う
    try:
        ind = stones[2:].index(stones[0])
        # print(" "*depth, "ans2", c)
        # print(" "*depth, ind, stones, stones[ind:])
        ans2 = dfs(stones[2+ind:], N-ind-2, depth+1)
    except:
        ans2 = 0

    ans = (ans1 + ans2) % MOD
    memory[stones] = ans
    return ans


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

    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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from math import *
def C(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))
from copy import *
n = int(input())
A = [int(input()) for i in range(n)]
a = set(A)
B = []
ans = 1
#print("--")
for i in a:
	tmp = [_ for _, x in enumerate(A) if x == i]
	B.append(tmp)
	#print(tmp)
	N = len(tmp)
	for j in range(len(tmp)-1):
		#print(tmp[j+1],tmp[j])
		if tmp[j+1] - tmp[j] == 1:
				N -= 1
	if N >= 2:
		cons = C(N,2)
		ans += cons
for i in B:
	for j in B:
		if i[-1] < j[0]:
			ans += 1
anss = ans %  ( 10**9 + 7 ) 
print(anss)

Submission status: Wrong Answer

Solution code:
N = int(input())
C = []
for i in range(N):
	C.append(int(input()))
D = [C[0]]
for i in range(1,N):
	if C[i] != C[i-1]:
		D.append(C[i])
num = [0] * (max(D)+1)
for i in range(len(D)):
	num[D[i]] += 1
ans = 0
# print(num)
for i in range(1,len(num)):
	if num[i] >= 2:
		ans += 2**(num[i]-1)
if ans == 0:
	print(ans)
else:
	print(ans-1)

Submission status: Wrong Answer

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


def main():
  n = int(input())
  nums = list(map(int, [input() for _ in range(n)]))
  table = {}

  for i, n in enumerate(nums):
    if i != 0 and n == nums[i - 1]:
      continue

    if n not in table:
      table[n] = []

    table[n].append(i)

  values = [0] * len(nums)
  value = 1

  for i in range(len(nums)):
    values[i] += value

    for j in table[nums[i]]:
      if i == j:
        continue

      values[j] += value

    value = values[i]

  print(value, flush=True)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
c = []
for i in range(2 * 10 ** 5):
    c.append([])
count = [1]
for i in range(n):
    color = int(input())
    if len(c[color - 1]) == 0 or c[color - 1][-1] != i - 1:
        c[color - 1].append(i)
    num = 0
    for j in range(len(c[color - 1])):
        num += count[c[color - 1][j]]
        num %= 10 ** 9 + 7
    count.append(num)
print(count[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
c = []
for i in range(2 * 10 ** 5):
    c.append([])
count = [1]
for i in range(n):
    color = int(input())
    if len(c[color - 1]) == 0 or c[color - 1][-1] != i - 1:
        c[color - 1].append(i)
    num = 0
    for j in range(len(c[color - 1])):
        num += count[c[color - 1][j]]
    count.append(num)
print(count[-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect
mod = 10**9+7
N = int(input())
S = ''
s = ''
for i in range(N):
    c = input()
    if s != c:
        S = S+c
    s = c

d = defaultdict(lambda:[])
dd = defaultdict(lambda:{})
dcum = defaultdict(lambda:[0])
for i in range(len(S)):
    d[S[i]].append(i)
    dd[S[i]][i] = len(d[S[i]])-1
    dcum[S[i]].append(0)
n = len(S)
dp = [0]*(n+1)
dp[-1]=1

for i in range(n-1,-1,-1):
    l = d[S[i]]
    j = dd[S[i]][i]+1
    dp[i] += dp[i+1]
    dp[i] += dcum[S[i]][j]
    dp[i] %= mod
    dcum[S[i]][j-1] += dp[i+1]+dcum[S[i]][j]
print(dp[0])

Submission status: Wrong Answer

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

MOD = 1000000007  # type: int

memory = {}


def dfs(stones, N, depth):
    if N <= 2:
        # print(" "*depth, stones, "leaf")
        return 1
    # print(" "*depth, stones)
    if stones in memory:
        return memory[stones]

    # ans1 はじめの石使わない
    # print(" "*depth, "ans1")
    ans1 = dfs(stones[1:], N-1, depth+1)

    # ans2 はじめの石を使う
    c = stones[2:].count(stones[0])
    if c == 0:
        ans2 = 0
    else:
        ind = stones[2:].index(stones[0])
        # print(" "*depth, "ans2", c)
        # print(" "*depth, ind, stones, stones[ind:])
        ans2 = dfs(stones[2+ind:], N-ind-2, depth+1)

    ans = (ans1 + ans2) % MOD
    memory[stones] = ans
    return ans


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

    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: Wrong Answer

Solution code:
import copy
N = int(input())
C = ""
for i in range(N):
    C += input()

work = [C]

result = []

def check(stone):

    pair = []

    for i in range(N-2):  # 1つ目の石
        # 連続する石はスキップ

        if stone[i] == stone[i+1]:
            continue
        
        for j in range(i+2,N):  # 2つ目の石
            if stone[j] != stone[i]:
                continue
            
            pair.append([i,j])
    
    return pair

flag = True

while flag:
    next = []
    flag = False
    for i in work:
        stone = list(i)
        pairs = check(stone)
        if pairs:
            for pair in pairs:
                stone2 = copy.copy(stone)
                color = stone[pair[0]]
                for i in range (pair[0]+1,pair[1]):
                    stone2[i] = color
                str_stone = "".join(stone2)

                if str_stone not in result and str_stone not in work:
                    flag = True
                    next.append(str_stone)
    
    result += work
    work = next

print(len(result))

Submission status: Wrong Answer

Solution code:
def reversi(N: int, C: list)->int:
    dp = [1] * (N+1)
    lefts = {}
    for i, c in enumerate(C):
        plus = 0
        if c in lefts:
            l = lefts[c]
            if l != i:
                plus = dp[l]

        dp[i+1] = dp[i] + plus
        lefts[c] = i+1
    return dp[N]


if __name__ == "__main__":
    N = int(input())
    C = [int(input()) for _ in range(N)]
    ans = reversi(N, C)
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect
mod = 10**9+7
N = int(input())
S = ''
s = ''
for i in range(N):
    c = input()
    if s != c:
        S = S+c
    s = c

d = defaultdict(lambda:[])
dcum = defaultdict(lambda:[0])
for i in range(len(S)):
    d[S[i]].append(i)
    dcum[S[i]].append(0)
n = len(S)
dp = [0]*(n+1)
dp[-1]=1

for i in range(n-1,-1,-1):
    l = d[S[i]]
    j = bisect.bisect(l,i)
    dp[i] += dp[i+1]
    dp[i] += dcum[S[i]][j]
    dp[i] %= mod
    dcum[S[i]][j-1] += dp[i+1]+dcum[S[i]][j]
print(dp[0])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect
mod = 10**9+7
N = int(input())
S = ''
s = ''
for i in range(N):
    c = input()
    if s != c:
        S = S+c
    s = c

d = defaultdict(lambda:[])
dcum = defaultdict(lambda:[0])
for i in range(len(S)):
    d[S[i]].append(i)
    dcum[S[i]].append(0)
n = len(S)
dp = [0]*(n+1)
dp[-1]=1

for i in range(n-1,-1,-1):
    l = d[S[i]]
    j = bisect.bisect(l,i)
    dp[i] += dp[i+1]
    dp[i] += dcum[S[i]][j]
    dcum[S[i]][j-1] = dp[i+1]+dcum[S[i]][j]
print(dp[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
C = [0] * N
mod = 10 ** 9 + 7
dic = {}
for i in range(N):
    C[i] = int(input())
    if not C[i] in dic:
        dic[C[i]] = [ i ]
    else:
        dic[C[i]].append(i)

dp = [0] * N
dp[0] = 1
for i in range(1,N):
    dp[i] = dp[i-1]
    if C[i] == C[i-1]:
        continue
    for prev in dic[C[i]]:
        if prev < i:
            if prev > 0:
                dp[i] += dp[prev-1]
            else:
                dp[i] += 1
        dp[i] %= mod

print(dp[N-1] % mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def find_change(colors):
    c_dict = defaultdict(list)
    for i, c in enumerate(colors):
        c_dict[c].append(i)

    for key, point_list in c_dict.items():
        for i in reversed(range(1, len(point_list))):
            if point_list[i] == point_list[i-1] + 1:
                del point_list[i]
        c_dict[key] = point_list
    changes = []
    for point_list in c_dict.values():
        for i in range(len(point_list) - 1):
            for point in point_list[i+1:]:
                changes.append((point_list[i], point))
    return changes

def search(colors):
    memo = {}
    def change_colors(colors):
        t_colors = tuple(colors)
        if t_colors in memo:
            return memo[t_colors]

        changes = find_change(colors)
        ans = len(changes) + 1
        for change in changes:
            new_colors = colors[:change[0]] + colors[change[1]:]
            ans += change_colors(new_colors) - 1
        memo[tuple(colors)] = ans
        return ans

    ans = change_colors(colors)
    print(ans % (10**9 + 7))

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

search(colors)

Submission status: Wrong Answer

Solution code:
n = int(input())
z = []
pre = 0
for _ in range(n):
    i = int(input())
    if i != pre:
        z.append(i)
    pre = i
n = len(z)
dp = [1] * (n+1)
dpp = [0] * 2 * 10 ** 5
for i in range(n):
    dp[i+1] = dp[i] + dpp[z[i]-1]
    dpp[z[i]-1] += dp[i+1]
    dp[i+1] %= 10 ** 9 + 7
print(dp[n])

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
A = [int(input()) for i in range(n)]
ans = 1
for i in range(n):
    tmp = 0
    for j in range(1,n):
        if A[j] == A[i]:
            tmp += 1
    ans += tmp
anss = ans %  ( 10**9 + 7 ) 
print(anss)

Submission status: Wrong Answer

Solution code:
N=int(input())
T=[int(input())for _ in range(N)]
S=set(T)
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
ans=0
for s in S:
    tmp=my_index_multi(T,s)
    print(tmp)
    if not tmp or len(tmp)==1:
        continue
    else:
        for i in range(len(tmp)-1):
            if tmp[i+1]-tmp[i]>1:
                ans+=(i+1)
print((ans+1)%(10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())
C = [0] * N
mod = 10 ** 9 + 7
dic = {}
for i in range(N):
    C[i] = int(input())
    if not C[i] in dic:
        dic[C[i]] = [ i ]
    else:
        dic[C[i]].append(i)

dp = [0] * N
dp[0] = 1
for i in range(1,N):
    dp[i] = dp[i-1]
    if C[i] == C[i-1]:
        continue

    for prev in dic[C[i]]:
        if prev < i:
            if prev > 0:
                dp[i] += dp[prev-1]
            else:
                dp[i] += 1

print(dp[N-1])

Submission status: Wrong Answer

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

dp=[0 for _ in range(n)]
res=[[] for _ in range(max(x)+1)]
res[x[0]].append(0)
dp2=[0 for _ in range(n)]
for i in range(1,len(x)):
    if len(res[x[i]])>0:
        if res[x[i]][-1]==0:#左端スタートで１つ目の場合
            dp[i]=dp[i-1]+1
        else:
            dp[i]=dp[i-1]+len(res[x[i]])+dp2[res[x[i]][-1]-1]
    else:
        dp[i]=dp[i-1]
    res[x[i]].append(i)
    dp2[i]=dp2[i-1]+dp[i]
#print(dp)
#print(dp2)
print((dp[len(x)-1]+1)%(10**9+7))
#print(res)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000)

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

ansls = []
cnt = 0

for n in range(0,N):
    C.append(int(input()))


def f(x,y,b):
    #if b in ansls:
        #None
    if True:
        global cnt
        ban = b[:]
    #print("call:",x,y,ban)
        ava = []
        num = ban[x]
        for i in range(x,y):
            ban[i] = num
    
        for i in range(0,len(ban)):
            now = ban[i]
            for j in range(1,len(ban) - i):
                if ban[i] == ban[i+j]:
                    if ban[i+j] != ban[i+j-1]:
                        ava.append([i,i+j])
    #print(ava)
        if len(ava) != 0:
            if not ban in ansls:
                ansls.append(ban)
                print(ansls)
                for i,j in ava:
                    f(i,j,ban)
                    #cnt += 1
                    
        else:
            if not ban in ansls:
                #cnt+=1
                ansls.append(ban)
        
        

f(0,0,C)
print(int(len(ansls)%((10**9)+7)))

Submission status: Wrong Answer

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

MOD = 1000000007  # type: int

memory = {}


def dfs(stones, depth):
    if len(stones) <= 2:
        # print(" "*depth, stones, "leaf")
        return 1
    # print(" "*depth, stones)
    if stones in memory:
        return memory[stones]

    # ans1 はじめの石使わない
    # print(" "*depth, "ans1")
    ans1 = dfs(stones[1:], depth+1)

    # ans2 はじめの石を使う
    c = stones[2:].count(stones[0])
    if c == 0:
        ans2 = 0
    else:
        ind = stones[2:].index(stones[0])
        # print(" "*depth, "ans2", c)
        # print(" "*depth, ind, stones, stones[ind:])
        ans2 = dfs(stones[2+ind:], depth+1)

    ans = (ans1 + ans2) % MOD
    memory[stones] = ans
    return ans


def solve(N: int, C: "List[int]"):
    print(dfs(tuple(C), 0))
    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: Wrong Answer

Solution code:
n = int(input())
c = [int(input()) for _ in range(n)]

dp = [-1] * n
dp[0] = 1
last_dic = {}
for i in range(n):
    if c[i] in last_dic.keys() and i - last_dic[c[i]] >= 2:
        dp[i] = dp[i-1] + (dp[last_dic[c[i]]])
    elif i:
        dp[i] = dp[i-1]
    last_dic[c[i]] = i
print(dp[-1])

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

if N >= 6:
    print(5)
else:
    print(3)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
import bisect
mod = 10**9+7
N = int(input())
S = ''
s = ''
for i in range(N):
    c = input()
    if s != c:
        S = S+c
    s = c

d = defaultdict(lambda:[])
for i in range(len(S)):
    d[S[i]].append(i)
n = len(S)
dp = [0]*(n+1)
dp[-1]=1

for i in range(n-1,-1,-1):
    l = d[S[i]]
    j = bisect.bisect(l,i)
    dp[i] += dp[i+1]
    for k in range(j,len(l)):
        dp[i] += dp[l[j]+1]
        dp[i] %= mod
print(dp[0])

Submission status: Wrong Answer

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

dp=[0 for _ in range(n)]
res=[[] for _ in range(max(x)+1)]
res[x[0]].append(0)
for i in range(1,len(x)):
    if len(res[x[i]])>0:
        if res[x[i]][-1]==0:#左端スタートで１つ目の場合
            dp[i]=dp[i-1]+1
        else:
            dp[i]=dp[i-1]+len(res[x[i]])
            for t in res[x[i]]:
                if t>0:
                    dp[i]+=dp[t-1]
    else:
        dp[i]=dp[i-1]
    res[x[i]].append(i)
#print(dp)
print(dp[len(x)-1]+1)
#print(res)

Submission status: Wrong Answer

Solution code:
#b
import math
def cc(n, r):
    return math.factorial(n) / math.factorial(n - r) / math.factorial(r)
n = int(input())
c = [int(input()) for _ in range(n)]
d = dict()
i = 1
while i < n:
    if c[i] == c[i-1]:
        del c[i]
        n -= 1
    else:
        i += 1
for i in c:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
cnt = 0
for i in d:
    if d[i] >= 2:
        cnt += cc(d[i],2)
print(cnt)

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
C = ""
for i in range(N):
    C += input()

work = [C]

result = []

def check(stone):

    pair = []

    for i in range(N-2):  # 1つ目の石
        # 連続する石はスキップ

        if stone[i] == stone[i+1]:
            continue
        
        for j in range(i+2,N):  # 2つ目の石
            if stone[j] != stone[i]:
                continue
            
            pair.append([i,j])
    
    return pair

flag = True

while flag:
    flag = False
    for i in work:
        stone = list(i)
        pairs = check(stone)
        if pairs:
            for pair in pairs:
                stone2 = copy.copy(stone)
                color = stone[pair[0]]
                for i in range (pair[0]+1,pair[1]):
                    stone2[i] = color
                str_stone = "".join(stone2)

                if str_stone not in result and str_stone not in work:
                    flag = True
                    work.append(str_stone)
                    print(result,work)
    
    result += work
    work = []

print(len(result))

Submission status: Wrong Answer

Solution code:
def solve(N, Cs):
    counts = [-1 for _ in Cs] + [1]
    latest_c = {}
    tans = 1
    for i, c in enumerate(Cs):
        if c not in latest_c:
            latest_c[c] = i
            counts[i] = tans
        else:
            previous_i = latest_c[c]
            if previous_i != i - 1:
                tans += counts[previous_i - 1]
            latest_c[c] = i
            counts[i] = tans
    return tans


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

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
C = [0]
c = [int(sys.stdin.readline()) for i in range(N)]

C = C+c
ans = 1
dp = [0] * (N + 100)
color = [[]for i in range((2*(10**5)+100))]
dp[0] = 1

dp[1] = 1
color[C[1]].append(1)
for i in range(2, N+1):
    dp[i] = dp[i - 1]

    # dp[i]+=~~
    for col in reversed(color[C[i]]):
        #print(i, col-1)
        if i - col == 1:
            break
        else:
            dp[i] += dp[col-1]
    # forの最後でいい
    color[C[i]].append(i)
    #dp[i] %= (10 ** 9 + 7)

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


# pypyで

Submission status: Wrong Answer

Solution code:
from math import *
def C(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

n = int(input())
A = [int(input()) for i in range(n)]
a = set(A)
B = []
ans = 1
for i in a:
	tmp = [_ for _, x in enumerate(A) if x == i]
	B.append(tmp)
	if len(tmp) >= 2:
		Cons =  C(len(tmp),2)
		for j in range(len(tmp)-1):
			if tmp[j+1]-tmp[j] == 1:
				Cons -= 1*(j+1)
		ans += Cons
for i in B:
	for j in B:
		if i[-1] < j[0]:
			ans += 1

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