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:
import sys
input=sys.stdin.readline
N=int(input())
C=[int(input()) for i in range(N)]
C=[C[i] for i in range(N) if i ==0 or C[i-1]!=C[i]]

import collections
table=collections.defaultdict(list)
N=len(C)
dp=[0]*(N+1)
dp[N]=1
mod=10**9 + 7
for i,x in enumerate(C[::-1]):
  dp[N-1-i]=dp[N-i]
  for y in table[x]:
    dp[N-1-i]+=dp[y+1]
  dp[N-1-i]%=mod
  table[x].append(N-1-i)

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
C=[int(input()) for i in range(N)]
C=[C[i] for i in range(N) if i ==0 or C[i-1]!=C[i]]

import collections
table=collections.defaultdict(list)
N=len(C)
dp=[0]*(N+1)
dp[N]=1
mod=10**9 + 7
for i,x in enumerate(C[::-1]):
  dp[N-1-i]=dp[N-i]
  for y in table[x]:
    dp[N-1-i]+=dp[y+1]
  dp[N-1-i]%=mod
  table[x].append(N-1-i)

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
C=[int(input()) for i in range(N)]
C=[C[i] for i in range(N) if i ==0 or C[i-1]!=C[i]]

import collections
table=collections.defaultdict(list)
N=len(C)
dp=[0]*(N+1)
dp[N]=1
mod=10**9 + 7
for i,x in enumerate(C[::-1]):
  dp[N-1-i]=dp[N-i]
  for y in table[x]:
    dp[N-1-i]+=dp[y+1]
    dp[N-1-i]%=mod
  table[x].append(N-1-i)

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
C=[int(input()) for i in range(N)]
C=[C[i] for i in range(N) if i ==0 or C[i-1]!=C[i]]

import collections
table=collections.defaultdict(list)
N=len(C)
dp=[0]*(N+1)
dp[N]=1
mod=10**9 + 7
for i,x in enumerate(C[::-1]):
  dp[N-1-i]=dp[N-i]
  for y in table[x]:
    dp[N-1-i]+=dp[y+1]
  dp[N-1-i]%=mod
  table[x].append(N-1-i)

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    C = [int(input()) for _ in range(N)]

    dp = [1] * (N + 1)
    dp[0] = 1
    D = {c: set() for c in set(C)}
    pre = -1
    for n in range(N):
        c = C[n]
        S = D[c]
        dp[n + 1] = dp[n]
        if pre == c:
            dp[n] = 0
            continue

        if len(S) != 0:
            dp[n + 1] = (dp[n + 1] + sum(dp[s] for s in S)) % mod
        D[c].add(n)
        pre = c
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    C = [int(input()) for _ in range(N)]

    dp = [1] * (N + 1)
    dp[0] = 1
    D = {}
    pre = -1
    for n in range(N):
        c = C[n] 
        S = D.setdefault(c, set())
        dp[n + 1] = dp[n]
        if pre == c:
            dp[n] = 0
            continue
        for s in S:
            dp[n + 1] = (dp[n + 1] + dp[s]) % mod 
        pre = c
        D.setdefault(c, set()).add(n)
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    c = [-1]
    INF = 10**9+7
    for _ in range(N):
        a = int(input())
        if c[-1] == a:
            continue
        c.append(a)
    
    c.pop(0)
    d,M = len(c),max(c)    
    _c = list(set(c))
    
    dp = [1 for _ in range(d+1)]
    c_dp = [[0 for _ in range(d+1)] for _ in range(M+1)]
    for i in range(d):
        for j in _c:
            if c[i] != j:
                c_dp[j][i+1] = c_dp[j][i]
            else:
                dp[i+1] = (c_dp[j][i] + dp[i])%INF
                c_dp[j][i+1] = dp[i+1]
                
    print(dp[-1])
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
  n = int(input())
  a = [[] for row in range(200001)]
  C = [int(input()) for i in range(n)]
  b = 0
  d = [0]
  mod = 10 ** 9 + 7
  mini_ans = 0
  for i,c in enumerate(C):
    if b != c:
      for j in a[c]:
        mini_ans += (d[j] + 1) % mod
      a[c].append(i)
    d.append(mini_ans % mod)
    b = c
  print(d[-1]+1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

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

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

main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
C = dict()
i, cp, lr = 0, 0, []
for _ in range(N):
    c = int(input())
    if c != cp:
        if c in C.keys():
            lr.append([C[c], i])
        C[c] = i
        cp = c
        i += 1
length = i
lr.sort()
hist, add, i, ans = [0] * length, [0] * length, 0, 0
for l, r in lr:
    while i <= l:
        hist[i] = hist[i-1] + add[i]
        ans += add[i]
        i += 1
    add[r] += hist[l] + 1
if len(lr) != 0:
    for i in range(l+1, length):
        ans += add[i]
print((ans+1) % (10**9+7))

Submission status: Time Limit Exceeded

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

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

    pre = -1
    for i in range(num)[::-1]:
        if data[i] == pre:
            data.pop(i)
        pre = data[i]

    num = len(data)

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

    for i in range(num):
        now_num = data[i]
        dp[i + 1] = (dp[i] + dic[now_num]) % mod
        dic[now_num] += dp[i]
        dic[now_num] %= mod

    print(dp[num])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

c = []
dp = [0] * (n + 1)
for i in range(n):
    stone = int(input())
    if len(c) == 0:
        dp[i + 1] = 1
    else:
        if stone in c and c[-1] is not stone:
            plc = len(c) - 1 - c[::-1].index(stone)
            dp[i + 1] = dp[i] + dp[plc + 1]
        else:
            dp[i + 1] = dp[i]
    c.append(stone)

print(dp[-1])

Submission status: Time Limit Exceeded

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

memo={}
new_C=[]

pre = 1.5
i=0
for c in C:
    if c!= pre:
        new_C.append(c)
        memo.setdefault(c,[]).append(i)
        i+=1
    pre=c

answer = [0]*len(new_C)
answer[0] = 1

for i in range(1, len(new_C)):
    try:
        prev_index = i-1 - new_C[i-1::-1].index(new_C[i])
        answer[i] = (answer[i-1] + answer[prev_index]) %mod
    except:
        answer[i] = answer[i-1]

print(answer[-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
prob = [10**8] + [int(input()) for _ in range(N)]
ans = [0 for _ in range(N + 1)]
ans[0] = 1
for i in range(1, N + 1):
  for j in range(i):
    if prob[j + 1] == prob[i] and prob[j] != prob[i]:
      ans[i] += ans[j]
print(ans[N])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

for i in range(2,n+1):
    for j in reversed(range(1,i)):
        if c[i-1] != c[i] == c[j] != c[j-1]:
            dp[i] = dp[i-1]+dp[j]
            break
    else:
        dp[i] = dp[i-1]
print(dp[-1])

Submission status: Time Limit Exceeded

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

dp = [0] * N
dp[0] = 1

for i in range(1, N):
    if c[i] == c[i - 1]:
        dp[i] = dp[i - 1]
        continue
    for j in range(i):
        if j == 0 and c[j] == c[i]:
            dp[i] += 1
        if c[i] == c[j + 1] and c[j] != c[j + 1]:
            dp[i] += dp[j]
print(dp[N - 1])

Submission status: Time Limit Exceeded

Solution code:
#import time
#t = []

N = int(input())

#st = time.time()

sums = [1]  # pair number sum until index
#cpos = [-1] * (2 * 10 ** 5 + 1)    # positions of each color
cpos = {}
lastc = -1  # last color of input
C = []      # color stone list

#print("prepare time [ms] = {}".format(1000 * (time.time() - st)))

for i in range(N):
    c = int(input())

#    sti = time.time()
#    st = time.time()

    if(lastc != c):
        lastc = c
        C.append(c)
        cnt = len(C)
#        print("lastc = {}, cnt = {}, C = {}".format(lastc, cnt, C))

#        print("prepare time in loop [ms] = {}".format(1000 * (time.time() - st)))
#        st = time.time()

        if(c in cpos):
            s = sums[-1]
            for pos in cpos[c]:
                s += sums[pos - 1]
            sums.append(s)
            cpos[c].append(cnt)
        else:
            sums.append(sums[-1])
            cpos[c] = [cnt]

#        print("calc time [ms] = {}".format(1000 * (time.time() - st)))
#        print("cpos = " + str(cpos))

#    print("iteration time [ms] = {}".format(1000 * (time.time() - sti)))

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

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
sums = [1]  # pair number sum until index
cpos = [-1] * (2 * 10 ** 5 + 1)    # positions of each color
#cpos = [-1] * (10)
lastc = -1  # last color of input
C = []      # color stone list
for i in range(N):
    c = int(input())
    if(lastc != c):
        lastc = c
        C.append(c)
        cnt = len(C)
#        print("lastc = {}, cnt = {}, C = {}".format(lastc, cnt, C))
        if(-1 == cpos[c]):
            cpos[c] = [cnt]
            sums.append(sums[-1])
        else:
            s = sums[-1]
            for pos in cpos[c]:
                s += sums[pos - 1]
            sums.append(s)
            cpos[c].append(cnt)
#        print("cpos = " + str(cpos))

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

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

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
stones = [input() for n in range(num)]

def clean(lis):
    rev = []
    lis = lis + ['end']
    for n in range(len(lis) - 1):
        if lis[n] != lis[n + 1]:
            rev.append(lis[n] )
    return rev

stones = clean(stones)

def rec(lis):
    cnt = 0
    for i, s1 in enumerate(lis):
        for j, s2 in enumerate(lis[i + 1:]):
            if s1 == s2:
                cnt += 1
                if len(lis[j + i + 2:]) > 1:
                    cnt += rec(lis[j + i + 2:])
    return cnt

print((rec(stones) + 1) % (1000000007))

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
stones = [input() for n in range(num)]

def clean(lis):
    rev = []
    lis = lis + ['end']
    for n in range(len(lis) - 1):
        if lis[n] != lis[n + 1]:
            rev.append(lis[n] )
    return rev

stones = clean(stones)

def rec(lis):
    cnt = 0
    for i, s1 in enumerate(lis):
        for j, s2 in enumerate(lis[i + 1:]):
            if s1 == s2:
                cnt += 1
                cleaned = clean(lis[j + i + 2:])
                if len(lis[j + i + 2:]) > 1:
                    cnt += rec(lis[j + i + 2:])
    return cnt

print((rec(stones) + 1) % (1000000007))

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
stones = [input() for n in range(num)]

def clean(lis):
    rev = []
    lis = lis + ['end']
    for n in range(len(lis) - 1):
        if lis[n] != lis[n + 1]:
            rev.append(lis[n] )
    return rev

stones = clean(stones)

def rec(lis):
    cnt = 0
    for i, s1 in enumerate(lis):
        for j, s2 in enumerate(lis[i + 1:]):
            if s1 == s2:
                cnt += 1
                cleaned = clean(lis[j + i + 2:])
                if len(cleaned) > 1:
                    cnt += rec(cleaned)
    return cnt

print((rec(stones) + 1) % (1000000007))

Submission status: Time Limit Exceeded

Solution code:
#  1 3 1 2 3 3 2

#  1 3 1 2 3 3 2
#      i
mod = 10 ** 9 + 7
N=int(input())
C=[0]
pre = 0
for i in range(N):
    cur = int(input())
    if pre != cur:
        C.append(cur)
        pre = cur
C.append(0)
N=len(C)-2
# dp[i] = 左からi個までの選び方が何通りか
dp=[0]*(N+2)
dp[0]=1
for i in range(1,N+1):
    dp[i]=dp[i-1]
    for j in range(1,i):
        if C[j]==C[i]:
            dp[i] = (dp[i] + dp[j-1]) % mod
    #print(i,dp[i])
print(dp[N] % mod)

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())
    if c == C[-1]:
        N -= 1
    else:
        C.append(c)
#C = C+c
dp = [0] * (N + 2)
dp_2 = [0] * (N + 2)
color = [[]for i in range((2*(10**5)+2))]
dp[0] = 1
dp[1] = 1
dp_2[0] = 1
dp_2[1] = 1
color[C[1]].append(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]
    # ↓これだと遅い(当日はこれ以上の高速化が思いつけなくてTLE)
    dp_2[i] = dp_2[i - 1] + sum([dp_2[col - 1] for col in color[C[i]]])
    color[C[i]].append(i)
    dp[i] %= (10 ** 9 + 7)
# print(C)
# print(dp)
# print(dp_2)
print(dp[N])

Submission status: Time Limit Exceeded

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

idx = 1
for i in range(n):
    tmp = int(input())
    if c[-1] != tmp:
        r[idx] += d[tmp]
        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]
    for j in r[i]:
        dp[i] += (dp[j-1]%mod)
    dp[i] %= mod

print(dp[-1])

Submission status: Time Limit Exceeded

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]] = [i]
        else:
            temp = dp[i - 1]
            if A[i] in current_dic:
                for x in current_dic[A[i]]:
                    temp += dp[x - 1]
                    temp %= MOD
                current_dic[A[i]] += [i]
            else:
                current_dic[A[i]] = [i]

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

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
   
i=0 
while i+1<len(C):
    if C[i]==C[i+1]:
        C.pop(i+1)
    else:
        i+=1

DP = [1]
dic = {}      
Sum = 1

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
   
i=0 
while i+1<len(C):
    if C[i]==C[i+1]:
        C.pop(i+1)
    else:
        i+=1

DP = [1]
dic = {}      

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
   
i=0 
while i+1<len(C):
    if C[i]==C[i+1]:
        C.pop(i+1)
    else:
        i+=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: Time Limit Exceeded

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
   
i=0 
while i+1<len(C):
    if C[i]==C[i+1]:
        C.pop(i+1)
    else:
        i+=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: Time Limit Exceeded

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]] = [i]
    else:
        dp[i] = dp[i - 1]
        for j in col[C[i - 1]]:
            dp[i] += dp[j - 1]
            dp[i] %= MOD
        col[C[i - 1]].append(i)

print(dp[N])

Submission status: Time Limit Exceeded

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 = [[] for i in range(200005)]
pre = -1
dp[0] = 1
for i in range(1, N + 1):
    if len(col[C[i - 1]]) == 0:
        dp[i] = dp[i - 1]
        col[C[i - 1]].append(i)
    else:
        dp[i] = dp[i - 1]
        for j in col[C[i - 1]]:
            dp[i] += dp[j - 1]
            dp[i] %= MOD
        col[C[i - 1]].append(i)

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
   
i=0 
while i+1<len(C):
    if C[i]==C[i+1]:
        C.pop(i+1)
    else:
        i+=1

DP = [1]
dic = {}      

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

Submission status: Time Limit Exceeded

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

pairs = []
pairnum = 0
for i in range(N - 2):
    if(C[i + 1] == C[i]):
#        print("col = {} : [{} - {}] : same -> skip".format(C[i], i, i + 1))
        continue
    prev = 0
    for j in range(i + 2, N):
#        print("C[{}] = {}, C[{}] = {}".format(i, C[i], j, C[j]))
        if(prev == C[j]):
            continue
        if(C[j] == C[i]):
#            print("col = {} : [{} - {}]".format(C[i], i, j))
            pairs.append([i, j])
            pairnum = pairnum + 1
        prev = C[j]
#print(str(pairs))

ans = 0
for i in range(1, 2 ** pairnum):
    lastidx = -1
    nocount = 0
#    print("check pair pattern = " + hex(i))
    for j in range(pairnum):
#        print("last idx = {}".format(lastidx))
        if(1 == ((i >> j) & 1)):
            if(lastidx >= pairs[j][0]):
                nocount = 1
                break
            else:
                lastidx = pairs[j][1]
    if(0 == nocount):
        ans = ans + 1
#        print("add pair pattern = " + hex(i))
ans = ans + 1
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
c = [int(input()) for i in range(n)]
dp = [1 for i in range(2*(10**5)+1)]
dp2 = [-1 for i in range(2*(10**5)+1)]
dp3 = [0 for i in range(2*(10**5)+1)]

ans = 1

def count(s):
  memo = {}
  res = 1
  for i in range(len(s)):
    if s[i] not in memo:
      memo[s[i]] = 1
    else:
      memo[s[i]] += 1
  for i in memo:
    res = res*2**(memo[i]-1)
  return res


dp2[c[0]] = 0
dp3[c[0]] += 1
#print("dp",dp)
#print("dp2",dp2)
     
for i in range(1,n):
  
  if c[i] != c[i-1]:
    if dp2[c[i]] == -1:
      dp2[c[i]] = i
      dp3[c[i]] += 1
    else:
      dp[c[i]] = count(c[dp2[c[i]]:i])*dp[c[i]]*(dp3[c[i]])
      ans += dp[c[i]]
      ans = ans % 1000000007 
      dp3[c[i]] += 1
      
      dp2[c[i]] = i
#  print(i,"dp",dp)
#  print(i,"dp2",dp2)
#  print(i,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
c = [int(input()) for i in range(n)]
dp = [1 for i in range(2*(10**5)+1)]
dp2 = [-1 for i in range(2*(10**5)+1)]
dp3 = [0 for i in range(2*(10**5)+1)]

ans = 1

def count(s):
  memo = {}
  res = 1
  for i in range(len(s)):
    if s[i] not in memo:
      memo[s[i]] = 1
    else:
      memo[s[i]] += 1
  for i in memo:
    res = res*2**(memo[i]-1)
  return res


dp2[c[0]] = 0
dp3[c[0]] += 1
#print("dp",dp)
#print("dp2",dp2)
     
for i in range(1,n):
  
  if c[i] != c[i-1]:
    if dp2[c[i]] == -1:
      dp2[c[i]] = i
      dp3[c[i]] += 1
    else:
      dp[c[i]] = count(c[dp2[c[i]]:i])*dp[c[i]]*(dp3[c[i]])
      ans += dp[c[i]]
      dp3[c[i]] += 1
      
      dp2[c[i]] = i
#  print(i,"dp",dp)
#  print(i,"dp2",dp2)
#  print(i,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
p = 10 ** 9 + 7
C = [0] * (N + 1)
D = defaultdict(list)
DP = [[0, 0] for i in range(N + 1)]
DP[0] = [1, 0]
LC = 0
LP = -1
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]:
    for d in D[C[i]]:
      DP[i][1] += DP[d][0]
    D[C[i]] += [i]
print(sum(DP[N]) % p)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
p = 10 ** 9 + 7
C = [0] * (N + 1)
D = defaultdict(list)
DP = [[0, 0] for i in range(N + 1)]
DP[0] = [1, 0]
LC = 0
LP = -1
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]:
    for d in D[C[i]]:
      DP[i][1] += DP[d][0]
    D[C[i]] += [i]
print(sum(DP[N]) % p)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
N = int(input())
C = []
i = 1
places = {}
for _ in range(N):
    c = int(input())
    if C != [] and c != C[-1]:
        C.append(c)
        if c not in places:
            places[c] = [i]
        else:
            places[c].append(i)
        i += 1
    if C == []:
        C.append(c)
        places[c] = [i]
        i += 1
dp = [1]
# print(C)
# print(places)
for i in range(1, len(C)+1):
    c = C[i-1]
    next_dp = dp[i-1]
    if len(places[c]) >= 2:
        for pos in places[c]:
            if pos >= i:
                break
            next_dp += dp[pos-1]
    dp.append(next_dp % mod)
# print(dp)
print(dp[len(C)])

Submission status: Time Limit Exceeded

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
    idxs = defaultdict(list)
    for i, c in enumerate(C):
        ret = dp[i]
        if c in idxs.keys():
            for j in idxs[c]:
                ret += dp[j]
        dp[i + 1] = ret % MOD
        idxs[c].append(i)

    ans = dp[len(C)]

    return ans % MOD

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N = read_int()[0]
big = 10**9 + 7
C = []
for _ in range(N):
    C.append(read_int()[0])

rec_res = 0


def rec(n):
    global rec_res
    color = C[n]

    for j in range(N-1, n+1,-1):
        if C[j] == color and C[j-1] != color:
            rec_res += 1
            if not len(C[j + 1:]) < 3:
                rec(j + 1)
    return rec_res


if __name__ == "__main__":
    for i in range(N):
	    rec(i)
    print((rec_res + 1) % big)

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)
N = len(pattern)

def onehop(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),}
allpattern = set()
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:
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())
    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] + sum([dp[col - 1] for col in color[C[i]]])
    color[C[i]].append(i)
    dp[i] %= (10 ** 9 + 7)
# print(dp)
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

maxpos_of_color = {}
num_of_color = {}
count_before = {}
precol = 0

for i in range(N):
    c = int(input())
    if not c in num_of_color:
        num_of_color[c] = 0
    if precol != c:
        if num_of_color[c] > 0:
            count_before[i] = num_of_color[c]
            for j in range(maxpos_of_color[c]):
                if j in count_before:
                    count_before[i] += count_before[j]
        num_of_color[c] += 1
    maxpos_of_color[c] = i
    precol = c

print(sum(count_before.values())+1)

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
n = int(input())
d = {}
l = np.array([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 = np.append(l,1)
    d[c] = copy.deepcopy(l)
  bef = c
print((sum(l)+1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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
L = len(C)
A = np.array(C)

ans = 1
f = np.ones(L + 1, dtype="int")
for i in range(2, L):
    ans += np.sum(f[A[:i-1] == A[i]])
    f[i + 1] = ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=""
ans=0
for _ in range(n):
    c = input()
    s+=c

def good_str(s):
    refs = s[:]+'#'
    u = ""
    for i in range(len(s)):
        if s[i] == refs[i+1]:
            pass
        else:
            u+=s[i]
    return u

s_set=set()
def dfs(s2):
    # print("-------s")
    # print(" s is ", s2)
    global ans, s_set
    if s2 in s_set:
        return
    s_set.add(s2)
    ans+=1
    # print("ans ", ans)
    m={}
    for i in range(len(s2)):
        if s2[i] not in m:
            m[s2[i]]=[i]
        else:
            m[s2[i]].append(i)
    # print(m)
    # print("keys", m.keys())
    for c in m.keys():
        # print(c,"|",m[c])
        for left in m[c]:
            for right in reversed(m[c]):
                if left >= right:
                    pass
                else:
                    # print(left, right)
                    new_str=""
                    for i in range(len(s2)):
                        if i <= left:
                            new_str+=s2[i]
                        elif i <= right:
                            new_str+=s2[left]
                        else:
                            new_str+=s2[i]
                    # print("new_str is ", new_str)
                    # 新しい文字列を作る
                    dfs(new_str)
    # print("--------e")


# dfs(good_str(s))
dfs(s)
# print("ans")
# print(ans)
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N = read_int()[0]
big = 10**9 + 7
C = []
for _ in range(N):
    C.append(read_int()[0])

rec_res = 0
def rec(s):
    global rec_res
    color = s[0]

    for j in range(len(s)-1, 1,-1):
        if s[j] == color and s[j-1] != color:
            rec_res += 1
            if not len(s[j + 1:]) < 3:
                rec(s[j + 1:])
    return rec_res


if __name__ == "__main__":
    for i in range(N):
	    rec(C[i:])
    print((rec_res + 1) % big)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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
L = len(C)
A = np.array(C)

ans = 1
f = np.ones(L + 1, dtype="int")
for i in range(2, L):
    g = f[:i-1]
    ans += np.sum(g[A[:i-1] == A[i]])
    f[i + 1] = ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
C = []
for i in range(N):
  c = input()
  if len(C) == 0:
    C.append(c)
  elif C[len(C) - 1] != c:
    C.append(c)

def f(subC):
  # print(subC)
  max = len(subC) - 1
  i = 0
  a = 0
  while i < max:
    j = i + 1
    while j < len(subC):
      # print(subC[i] + " == " + subC[j])
      if subC[i] == subC[j]:
        a2 = f(subC[j:len(subC)])
        a = a + 1 + (2 ** a2 if a2 > 0 else 0)
        max = j if max > j else max
        break
      j = j + 1
    i = i + 1
  # print(a)
  return(a)

print((f(C) + 1) % (10 ** 9 + 7))