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: Time Limit Exceeded

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 j <= i:
        continue

      values[j] += value

    value = values[i]

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


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

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].append(len(C2))
    else:
      L[i] = deque([])
    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]])
    if len(L[C2[i]]) > 0:
      L[C2[i]].popleft()

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: Time Limit Exceeded

Solution code:
N = int(input())
C = []
p = 10**9 + 7
if N <= 2:
    print(1)
else:
    prevprev = int(input())
    prev = int(input())
    C = [prevprev, prev]
    part = []
    if prevprev == prev:
        dp = [[1, [0]], [1, [0, 1]]]
    else:
        dp = [[1, [0]], [1, [1]]]
    for i in range(2, N):
        current = int(input())
        C.append(current)
        part.append(prevprev)
        dp.append([dp[i-1][0], [i]])
        if current == prev:
            dp[i][1] = dp[i-1][1]
            dp[i][1] += [i]
        elif current in part:
            idx = part.index(current)
            dp[i][1] = dp[idx][1]
            l = len(dp[i][1])
            for j in dp[i][1]:
                dp[i][0] += dp[j][0]
            if l > 1:
                dp[i][0] -= l-1
            dp[i][0] = dp[i][0]%p
            dp[i][1] += [i]
        prev, prevprev = current, prev
    print(dp[N-1][0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
c = []
s = {}
pair = []
for i in range(n):
  ci = int(input())
  if ci in s:
    for j in range(len(c))[::-1]:
      if ci == c[j]:
        if j == len(c) - 1:
          break
        pair.append([j, len(c)])
  c.append(ci)
  s = set(c)
ans = 1
l = len(pair)
for i in range(l):
  end = pair[i][1]
  count = 1
  for j in range(i+1, l):
    if pair[j][0] > end:
      count +=1
      end = pair[j][1]
  ans += count
print(ans)

Submission status: Time Limit Exceeded

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] = (values[j] + value) % int(1e+9 + 7)

    value = values[i] % int(1e+9 + 7)

  print(value, flush=True)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
c = []
for i in range(n):
    c.append(int(input()))
# 全ペアを左から深さ優先探索する
ans = 1
# index
stack = [0]
while len(stack) > 0:
    if c[stack[-1]] in c[stack[-1]+1:]:
        flag=False
        take=False
        for i in range(1,n-stack[-1]):
            if c[stack[-1]] != c[stack[-1]+i]:
                flag = True
            if flag and c[stack[-1]] == c[stack[-1]+i]:
                next_i = stack[-1]+i
                ans+=1
                stack.append(next_i)
                take=True
                break
        if not flag & take:
            stack[-1]+=1
    else:
        stack[-1]+=1
    if stack[-1] >= n-1:
        stack.pop(-1)
        if len(stack) > 0:
            stack[-1]+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
d = {}
l = [0]
bef = -1
for i in range(n):
  c = int(input())
  if c != bef:
    if c in d.keys():
      for j,k in enumerate(d[c]):
        l[j] += k
      l.append(1)
    d[c] = copy.deepcopy(l)
  bef = c
print(sum(l)+1)

Submission status: Time Limit Exceeded

Solution code:
import sys

def p2s(p):
  return ' '.join(p)
def s2p(s):
  return s.split(' ')
def compress(p):
  new_p = [p[0]]
  for i in range(1,len(p)):
    if new_p[-1] != p[i]:
      new_p.append(p[i])
  return new_p

_ = input()
_p = [c.strip() for c in sys.stdin]
# 連続する同じ色の石の塊は一つの石とみなせる
pattern = compress(_p)
allpattern = {p2s(pattern),}

def onehop(p):
  N = len(p)
  result = set()
  # 始点
  for i in range(N-1):
    if p[i] == p[i+1]: continue # 同じ色が連続してるときは一番右端をとる
    # 終点
    for j in range(N-1, i+1, -1):
      if p[j] == p[j-1]: continue # 同じ色が連続してる時は一番左端をとる
      if p[i] == p[j]:
        # 間の石をひっくり返す
        new_p = [p[i] if i < k < j else p[k] for k in range(N)]
        result.add(p2s(new_p))
  return result


nows = {p2s(pattern),}
while True:
  nexts = set()
  for s in nows:
    if len(s) > 2:
      nexts |= onehop(s2p(s))
  allpattern |= nows
  if len(nexts) == 0:
    break
  nows = nexts

print(len(allpattern))

Submission status: Time Limit Exceeded

Solution code:
mod=7+10**9
n=int(input())
c=[int(input()) for _ in [0]*n]
def dp(l):
    if not l:
        return 1
    if len(l)==1:
        return 1
    ans=0
    i=0
    while i<len(l):
        if l[i]==l[0]:
            j=i
            while j<len(l) and l[j]==l[0]:
                j+=1
            ans+=dp(l[j:])
            ans%=mod
            i=j
        i+=1
    return ans%mod
print(dp(c))

Submission status: Time Limit Exceeded

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

ans = 1
f = [1] * (N + 1)
for i, c in enumerate(C):
    for j in range(i - 1):
        if C[j] == c:
            ans += f[j]
    f[i + 1] = ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
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 in cindex:
            cindex[c].append(counter)
        else:
            cindex[c] = [counter]

def variation(i, memo = {}):
    if i == len(C)-1: return 1
    try:
        return memo[i]
    except KeyError:
        total = 0
        L = cindex[C[i]]
        for l in L:
            if l > i:
                total += variation(l, memo) #lまで塗る
                total %= mod
                break
        total += variation(i + 1, memo)
        total %= mod
        memo[i] = total
        return total
 
memo = {}
print(variation(0, memo))

Submission status: Time Limit Exceeded

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

dp = [0] * N
dp[0] = 1
for i in range(1,N):
    dp[i] = dp[i-1] % mod
    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: Time Limit Exceeded

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


def main():
  n = int(input())
  nums = list(map(int, [input() for _ in range(n)]))
  values = [0] * len(nums)
  value = 1

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

    for j in range(i + 1, len(nums)):
      if nums[i] != nums[j] or nums[j - 1] == nums[j]:
        continue

      values[j] += value

    value = values[i]

  print(value, flush=True)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

ans = 1
pre = 0
for i, c in enumerate(C):
    if pre == c:
        f[i] = ans
        continue
    else:
        pre = c

    flag = True
    for j in range(i - 1):
        if C[j] == c:
            if flag:
                if j == 0:
                    ans += 1
                else:
                    ans += f[j - 1]
                flag = False
            else:
                continue
        else:
            flag = True
    f[i] = ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
C = [0]
#c = [int(sys.stdin.readline()) for i in range(N)]
n = N
for i in range(1, n + 1):
    c = int(sys.stdin.readline())
    #print(c, i, C)
    if c == C[-1]:
        N -= 1
    else:
        C.append(c)

#C = C+c
dp = [0] * (N + 2)
color = [[]for i in range((2*(10**5)+2))]
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]+=~~
    dp[i] = dp[i - 1] + sum([dp[col - 1] for col in color[C[i]]])
    """
    for col in color[C[i]]:
        #print(i, col-1)
        dp[i] += dp[col-1]
    """
    # forの最後でいい
    color[C[i]].append(i)
    dp[i] %= (10 ** 9 + 7)

# print(dp)
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
from copy import copy

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

def is_fin(C):
    hist = set([C[0]])
    active = C[0]
    for i in C:
        if i != active:
            if i in hist:
                return False
            hist.add(i)
            active = i
    return True

ret = set()
def dfs(C, depth):
    if depth >=5 :
        return
    ret.add(str(C))
    if is_fin(C):
        return

    for i in range(len(C)):
        for j in range(i + 1, len(C)):
            if C[i] == C[j] and len(set(C[i:j])) >= 2:
                _C = copy(C)
                _C[i:j] = [C[i]] * (j - i)
                dfs(_C, depth+1)

dfs(C, 0)
print(len(ret))

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
C = [0]
#c = [int(sys.stdin.readline()) for i in range(N)]
n = N
for i in range(1, n + 1):
    c = int(sys.stdin.readline())
    #print(c, i, C)
    if c == C[-1]:
        N -= 1
        continue
    else:
        C.append(c)

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


# pypyで

Submission status: Time Limit Exceeded

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
    else:
        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:

                for i,j in ava:
                    f(i,j,ban)
                    #cnt += 1
                ansls.append(ban)
                    
        else:
            if not ban in ansls:
                #cnt+=1
                ansls.append(ban)
        
        

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

Submission status: Time Limit Exceeded

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)
place = [[] for _ in range(2 * 10 ** 5)]
for i in range(n):
    dp[i+1] = dp[i]
    for p in place[z[i] - 1]:
        dp[i+1] += dp[p]
    place[z[i] - 1].append(i)
    dp[i+1] %= 10 ** 9 + 7
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
C = []
p = 10**9 + 7
if N <= 2:
    print(1)
else:
    C.append(int(input()))
    C.append(int(input()))
    dp = [1, 1]
    part = []
    for i in range(2, N):
        C.append(int(input()))
        part.append(C[i-2])
        if C[i] == C[i-1]:
            dp.append(dp[i-1])
        elif C[i] not in part:
            dp.append(dp[i - 1])
        else:
            m = C[i]
            part = C[0:i-1]
            idx = [j for j, x in enumerate(part) if x == m]
            l = len(idx)
            d = dp[i-1]
            for j in idx:
                d += dp[j]
            if l > 1:
                d -= l-1
            dp.append(d)
    print(dp[N-1])

Submission status: Time Limit Exceeded

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)
                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: Time Limit Exceeded

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)%(10**9+7))
#print(res)

Submission status: Time Limit Exceeded

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)
place = [set() for _ in range(2 * 10 ** 5)]
for i in range(n):
    dp[i+1] = dp[i]
    for p in place[z[i] - 1]:
        dp[i+1] += dp[p]
    place[z[i] - 1].add(i)
    dp[i+1] %= 10 ** 9 + 7
print(dp[n])

Submission status: Time Limit Exceeded

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)
place = {}
for i in range(n):
    dp[i+1] = dp[i]
    if z[i] not in place:
        place[z[i]] = {i}
    else:
        for p in place[z[i]]:
            dp[i+1] += dp[p]
        place[z[i]].add(i)
    dp[i+1] %= 10 ** 9 + 7
print(dp[n])

Submission status: Time Limit Exceeded

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

result = ["".join(C)]

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 result:
        stone = list(i)
        #print(stone)
        pairs = check(stone)
        #print(pairs)
        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:
                    flag = True
                    result.append(str_stone)

print(len(result))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

M = pow(10, 9) + 7
import sys

dc = {}
al = [0]

rr = [1]


def search(ss, start, end):
    z = al[(start + end)//2]
    nz = al[(start + end)//2+1]
    if z <= ss and ss < nz:
        return (start+end)//2
    elif ss < z:
        return search(ss, start, (start+end)//2)
    else:
        return search(ss, (start+end)//2+1, end)

c = 0
cn = 0
for line in sys.stdin:
    a = int(line)
    if a in dc:
        ss = dc[a]
        if ss != c-1:
            if ss >= al[cn]:
                rr.append((rr[cn]*2)%M)
            else:
                i = search(ss, 0, cn)
                rr.append((rr[cn] + rr[i])%M)
            al.append(c)
            cn += 1
    dc[a] = c
    c += 1
print(rr[cn]%M)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

n = int(input())
L = []
dplist = [1]
last = 0
dic = {}

for i in range(n):
    c = int(input())
    if c not in dic:
        dic[c] = 1
    else:
        dic[c] += 1
    L.append(c)
    if c == last:
        dplist.append(dplist[i])
        continue
    last = c
    re = 0
    if dic[c] > 1:
        for j in range(i-1):
            if L[j] == c:
                re += dplist[j]
    dplist.append(dplist[i]+re)

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

Submission status: Time Limit Exceeded

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):
    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:
        for i,j in ava:
            #print(i,j,ban)
            f(i,j,ban)
            if not ban in ansls:
                cnt += 1
                ansls.append(ban)
    else:
        if not ban in ansls:
            cnt+=1
            ansls.append(ban)
        
        

f(0,0,C)
print(cnt)

Submission status: Time Limit Exceeded

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

Ds = [C]
d = 0
while d < len(Ds):
  for i in range(0, N - 1):
    for j in range(i + 1, N):
      if (Ds[d][i] == Ds[d][j]) & (Ds[d][j - 1] != Ds[d][j]):
        E = []
        for k in range(0, N):
          E.append(Ds[d][k] if (k < i) | (j < k) else Ds[d][i])
        Ds.append(E)
  d = d + 1

count = {}
for D in Ds:
  if "".join(D) not in count:
    count["".join(D)] = 1
  else:
    count["".join(D)] = count["".join(D)] + 1

print(len(count))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
C = []
p = 10**9 + 7
if N <= 2:
    print(1)
else:
    C.append(int(input()))
    C.append(int(input()))
    dp = [1, 1]
    for i in range(2, N):
        C.append(int(input()))
        if C[i] == C[i-1]:
            dp.append(dp[i-1])
        else:
            m = C[i]
            part = C[0:i-1]
            idx = [j for j, x in enumerate(part) if x == m]
            l = len(idx)
            d = dp[i-1]
            for j in idx:
                d += dp[j]
            if l > 1:
                d -= l-1
            dp.append(d)
    print(dp[N-1])

Submission status: Time Limit Exceeded

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

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


def reverse(stone):
    str_stone = "".join(stone)

    if str_stone in result:
        return
    
    result.append(str_stone)

    pairs = check(stone)

    for pair in pairs:
        stone2 = copy.copy(stone)
        color = stone[pair[0]]
        for i in range (pair[0]+1,pair[1]):
            stone2[i] = color
        reverse(stone2)


reverse(C)

print(len(result))

Submission status: Time Limit Exceeded

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

n = int(input())
L = []
dplist = [1]
last = 0

for i in range(n):
    c = int(input())
    L.append(c)
    if c == last:
        dplist.append(dplist[i])
        continue
    last = c
    re = 0
    for j in range(i-1):
        if L[j] == c:
            re += dplist[j]
    dplist.append(dplist[i]+re)

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

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = 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
sys.setrecursionlimit(100000000)
def B():
    n = I()
    memo = [None]*(n+1)
    memo[0] = 1
    def dfs(n):
        if memo[n] != None:
            return memo[n]
        res = 0
        for i in v[n]:
            res += dfs(i)
        memo[n] = res
        return res
    c = IR(n)
    v = [[i-1] for i in range(n)]
    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[y].append(x)
            x = y
    memo = [None]*(n+1)
    memo[0] = 1
    print(dfs(n-1))
#C
def C():
    return

#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: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = 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
sys.setrecursionlimit(100000000)
def B():
    def dfs(n):
        if n == 0:
            return 1
        res = 0
        for i in v[n]:
            res += dfs(i)
        return res
    n = I()
    c = IR(n)
    v = [[i-1] for i in range(n)]
    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[y].append(x)
            x = y
    memo = [None]*(n+1)
    memo[0] = 1
    print(dfs(n-1))
#C
def C():
    return

#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: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
C = np.zeros([N], dtype = int)
p = 10**9 + 7
if N <= 2:
    print(1)
else:
    C[0] = int(input())
    C[1] = int(input())
    dp = np.ones([N], dtype=int)
    for i in range(2, N):
        C[i] = int(input())
        if C[i] == C[i-1]:
            dp[i] = dp[i-1]
        else:
            m = C[i]
            part = C[0:i-1]
            idx = np.where(part == m)
            l = np.size(list(idx))
            d = dp[i-1] + sum(dp[idx])
            if l > 1:
                d -= l-1
            dp[i] = d%p
    print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
strC = ''.join(map(str, C))
cntC = []
for num, i in enumerate(strC):
    try:
        cntC.append(strC[0:num].rindex(i) + 1)
    except ValueError:
        cntC.append(-1)
# print(cntC)

dp = [0] * (N + 10)
dp[0] = 1
for i in range(N):
    if cntC[i] == -1 or cntC[i] == i:
        dp[i + 1] = dp[i]
    else:
        dp[i + 1] = dp[i] + dp[cntC[i]]


print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict


def main():
    # n,m = [int(z) for z in input().split()]
    # table =[
    #     [int(z) for z in input().split()]
    #     for _ in range(n)
    # ]
    V = 10 ** 9 + 7
    n = int(input())
    c = [int(input()) for _ in range(n)]

    table = [0] * (n + 1)
    table[0] = 1

    D = defaultdict(lambda: [])

    for i in range(n):
        ci = c[i]
        if i != 0:
            if c[i - 1] == ci:
                table[i + 1] = table[i] % V
                continue

        pre = D[ci]
        res = table[i]
        for p_index in pre:
            res += table[p_index] % V
            res %= V
        table[i + 1] = res % V

        D[ci].append(i)

    print(table[-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
c = [int(raw_input()) for i in range(n)]
mod = 1000000007

dp = [0] * len(c)
dp[-1] = 1
for i in range(len(c) - 2, -1, -1):
    dp[i] = dp[i + 1]
    try:
        j = c.index(c[i], i + 1)
        if j > i + 1:
            dp[i] = (dp[i] + dp[j]) % mod
    except:
        pass

print dp[0]

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
mod = pow(10, 9) + 7
x = 0
c = []
for _ in range(n):
    y = int(input())
    if not x == y:
        c.append(y)
    x = y
m = len(c)
last = [-1] * (2 * pow(10, 5) + 5)
dp = [0] * m
dpsum = [0] * m
for i in range(m):
    if not last[c[i]] == -1:
        dp[i] = dpsum[last[c[i]]] + 1
    dpsum[i] = dp[i] + dpsum[max(i - 1, 0)]
    dpsum[i] %= mod
    last[c[i]] = i
ans = (dpsum[-1] + 1) % mod
print(ans)

Submission status: Accepted

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

# 解説AC
dp = [1] * n
color = [-1] * max(c)
for i, ci in enumerate(c):
    dp[i] = dp[i - 1]
    if 0 <= color[ci - 1] < i - 1:
        dp[i] += dp[color[ci - 1]]
        dp[i] %= mod
    color[ci - 1] = i
print(dp[-1])

Submission status: Accepted

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

# 解説AC
dp = [1] * n
color = [-1] * max(c)
for i, ci in enumerate(c):
    dp[i] = dp[i - 1]
    if 0 <= color[ci - 1] < i - 1:
        dp[i] += dp[color[ci - 1]]
    color[ci - 1] = i
print(dp[-1] % mod)

Submission status: Accepted

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

# 解説AC
dp = [1] * n
color = [-1] * max(c)
for i, ci in enumerate(c):
    dp[i] = dp[i - 1]
    if 0 <= color[ci - 1] < i - 1:
        dp[i] += dp[color[ci - 1]]
        dp[i] %= mod
    color[ci - 1] = i
print(dp[-1] % mod)

Submission status: Accepted

Solution code:
# 解説 https://betrue12.hateblo.jp/entry/2019/03/17/011847
# from collections import defaultdict

mod = 10 ** 9 + 7

N = int(input())
C = [int(input()) for _ in range(N)]
# L = [-1] * (N + 10)  # 出たところ
# dp = [-1] * (N + 10)
# dp[0] = 1
L  = [-1] * (2*10**5 + 10)
dp = [-1] * (2*10**5 + 10)
dp[0] = 1
 

for i in range(N):
    if L[C[i]] == -1:
        dp[i + 1] = dp[i]
    elif C[i] == C[i - 1]:
        dp[i + 1] = dp[i]
    else:
        dp[i + 1] = dp[i] + dp[L[C[i]]]
    
    dp[i + 1] %= mod
    L[C[i]] = i + 1

print(dp[N])