Problem:


Score : 600 points

Problem Statement

You are given an integer sequence of length n+1, a_1,a_2,...,a_{n+1}, which consists of the n integers 1,...,n.
It is known that each of the n integers 1,...,n appears at least once in this sequence.

For each integer k=1,...,n+1, find the number of the different subsequences (not necessarily contiguous) of the given sequence with length k, modulo 10^9+7.

Notes

If the contents of two subsequences are the same, they are not separately counted even if they originate from different positions in the original sequence.

A subsequence of a sequence a with length k is a sequence obtained by selecting k of the elements of a and arranging them without changing their relative order. For example, the sequences 1,3,5 and 1,2,3 are subsequences of 1,2,3,4,5, while 3,1,2 and 1,10,100 are not.

Constraints

1 \leq n \leq 10^5

1 \leq a_i \leq n

Each of the integers 1,...,n appears in the sequence.

n and a_i are integers.

Input

Input is given from Standard Input in the following format:

n
a_1 a_2 ... a_{n+1}

Output

Print n+1 lines.
The k-th line should contain the number of the different subsequences of the given sequence with length k, modulo 10^9+7.

Sample Input 1

3
1 2 1 3

Sample Output 1

3
5
4
1

There are three subsequences with length 1: 1 and 2 and 3.

There are five subsequences with length 2: 1,1 and 1,2 and 1,3 and 2,1 and 2,3.

There are four subsequences with length 3: 1,1,3 and 1,2,1 and 1,2,3 and 2,1,3.

There is one subsequence with length 4: 1,2,1,3.

Sample Input 2

1
1 1

Sample Output 2

1
1

There is one subsequence with length 1: 1.

There is one subsequence with length 2: 1,1.

Sample Input 3

32
29 19 7 10 26 32 27 4 11 20 2 8 16 23 5 14 6 12 17 22 18 30 28 24 15 1 25 3 13 21 19 31 9

Sample Output 3

32
525
5453
40919
237336
1107568
4272048
13884156
38567100
92561040
193536720
354817320
573166440
818809200
37158313
166803103
166803103
37158313
818809200
573166440
354817320
193536720
92561040
38567100
13884156
4272048
1107568
237336
40920
5456
528
33
1

Be sure to print the numbers modulo 10^9+7.



Sample input:
3
1 2 1 3


Sample output:
3
5
4
1

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def comb(n,k,p):
    from math import factorial
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p


def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7

    pos = [-1] * 100010
    for i, a in enumerate(A):
        if pos[a] != -1:
            pos1, pos2 = min(pos[a], i), max(pos[a], i)
            break
        pos[a] = i

    dist = pos2 - pos1
    for i in range(1, N + 2):
        ans = comb(N + 1, i, MOD)
        if i <= dist:
            ans -= comb(N + 1 - dist - 1, i - 1, MOD)

        print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [int(x) for x in input().split()]

found = {}
for i, a in enumerate(A):
    if a in found:
        dup = a
        dup_1 = found[a]
        dup_2 = i
    found[a] = i

from functools import lru_cache

@lru_cache(maxsize=None)
def gfp_inv(x, p):
    return pow(x, p - 2, p)

@lru_cache(maxsize=None)
def fact(n, m, p):
    ret = 1
    for i in range(m, n + 1):
        ret = (ret * i) % p
    return ret

def comb(n, m):
    if m < 0 or n < m: return 0
    if n == m: return 1
    return fact(n, n - m + 1, p) * gfp_inv(fact(m, 1, p), p) % p

p = 10**9 + 7

intv = dup_2 - dup_1 - 1
for k in range(1, n + 2):
    ans = comb(n + 1, k)
    ans -= comb(n + 1 - intv - 2, k - 1)
    print(ans % p)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [int(x) for x in input().split()]

found = {}
for i, a in enumerate(A):
    if a in found:
        dup = a
        dup_1 = found[a]
        dup_2 = i
    found[a] = i

from functools import lru_cache

def gfp_inv(x, p):
    return pow(x, p - 2, p)

@lru_cache()
def fact(n, m, p):
    ret = 1
    for i in range(m, n + 1):
        ret = (ret * i) % p
    return ret

def comb(n, m):
    if m < 0 or n < m: return 0
    if n == m: return 1
    return fact(n, n - m + 1, p) * gfp_inv(fact(m, 1, p), p) % p

p = 10**9 + 7

intv = dup_2 - dup_1 - 1
for k in range(1, n + 2):
    ans = comb(n + 1, k)
    ans -= comb(n + 1 - intv - 2, k - 1)
    print(ans % p)

Submission status: Time Limit Exceeded

Solution code:
#list_int 並べて出力 print (' '.join(map(str,ans_li)))
#list_str 並べて出力 print (' '.join(list))

# 2進数 format(10, 'b') # '1010'

# aa=[int(input()) for i in range(n)]

#for i,name in enumerate(list)

''' 二次元配列を一列ずつ
for i in ans:
	print(*i)
'''
''' heapq
queue = []
heapq.heapify(queue) #heapqの作成
heapq.heappush(queue,num) #numのpush(値の追加)
pop = heapq.heappop(queue) #numのpop(最小値の出力)
pop = heapq.heappushpop(queue,num) #push -> pop

'''

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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

def Comb(n):
    gyakugen = [1]*(n+1)
    fac = [1]*(n+1)

    for i in range(1,n+1):
        fac[i] = (fac[i-1]*i)%mod

    gyakugen[n] = pow(fac[n],mod-2,mod)

    for i in range(n,0,-1):
        gyakugen[i-1] = gyakugen[i]*i

    com = [1]*(n+1)

    for i in range(1,n+1):
        com[i] = (fac[n]*gyakugen[i]*gyakugen[n-i])%mod

    return com

N = int(input())
aa = inpl_int()

i = 1
dd = defaultdict(int)
for i,a in enumerate(aa):
	if dd[a] == 0:
		dd[a] = i+1
	else:
		X1 = dd[a]-1
		X2 = i

L,R = X1,N-X2
ALL = 1


ALL = Comb(N+1)
daburi = Comb(L+R)


for i in range(1,N+2):
	if L+R+1 >= i:
		print(ALL[i]-daburi[i-1])
	else:
		print(ALL[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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

def Comb(n):
    gyakugen = [1]*(n+1)
    fac = [1]*(n+1)

    for i in range(1,n+1):
        fac[i] = (fac[i-1]*i)%mod

    gyakugen[n] = pow(fac[n],mod-2,mod)

    for i in range(n,0,-1):
        gyakugen[i-1] = gyakugen[i]*i

    com = [1]*(n+1)

    for i in range(1,n+1):
        com[i] = (fac[n]*gyakugen[i]*gyakugen[n-i])%mod

    return com

N = int(input())
aa = inpl_int()

i = 1
while True:
	if aa.count(i)==2:
		X1 = aa.index(i)
		aa[X1] = 0
		X2 = aa.index(i)
		break
	i += 1

L,R = X1,N-X2
ALL = 1


ALL = Comb(N+1)
daburi = Comb(L+R)


for i in range(1,N+2):
	if L+R+1 >= i:
		print(ALL[i]-daburi[i-1])
	else:
		print(ALL[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
e = list(map(int,input().split()))
mod = 1000000007
kai = [0]*(N+3)
#被り探し
for i in range(N):
  d = e[i]
  e[i] = e[i]+ 9999999
  try:
    f = e.index(d)
    break
  except:
    pass
e = []
g = i +0
for i in range(N+3):
  if i ==0:
    kai[i] = 1
  else:
    kai[i] = (kai[i-1]*(i))%mod
def comb(n,k,p):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=kai[n] 
  b=kai[k] 
  c=kai[n-k] 
  b = pow(b,mod-2,mod)
  c = pow(c,mod-2,mod)
  return (a*b*c)%mod
h = [1]*((N+6)//2)
for j in range((N+4)//2):
  h[j+1] = comb(N+1,j+1,mod)
for j in range(N+1):
  if N-j>N/2:
    print(h[j+1]-comb(g+N-f,j,mod))
  else:
    print(h[N-j]-comb(g+N-f,j,mod))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
e = list(map(int,input().split()))
mod = 1000000007
kai = [0]*(N+3)
#被り探し
for i in range(N):
  d = e[i]
  e[i] = e[i]+ 9999999
  try:
    f = e.index(d)
    break
  except:
    pass
e = []
g = i +0
for i in range(N+3):
  if i ==0:
    kai[i] = 1
  else:
    kai[i] = (kai[i-1]*(i))%mod
def comb(n,k,p):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=kai[n] 
  b=kai[k] 
  c=kai[n-k] 
  b = pow(b,mod-2,mod)
  c = pow(c,mod-2,mod)
  return (a*b*c)%mod
for j in range(N+1):
  print(comb(N+1,j+1,mod)-comb(g+N-f,j,mod))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
e = list(map(int,input().split()))
mod = 1000000007
kai = [0]*(N+3)
#被り探し
for i in range(N):
  d = e[i]
  e[i] = e[i]+ 9999999
  try:
    f = e.index(d)
    break
  except:
    pass
e = []
g = i +0
for i in range(N+3):
  if i ==0:
    kai[i] = 1
  else:
    kai[i] = (kai[i-1]*(i))%mod
def comb(n,k,p):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=kai[n] %p
  b=kai[k] %p
  c=kai[n-k] %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
for j in range(N+1):
  print(comb(N+1,j+1,mod)-comb(g+N-f,j,mod))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
e = list(map(int,input().split()))
mod = 1000000007
def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
#被り探し
for i in range(N):
  d = e[i]
  e[i] = e[i]+ 9999999
  try:
    f = e.index(d)
    break
  except:
    pass
for j in range(N+1):
  print(comb(N+1,j+1,mod)-comb(i+N-f,j,mod))

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9+7

def nCr(n,r):
    if n < r:
        return 0
    f = math.factorial
    return (f(n) // f(r) // f(n-r)) % MOD

n = int(input())
a = list(map(int, input().split()))

d = sum(a)-n*(n+1)//2
x = a.index(d)
y = a[x+1:].index(d)+x+1

for i in range(1, n+2):
    print(nCr(n+1, i) - nCr((n+x-y), (i-1)))

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k,p):
	from math import factorial
	if n<0 or k<0 or n<k: return 0
	if n==0 or k==0: return 1
	a,b,c = factorial(n)%p,factorial(k)%p,factorial(n-k)%p
	return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
	if b==0: return 1
	elif b%2==0:
		d = power_func(a,b//2,p)
		return d**2 %p
	elif b%2==1: return (a*power_func(a,b-1,p))%p
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
twice = Counter(a).most_common(1)[0][0]
x,y = (i for i,j in enumerate(a) if j == twice)
num,y = 1,n-y
for i in range(1,x+y+2):
	ans = comb(n+1,i,10**9+7)
	for j in range(max(0,i-y-1),min(i,x+1)):
		ans -= comb(x,j,10**9+7)*comb(y,i-j-1,10**9+7)
	print(ans)
for i in range(x+y+2,n+2): print(comb(n+1,i,10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from math import factorial
n = int(input())
print(n)
a = [int(i) for i in input().split()]
twice = Counter(a).most_common(1)[0][0]
x,y = (i for i,j in enumerate(a) if j == twice)
num,y = n+1,n-y
X,Y,numx,numy = [1],[1],1,1
for i in range(1,x+1):
	numx = numx*(x-i+1)//i
	X.append(numx)
for i in range(1,y+1):
	numy = numy*(y-i+1)//i
	Y.append(numy)
for i in range(2,x+y+2):
	num = num*(n+2-i)//i
	ans = num
	for j in range(max(0,i-y-1),min(i,x+1)):
		ans -= X[j]*Y[i-j-1]
	print(ans%(10**9+7))
for i in range(x+y+2,n+2):
	num = num*(n+2-i)//i
	print(num%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from math import factorial
n = int(input())
print(n)
a = [int(i) for i in input().split()]
twice = Counter(a).most_common(1)[0][0]
x,y = (i for i,j in enumerate(a) if j == twice)
num,y = n+1,n-y
X,Y = factorial(x),factorial(y)
for i in range(2,x+y+2):
	num = num*(n+2-i)//i
	ans,numx,numy = num,1,1
	for j in range(max(0,i-y-1),min(i,x+1)):
		if j==0: ans -= Y//(factorial(i-1)*factorial(y-i+1))
		elif j==i-1: ans -= X//(factorial(j)*factorial(x-j))
		else: ans -= (X//(factorial(j)*factorial(x-j)))*(Y//(factorial(i-j-1)*factorial(y-i+j+1)))
	print(ans%(10**9+7))
for i in range(x+y+2,n+2):
	num = num*(n+2-i)//i
	print(num%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


# 2回表れている値とそのインデックスを取得
G = set()
for a in A:
    if a in G:
        C = a
    else:
        G.add(a)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

X = factorial(N+1)
O = factorial(outside)

L = list(range(1, N+2))
M = [1] + list(range(1, outside+1))

l1 = 1
l2 = X
o1 = O
oc = 0
X %= MOD
O %= MOD

for k in range(1, len(A)+1):
    l1 *= k
    l2 //= L[-k]
    if k > outside + 1:
        Y = pow((l1 * l2) % MOD, MOD-2, MOD)
        print((X * Y) % MOD)
    else:
        oc += 1
        Y = pow(l1 * l2 % MOD, MOD - 2, MOD)
        Y2 = pow(l1//k * o1 % MOD, MOD - 2, MOD)
        print(((X * Y) % MOD - (O * Y2) % MOD))
        o1 //= M[-oc]

Submission status: Time Limit Exceeded

Solution code:
from statistics import mode
from math import factorial

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

X = factorial(N+1)
O = factorial(outside)

L = list(range(1, N+2))
M = [1] + list(range(1, outside+1))

l1 = 1
l2 = X
o1 = O
oc = 0
X %= MOD
O %= MOD

for k in range(1, len(A)+1):
    l1 *= k
    l2 //= L[-k]
    if k > outside + 1:
        Y = pow((l1 * l2) % MOD, MOD-2, MOD)
        print((X * Y) % MOD)
    else:
        oc += 1
        Y = pow(l1 * l2 % MOD, MOD - 2, MOD)
        Y2 = pow(l1//k * o1 % MOD, MOD - 2, MOD)
        print(((X * Y) % MOD - (O * Y2) % MOD))
        o1 //= M[-oc]

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


# 2回表れている値とそのインデックスを取得
for a in A:
    if A.count(a) == 2:
        C = a
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

X = factorial(N+1)
O = factorial(outside) % MOD

L = list(range(1, N+2))
l1 = 1
l2 = X

X %= MOD

for k in range(1, len(A)+1):
    l1 *= k
    l2 //= L[-k]
    if k > outside + 1:
        Y = pow((l1 * l2) % MOD, MOD-2, MOD)
        print((X * Y) % MOD)
    else:
        Y = pow(l1 * l2 % MOD, MOD - 2, MOD)
        Y2 = pow((factorial(k-1)) * factorial(outside - k + 1) % MOD, MOD - 2, MOD)
        print(((X * Y) % MOD - (O * Y2) % MOD))

Submission status: Time Limit Exceeded

Solution code:
from statistics import mode
from math import factorial

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

X = factorial(N+1)
O = factorial(outside) % MOD

L = list(range(1, N+2))
l1 = 1
l2 = X

X %= MOD

for k in range(1, len(A)+1):
    l1 *= k
    l2 //= L[-k]
    if k > outside + 1:
        Y = pow((l1 * l2) % MOD, MOD-2, MOD)
        print((X * Y) % MOD)
    else:
        Y = pow(l1 * l2 % MOD, MOD - 2, MOD)
        Y2 = pow((factorial(k-1)) * factorial(outside - k + 1) % MOD, MOD - 2, MOD)
        print(((X * Y) % MOD - (O * Y2) % MOD))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


# 2回表れている値とそのインデックスを取得
for a in A:
    if A.count(a) == 2:
        C = a
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

X = factorial(N+1) % MOD
O = factorial(outside) % MOD

for k in range(1, len(A)+1):
    if k > outside + 1:
        Y = pow((factorial(k)) * factorial(N+1-k) % MOD, MOD-2, MOD)
        print((X * Y) % MOD)
    else:
        Y = pow((factorial(k)) * factorial(N+1-k) % MOD, MOD - 2, MOD)
        Y2 = pow((factorial(k-1)) * factorial(outside - k + 1) % MOD, MOD - 2, MOD)
        print(((X * Y) % MOD - (O * Y2) % MOD))

Submission status: Time Limit Exceeded

Solution code:
from statistics import mode
from math import factorial

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

X = factorial(N+1) % MOD
O = factorial(outside) % MOD

for k in range(1, len(A)+1):
    if k > outside + 1:
        Y = pow((factorial(k)) * factorial(N+1-k) % MOD, MOD-2, MOD)
        print((X * Y) % MOD)
    else:
        Y = pow((factorial(k)) * factorial(N+1-k) % MOD, MOD - 2, MOD)
        Y2 = pow((factorial(k-1)) * factorial(outside - k + 1) % MOD, MOD - 2, MOD)
        print(((X * Y) % MOD - (O * Y2) % MOD))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
#重複始点終点調査
se=[]
for i in range(len(A)):
  if A[i]==sum(A)-N*(N+1)/2:
    se.append(i)
l=se[0]
r=se[1]

mod=10**9+7
 
#階乗計算
factorial=[1]
inverse=[1]
for i in range(1,N+2):
    factorial.append(factorial[-1]*i %mod)
    inverse.append((pow(factorial[i], mod-2, mod)))
#combination計算
def nCr(n,r):
  if n<r or n==0 or r==0:
    return 0
  return factorial[n] * inverse[r] * inverse[n-r] % mod

print(N)
for i in range(2,N+2):
    print(int(nCr(N+1,i)-nCr(l+N-r,i-1))%mod)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
#重複始点終点調査
se=[]
for i in range(len(A)):
  if A[i]==sum(A)-N*(N+1)/2:
    se.append(i)

mod=10**9+7
 
#階乗計算
factorial=[1]
inverse=[1]
for i in range(1,N+2):
    factorial.append(factorial[-1]*i %mod)
    inverse.append((pow(factorial[i], mod-2, mod)))
#combination計算
def nCr(n,r):
  if n<r or n==0 or r==0:
    return 0
  return factorial[n] * inverse[r] * inverse[n-r] % mod

print(N)
for i in range(2,N+2):
    print(int(nCr(N+1,i)-nCr(se[0]+N-se[1],i-1))%mod)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
#重複始点終点調査
se=[]
for i in range(len(A)):
  if A[i]==sum(A)-N*(N+1)/2:
    se.append(i)

mod=10**9+7
 
#階乗計算
factorial=[1]
for i in range(1,N+2):
    factorial.append(factorial[i-1]*i %mod)
#逆元計算
inverse=[0]*(N+2)
inverse[N+2-1] = pow(factorial[N+2-1], mod-2,mod)
for i in range(N+2-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod
#combination計算
def nCr(n,r):
  if n<r or n==0 or r==0:
    return 0
  return factorial[n] * inverse[r] * inverse[n-r] % mod

print(N)
if N==1:
  print(N)
else:
  for i in range(1,N+1):
    print(int(nCr(N+1,i+1)-nCr(se[0]+N-se[1],i))%mod)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
#重複始点終点調査
se=[]
for i in range(len(A)):
  if A[i]==sum(A)-N*(N+1)/2:
    se.append(i)

mod=10**9+7
 
#繰り返し二乗法
def great_power(x, y):
    if   y == 0:
      return 1
    elif y == 1:
      return x % mod
    elif y % 2 == 0:
      return great_power(x, y//2)**2 % mod
    else:
      return great_power(x, y//2)**2 * x % mod
#階乗計算
factorial=[1]
for i in range(1,N+2):
    factorial.append(factorial[i-1]*i %mod)
#逆元計算
inverse=[0]*(N+2)
inverse[N+2-1] = great_power(factorial[N+2-1], mod-2)
for i in range(N+2-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod
#combination計算
def nCr(n,r):
  if n<r or n==0 or r==0:
    return 0
  return factorial[n] * inverse[r] * inverse[n-r] % mod

print(N)
if N==1:
  print(N)
else:
  for i in range(1,N+1):
    print(int(nCr(N+1,i+1)-nCr(se[0]+N-se[1],i))%mod)

Submission status: Time Limit Exceeded

Solution code:

MODULO = 10**9 + 7
def modulo(x):
    return x % MODULO

n = int(input())
xs = list(map(int, input().split()))

def locate_dup(xs):
    d = {}
    for i,x in enumerate(xs):
        if x in d:
            return d[x], i
        else:
            d[x] = i
    assert(False)

first, second = locate_dup(xs)


class X:
    def __init__(self, first, second, length):
        self.dup_first = first
        self.dup_second = second
        self.length = length
        self.memo = {}

    def C(self, k, pos):
        v = self.memo.get((k, pos), None)
        if v is None:
            v = self.calcC(k, pos)
            self.memo[(k, pos)] = v
        return v


    def calcC(self, k, pos):
        if k <= 0 or pos >= self.length:
            return 0
        elif k == 1:
            if pos <= self.dup_first:
                return modulo(self.length - pos - 1)
            else:
                return modulo(self.length - pos)
        else:
            if pos == self.dup_first:
                return modulo(self.C(k-1, pos+1) + self.C(k, pos+1) - self.C(k-1, self.dup_second + 1))
            else:
                return modulo(self.C(k-1, pos+1) + self.C(k, pos+1))

x = X(first, second, n+1)

for i in range(0, n+1):
    for j in range(n+1, 1, -1):
        x.C(i+1, j)
    print(x.C(i+1, 0))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
def search(xs):
    global N
    used = [-1] * N
    for i, x in enumerate(xs):
        if used[x-1] != -1:
            return used[x-1], i
        used[x-1] = i
x, y = search(a)
if x > y:
    x, y = y, x

MOD = int(1e9+7)
def pow(a, b):
    global MOD
    x = a
    ret = 1
    while b:
        if b&1:
            ret = (ret * x) % MOD
        x = x * x % MOD
        b >>= 1
    return ret % MOD

fact = [1] * (N+2)
for i in range(N+1):
    fact[i+1] = (i+1) * fact[i]
inv = [pow(fact[i], MOD-2) for i in range(N+2)]

def C(n, m):
    global fact, inv, MOD
    if m == 0:
        return 1
    return fact[n] * inv[n-m] * inv[m] % MOD

def solve(n):
    global N, a, x, y
    ans = C(N+1, n)
    if n <= x+1 + N+1-(y+1):
        ans -= C(x+1 + N+1-(y+1) -1, n-1)
    # if n-1 <= x:
    #     ans -= C(x, n-1)
    # if n-1 <= N - y:
    #     ans -= C(N - y, n-1)
    return ans

print(N)
for i in range(1, N+1):
    print(solve(i+1))

Submission status: Time Limit Exceeded

Solution code:
import scipy.misc as scm
def comb(k,r):
  """kCpを求める"""
  if k<0 or r<0 or r>k: return 0
  elif k==0 or r==0: return 1
  else:
    return (X[k]*Y[r]*Y[k-r])
  
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
n = int(input())
a = list(map(int,input().split()))
p=10**9+7
ans=0
X=[1]  #階乗テーブル
for i in range(1,n+2):
  X+=[ (X[-1]*i) %p ]
Y=[1]*(n+2)  #階乗の逆元テーブル
Y[n+1]=power_func(X[n+1],p-2,p)
for i in range(n,-1,-1):
  Y[i]=Y[i+1]*(i+1) %p

#ダブりをみつける
check = [0]*n
for i in range(n+1):
  if check[a[i]-1]==1: dub = a[i]
  else: check[a[i]-1] = 1

indexes = [i for i, x in enumerate(a) if x == dub]
ind1, ind2  = indexes[0], indexes[1]

for i in range(1,n+2):
  ans = scm.comb(n+1, i,1)
  if ind1 + n -ind2 +1 >= i:
    ans -= scm.comb(ind1 + n -ind2, i-1,1)
  print(ans%p)

Submission status: Time Limit Exceeded

Solution code:
def comb(k,r):
  """kCpを求める"""
  if k<0 or r<0 or r>k: return 0
  elif k==0 or r==0: return 1
  else:
    return (X[k]*Y[r]*Y[k-r])
  
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
n = int(input())
a = list(map(int,input().split()))
p=10**9+7
ans=0
X=[1]  #階乗テーブル
for i in range(1,n+2):
  X+=[ (X[-1]*i) %p ]
Y=[1]*(n+2)  #階乗の逆元テーブル
Y[n+1]=power_func(X[n+1],p-2,p)
for i in range(n,-1,-1):
  Y[i]=Y[i+1]*(i+1) %p

#ダブりをみつける
check = [0]*n
for i in range(n+1):
  if check[a[i]-1]==1: dub = a[i]
  else: check[a[i]-1] = 1

indexes = [i for i, x in enumerate(a) if x == dub]
ind1, ind2  = indexes[0], indexes[1]

for i in range(1,n+2):
  ans = comb(n+1, i)
  if ind1 + n -ind2 +1 >= i:
    for j in range(i):
      ans -= comb(ind1, j)* comb(n-ind2,i-j-1)
  print(ans%p)

Submission status: Time Limit Exceeded

Solution code:
import scipy.misc as scm
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
n = int(input())
a = list(map(int,input().split()))
p=10**9+7
ans=0
X=[1]  #階乗テーブル
for i in range(1,n+1):
  X+=[ (X[-1]*i) %p ]
Y=[1]*(n+1)  #階乗の逆元テーブル
Y[n]=power_func(X[n],p-2,p)
for i in range(n-1,-1,-1):
  Y[i]=Y[i+1]*(i+1) %p

#ダブりをみつける
check = [0]*n
for i in range(n+1):
  if check[a[i]-1]==1: dub = a[i]
  else: check[a[i]-1] = 1

indexes = [i for i, x in enumerate(a) if x == dub]
ind1, ind2  = indexes[0], indexes[1]

for i in range(1,n+2):
  ans = scm.comb(n+1, i, 1)
  if ind1 + n -ind2 +1 >= i:
    for j in range(i):
      ans -= scm.comb(ind1, j, 1)* scm.comb(n-ind2,i-j-1,1)
  print(ans%p)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))

dup = sum(a) - n * (n + 1) // 2
d1 = a.index(dup)
d2 = a.index(dup, d1 + 1)

N = n + 1
Ndup = d1 + n - d2

MOD = 10 ** 9 + 7

# パスカルの三角形
def makePascal(N):
    C = [0 for i in range(N // 2 + 1)]
    C[0] = 1
    for i in range(N):
        for j in range(len(C) - 1, 0, -1):
            C[j] = (C[j] + C[j - 1]) % MOD
    return C

Pascal = {}
Pascal[N] = makePascal(N)
Pascal[Ndup] = makePascal(Ndup)

def comb(n, r):
    if r < len(Pascal[n]):
        return Pascal[n][r]
    elif r <= n:
        return Pascal[n][n - r]
    else:
        return 0

for k in range(1, N + 1):
    C = comb(N, k)
    Cdup = comb(Ndup, k - 1)
    print((C - Cdup) % MOD)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))

dup = sum(a) - n * (n + 1) // 2
d1 = a.index(dup)
d2 = a.index(dup, d1 + 1)

C = n + 1
Cdup = 1
for k in range(1, n + 2):
    print((C - Cdup) % (10 ** 9 + 7))
    C = C * (n + 1 - k) // (k + 1)
    Cdup = Cdup * (d1 + n - d2 - k + 1) // k

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fact
 
MOD = int(1e9 + 7)
def inv(x):
    return pow(x, MOD-2, MOD)
 
def comb(n, r):
    if r>n:
        return 0
    else:
        return (fact(n) * inv(fact(n-r)) * inv(fact(r))) % MOD

N = int(input())
A = list(map(int, input().split()))

L,R = -1,-1
ls = []
for i in range(N+1):
    if A[i] in ls:
        R = i + 1
        L = ls.index(A[i]) + 1
        break
    else:
        ls.append(A[i])

[print( comb(N+1,i) - comb(L+N-R,i-1) ) for i in range(1,N+2)  ]

Submission status: Time Limit Exceeded

Solution code:
def D_11(x):
    n = x[0]  # 整数の数
    a = x[1:]  # 数列
    M = 10**9 + 7  # 求めた解の剰余をこれで取る

    # aの中から重複した要素のインデックス(それぞれl,rとする)を求める
    freq = [0] * (n + 1)
    for i in a:
        freq[i] += 1  # i番目の要素は整数iの個数
    index = [i for i, x in enumerate(a) if x == freq.index(
        max(freq))]  # 重複した数のインデックスを取得
    l, r = index[0] + 1, index[1] + 1  # +1するのは数列が1スタートのため

    # 組み合わせの計算
    def power(x, n, m):
        # 冪乗(powだと時間がかかりすぎるため)+剰余つき
        y = 1
        while n > 0:
            if n % 2 == 0:
                x = (x * x) % m
                n = n // 2
            else:
                y = (y * x) % m
                n -= 1
        return y

    # この部分は関数の外に出しておかないと、呼び出しのたびに計算して遅い
    factrial = [1] * (n + 2)
    inverse = [1] * (n + 2)
    for i in range(1, n + 2):
        factrial[i] = (factrial[i - 1] * i) % M
    inverse[n + 1] = power(factrial[n + 1], M - 2, M)  # フェルマーの小定理からの帰結
    for i in range(n, -1, -1):
        inverse[i] = (inverse[i + 1] * (i + 1)) % M

    def mod_combination(n, r, m):
        if r > n or n < 0 or r < 0:
            return 0
        else:
            return (factrial[n] * inverse[r] * inverse[n - r]) % m
    for k in range(1, n + 2):
        all_comb = mod_combination(n + 1, k, M) % M
        duplication = mod_combination(l + n - r, k - 1, M) % M
        print(all_comb - duplication)

n = int(input())
l = [int(i) for i in input().split()]
x = [n] + l
D_11(x)

Submission status: Time Limit Exceeded

Solution code:
def D_11(x):
    n = x[0]  # 整数の数
    a = x[1:]  # 数列
    M = pow(10, 9) + 7  # 求めた解の剰余をこれで取る

    # aの中から重複した要素のインデックス(それぞれl,rとする)を求める
    import collections
    freq = collections.Counter(a).most_common(1)  # 最も多く出てきた数(入力の制約より、頻度は2となる)
    index = [i for i, x in enumerate(a) if x == freq[0][0]]  # 重複した数のインデックスを取得
    l, r = index[0] + 1, index[1] + 1  # +1するのは数列が1スタートのため

    # 組み合わせの計算
    def power(x, n, m):
        # 冪乗(powだと時間がかかりすぎるため)+剰余つき
        y = 1
        while n > 0:
            if n % 2 == 0:
                x = (x * x) % m
                n = n // 2
            else:
                y = (y * x) % m
                n -= 1
        return y

    def mod_combination(n, r, m):
        if r > n:
            return 0
        factrial = [1] * (n + 1)
        inverse = [1] * (n + 1)
        for i in range(1, n + 1, 1):
            factrial[i] = (factrial[i - 1] * i) % m
            inverse[i] = power(factrial[i], m - 2, m)  # フェルマーの小定理からの帰結
        return (factrial[n] * inverse[r] * inverse[n - r]) % m

    for k in range(1, n + 2, 1):
        all_comb = mod_combination(n + 1, k, M)
        duplication = mod_combination(l + n - r, k - 1, M)
        print(all_comb - duplication)

n = int(input())
l = [int(i) for i in input().split()]
x = [n] + l
D_11(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
a = input().split()

t = set()
x, v = [(i, v) for i, v in enumerate(a) if v in t or t.add(v)][0]
y = a.index(v)
r = N - x + y

def mod(x):
    return x % (10 ** 9 + 7)

def combi(a, b):
    if a < b:
        return 0
    x, y = 1, 1
    for i in range(b):
        x = x * (a - i)
        y = y * (1 + i)
    return mod(x // y)

for k in range(1, N+2):
    print(mod(combi(N+1, k) - combi(r, k-1)))

Submission status: Time Limit Exceeded

Solution code:
n=input()
s=raw_input().split()
maxn=1000000007
p=[]
a=[0 for i in range(n+2)]
def cal(l):
    p=1
    k=1
    while k<=l:
        p=p*k
        k=k+1
    return p
pointer2=-1
for i in range(1,n+2):
    if s[i-1] in p:
        pointer2=i
    p.append(s[i-1])
    a[i]=int((cal(n+1)/cal(i)/cal(n+1-i))%maxn)
pointer=s.index(s[pointer2-1])+1
for left in range(pointer):
    for right in range(pointer2,len(s)+1):
        #print left,right-pointer2
        t1=max(int(cal(pointer)/cal(left)/cal(pointer+1-left))%maxn,1)
        t2=max(int(cal(len(s)-pointer2)/cal(len(s)-right)/cal(right-pointer2)%maxn),1)
        #print left+right-pointer2+1,t1,t2
        a[left+right-pointer2+1]-=t1*t2
for i in range(1,len(a)):
    print a[i]