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:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    n = II()
    a = ILI()
    return n, a


def nCr(n, r):
    if r == 0:
        ret = 1
    elif n >= r:
        ret = math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
    else:
        ret = 0
    return ret


def solve(n, a):
    d_check = collections.defaultdict(int)
    ind_double = None
    for ind, ele in enumerate(a):
        if ele in d_check:
            ind_double = (d_check[ele], ind)
            break
        else:
            d_check[ele] = ind

    len_left = ind_double[0]
    len_right = n - ind_double[1]

    ans = [n]
    combs_all = [n + 1]
    combs_double = [1]

    for i in range(2, n + 2):
        comb_all = combs_all[i - 2] * (n + 1 - i + 1) // i
        comb_double = combs_double[i - 2] * (len_left + len_right - i + 2) // (i - 1)
        _ans = comb_all - comb_double
        ans.append(_ans % MOD)
        combs_all.append(comb_all)
        combs_double.append(comb_double)

    ans = "\n".join(map(str, ans))
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    n = II()
    a = ILI()
    return n, a


def nCr(n, r):
    try:
        ret = math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
    except:
        ret = 0
    return ret


def solve(n, a):
    d_check = collections.defaultdict(int)
    ind_double = None
    for ind, ele in enumerate(a):
        if ele in d_check:
            ind_double = (d_check[ele], ind)
            break
        else:
            d_check[ele] = ind

    len_left = ind_double[0]
    len_right = n - ind_double[1]

    ans = []
    for i in range(1, n + 2):
        if i == 1:
            ans.append(n)
        elif i == n + 1:
            ans.append(1)
        else:
            combs = nCr(n + 1, i) - nCr(len_left + len_right, i - 1)
            ans.append(combs % MOD)

    return ans


def main():
    params = read()
    ans = solve(*params)
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    n = II()
    a = ILI()
    return n, a

d_comb = collections.defaultdict(int)

def nCr(n, r):
    global d_comb
    if n < 0 or r < 0 or n < r:
        return 0
    elif n == 0 or r == 0:
        return 1

    if (n - 1, r - 1) in d_comb:
        left = d_comb[(n - 1, r - 1)]
    else:
        left = nCr(n - 1, r - 1)
        d_comb[(n - 1, r - 1)] = left


    if (n - 1, r) in d_comb:
        right = d_comb[(n - 1, r)]
    else:
        right = nCr(n - 1, r)
        d_comb[(n - 1, r)] = right

    return left + right


def solve(n, a):
    d_check = collections.defaultdict(int)
    ind_double = None
    for ind, ele in enumerate(a):
        if ele in d_check:
            ind_double = (d_check[ele], ind)
            break
        else:
            d_check[ele] = ind

    len_left = ind_double[0]
    len_right = n - ind_double[1]

    ans = []
    for i in range(1, n + 2):
        if i == 1:
            ans.append(n)
        elif i == n + 1:
            ans.append(1)
        else:
            combs = nCr(n + 1, i) - nCr(len_left + len_right, i - 1)
            ans.append(combs % MOD)

    return ans


def main():
    params = read()
    ans = solve(*params)
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,*A=map(int,open(0).read().split())
f=[1]*(n+2);r=f[:]
MOD=10**9+7
for i in range(n+1):f[i+1]=e=f[i]*-~i%MOD;r[i+1]=pow(e,MOD-2,MOD)
for i in range(1,n+1):
    try:
        L=A.index(i);R=A.index(i,L+1)
        for k in range(1,n+2):
            print((f[n+1]*r[k]*r[n+1-k]-(k<=L+n+1-R and f[L-1+n+1-R]*r[k-1]*r[L+n+1-k-R]))%MOD)
    except:...

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
seq = input().split()
lc = 'a'
already = []
for idx,c in enumerate(seq):
    if c in already:
        break
    already.append(c)
    lc = c

left = seq.index(c)
right = list(reversed(seq)).index(c)
middle = n-left-right-2
# print(left,middle,right,lc)
# print(seq)
NUM = 10**9+7

# def f(n):
#     if n<=1:
#         return 1
#     else:
#         return n*f(n-1)
#
from math import factorial
def f(n,k):
    if n<k:
        return 1
    else:
        return n*f(n-1,k)


def c(n,k):
    if k == 1:
        return n
    if k == n:
        return 1
    # return f(n)//(f(k) * f(n-k))
    return f(n,max(k,n-k)+1)//f(min(k,n-k),1)

# from itertools import combinations as combi
# def c(n,k):
#     return len(list(combi(range(n),k)))

def calc(n,k):
    if k == 1:
        return n-1
    if k == n:
        return 1
    # if k == n-1:
    #     return c(n,k) - 1
    # if k == 2:
    #     return c(n,k) - lidx - (n-ridx)
    # if k == 3:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,1)
    # if k == 4:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,2) - c(lidx,2) * c(n-ridx,1)
    if k-1 > left+right:
        return c(n,k)
    else:
        return c(n,k) - c(left+right, k-1)


for k in range(1,n+1 +1):
    print(int(calc(n+1,k))%NUM)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
d = {}
for i, a in enumerate(A):
    if a in d:
        save = (d[a], i + 1)
    else:
        d[a] = i + 1

MOD = int(1e9) + 7


def mul_mod(a, b):
    return (a % MOD) * (b % MOD) % MOD


def power_mod(a, b):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_mod(a, b // 2)
        return d * d % MOD
    return a * power_mod(a, b - 1) % MOD


def fact_mod(N):
    fact = []
    for i in range(N + 1):
        if i == 0:
            fact.append(1)
        else:
            fact.append(fact[-1] * i % MOD)
    return fact


def comb_mod(n, r, fact):
    res = fact[n]
    a = power_mod(fact[n - r], MOD - 2)
    b = power_mod(fact[r], MOD - 2)
    res = mul_mod(res, a)
    res = mul_mod(res, b)
    return res


fact = fact_mod(N + 1)


for i in range(N):
    a = comb_mod(N + 1, i + 1, fact)
    if save[0] - 1 + N + 1 - save[1] >= i:
        b = comb_mod(save[0] - 1 + N + 1 - save[1], i, fact)
    else:
        b = 0
    # print(a, b)
    print((a - b) % MOD)

print(1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
seq = input().split()
lc = 'a'
already = []
for idx,c in enumerate(seq):
    if c in already:
        break
    already.append(c)
    lc = c

left = seq.index(c)
right = list(reversed(seq)).index(c)
middle = n-left-right-2
# print(left,middle,right,lc)
# print(seq)
NUM = 10**9+7

def f(n):
    if n<=1:
        return 1
    else:
        return n*f(n-1)

from math import factorial
f = factorial

def c(n,k):
    if k == 1:
        return n
    if k == n:
        return 1
    return (f(n)/(f(k) * f(n-k))%NUM)

def calc(n,k):
    if k == 1:
        return n-1
    if k == n:
        return 1
    # if k == n-1:
    #     return c(n,k) - 1
    # if k == 2:
    #     return c(n,k) - lidx - (n-ridx)
    # if k == 3:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,1)
    # if k == 4:
    #     return c(n,k) - c(lidx,1) * c(n-ridx,2) - c(lidx,2) * c(n-ridx,1)
    if k-1 > left+right:
        return c(n,k)
    else:
        return c(n,k) - c(left+right, k-1)


for k in range(1,n+1 +1):
    print(int(calc(n+1,k))%NUM)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
d = {}
for i, a in enumerate(A):
    if a in d:
        save = (d[a], i + 1)
    else:
        d[a] = i + 1

MOD = int(1e9) + 7


def get_combs(N, last):
    ret = []
    for i in range(last):
        if i == 0:
            ret.append(1)
        else:
            tmp = ret[-1] * (N - i + 1) // i
            ret.append(tmp)
    return ret


L = get_combs(N + 1, N + 1)
M = get_combs(save[0] - 1 + N + 1 - save[1], N + 1)

for i in range(N):
    print((L[i + 1] - M[i]) % MOD)
print(1)

Submission status: Time Limit Exceeded

Solution code:
import functools
import operator


def __nCr(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    numer = functools.reduce(operator.mul, range(n, n - r, -1))
    denom = functools.reduce(operator.mul, range(1, r + 1))
    return numer // denom

MOD = 1000000007
n = int(input())
a = list(map(int, input().split()))
pos = [-1 for _ in range(n + 1)]
for i in range(n + 1):
    if pos[a[i]] > -1:
        l, r = pos[a[i]], i
    else:
        pos[a[i]] = i

# print(l, r)

ans = []
ans.append(str(n))
for k in range(2, n + 1):
    ttl = __nCr(n + 1, k)
    if l + (n - r) >= k - 1:
        subx = __nCr(l + n - r, k - 1)
        ttl -= subx
    ans.append(str(ttl % MOD))
ans.append(str(1))
print('\n'.join(ans))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
l = 0
for i in range(1,n+1):
	if A.count(i) > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
				if len(p) > 1:
					break
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)%mod
	t %= mod
	t *= pow(k+1,mod-2,mod)
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)%mod
		d %= mod
		d *= pow(k,mod-2,mod)
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
for i in range(1,n+1):
	l = 0
	if A.count(i) > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
				if len(p) > 1:
					break
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)%mod
	t %= mod
	t *= pow(k+1,mod-2,mod)
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)%mod
		d %= mod
		d *= pow(k,mod-2,mod)
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
n = int(raw_input())
d = {}
for i, ai in enumerate(int(_) for _ in raw_input().split()):
    if ai in d:
        stt = d[ai]
        end = i
        break
    d[ai] = i
del d, i, ai

frid = {}
n21 = n // 2 + 1
q = 1
for i in xrange(1, n21 + 1):
    q = q * i % MOD
frid[n21] = pow(q, MOD - 2, MOD)
for j in xrange(n21 - 1, -1, -1):
    frid[j] = frid[j + 1] * (j + 1) % MOD


def ncr(n, r):
    if r * 2 > n:
        return ncr(n, n - r)
    p = 1
    for i in xrange(n - r + 1, n + 1):
        p = p * i % MOD
    return (p * frid[r]) % MOD


l = stt
r = n - end

for k in xrange(1, n + 2):
    a = ncr(n + 1, k) % MOD
    if l + r >= k - 1:
        a -= ncr(l + r, k - 1) % MOD
    print a % MOD

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
for i in range(1,n+1):
	l = 0
	if A.count(i) > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)%mod
	t %= mod
	t *= pow(k+1,mod-2,mod)
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)%mod
		d %= mod
		d *= pow(k,mod-2,mod)
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)

Submission status: Time Limit Exceeded

Solution code:
import functools
import operator


def __nCr(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    numer = functools.reduce(operator.mul, range(n, n - r, -1))
    denom = functools.reduce(operator.mul, range(1, r + 1))
    return numer // denom

MOD = 1000000007
n = int(input())
a = list(map(int, input().split()))
pos = [-1 for _ in range(n + 1)]
for i in range(n + 1):
    if pos[a[i]] > -1:
        l, r = pos[a[i]], i
    else:
        pos[a[i]] = i

# print(l, r)

ans = []
ans.append(str(n))
for k in range(2, n + 1):
    ttl = __nCr(n + 1, k)
    if l >= k - 1:
        subl = __nCr(l, k - 1)
        # print(k, 'subl', subl)
        ttl -= subl
    if (n - r) >= k - 1:
        subr = __nCr(n - r, k - 1)
        # print(k, 'subr', subr)
        ttl -= subr
    if l + (n - r) >= k - 1 and k >= 3:
        subx = 0
        bl = max(1, k - (n - r) - 1)
        br = min(l + 1, k)
        for b in range(bl, br):
            subx += __nCr(l, b) * __nCr(n - r, (k - b - 1))
        # subx = l * (n - r) * __nCr(l + (n - r) - 2, k - 3)
        # print(k, 'subx', subx)
        ttl -= subx
    ans.append(str(ttl % MOD))
ans.append(str(1))
print('\n'.join(ans))

Submission status: Time Limit Exceeded

Solution code:
import math

red = 10 ** 9 + 7
def nCr(n, r):
    f = math.factorial
    return f(n) // f(r) // f(n - r)

red = 10 ** 9 + 7
n = int(input())
rev = [None] * (n + 1)
xs = [int(i) for i in input().split()]
dup = []
for i in range(n + 1):
    x = xs[i]
    if rev[x] is not None:
        dup.append(x)
        dup.append(rev[x])
        dup.append(i)
        dup.append(i - rev[x] - 1)
        break
    else:
        rev[x] = i
# print(dup)
for i in range(1, n + 2):
    if i == 1:
        print(n)
    elif i == n + 1:
        print(1)
    else:
        ret = 0
        # no dup
        if n - 1 >= i:
            ret += nCr(n - 1, i)
            #print("#", nCr(n - 1, i))
        # both selected
        if i >= 2:
            ret += nCr(n - 1, i - 2)
            #print("##", nCr(n - 1, i - 2))
        ret += 2 * nCr(n - 1, i - 1)
        if n - dup[3] - 1 - (i - 1) >= 0:
            #ret += nCr(n - 1, i - 1)
            ret -= nCr(n - dup[3] - 1, i - 1)
            #print("###", nCr(n - 1, i - 1), nCr(n - dup[3] - 1, i - 1))
        print(ret % red)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
for i in range(1,n+1):
	l = 0
	if A.count(i) > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	#t *= (n+1-k)%mod*pow(k+1,mod-2,mod)
	t *= (n+1-k)%mod*(k+1)**(mod-2)%mod
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		#d *= (n+p[0]-p[1]-k+1)%mod*pow(k,mod-2,mod)
		d *= (n+p[0]-p[1]-k+1)%mod*(k)**(mod-2)%mod
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

def nCr(n, r):
    f = math.factorial
    return f(n) // (f(r) * f(n - r))

red = 10 ** 9 + 7
n = int(input())
rev = [None] * (n + 1)
xs = [int(i) for i in input().split()]
dup = []
for i in range(n + 1):
    x = xs[i]
    if rev[x] is not None:
        dup.append(x)
        dup.append(rev[x])
        dup.append(i)
        dup.append(i - rev[x] - 1)
        break
    else:
        rev[x] = i
# print(dup)
for i in range(1, n + 2):
    if i == 1:
        print(n)
    elif i == n + 1:
        print(1)
    else:
        ret = 0
        # no dup
        if n - 1 >= i:
            ret += nCr(n - 1, i)
            #print("#", nCr(n - 1, i))
        # both selected
        if i >= 2:
            ret += nCr(n - 1, i - 2)
            #print("##", nCr(n - 1, i - 2))
        ret += 2 * nCr(n - 1, i - 1)
        if n - dup[3] - 1 - (i - 1) >= 0:
            #ret += nCr(n - 1, i - 1)
            ret -= nCr(n - dup[3] - 1, i - 1)
            #print("###", nCr(n - 1, i - 1), nCr(n - dup[3] - 1, i - 1))
        print(ret % red)

Submission status: Time Limit Exceeded

Solution code:
def comb(n, r):
  if r > n:
    return 0
  ret = 1
  for i in range(n, n-r, -1):
    ret *= i
  for i in range(1, r+1):
    ret //= i
  return ret

mod = 1000000007

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

b = [-1] * (n+1)
x = y = 0
for i in range(n+1):
  if b[a[i]] != -1:
    x = b[a[i]]
    y = i
    break
  b[a[i]] = i

for i in range(1, n+2):
  ans = (comb(n+1, i) - comb(n+x-y, i-1)) % mod
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import functools
import operator


def __nCr(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    numer = functools.reduce(operator.mul, range(n, n - r, -1))
    denom = functools.reduce(operator.mul, range(1, r + 1))
    return numer // denom

MOD = 1000000007
n = int(input())
a = list(map(int, input().split()))
pos = [-1 for _ in range(n + 1)]
for i in range(n + 1):
    if pos[a[i]] > -1:
        l, r = pos[a[i]], i
    else:
        pos[a[i]] = i

# print(l, r)

ans = []
ans.append(str(n))
for k in range(2, n + 1):
    ttl = __nCr(n + 1, k)
    if l >= k - 1:
        subl = __nCr(l, k - 1)
        # print(k, 'subl', subl)
        ttl -= subl
    if (n - r) >= k - 1:
        subr = __nCr(n - r, k - 1)
        # print(k, 'subr', subr)
        ttl -= subr
    if l + (n - r) >= k - 1 and k >= 3:
        subx = 0
        for b in range(1, k - 1):
            # print('b', b, 'l', l, 'n - r', n - r, 'k - b', k - b)
            if l >= b and n - r >= k - b - 1:
                subx += __nCr(l, b) * __nCr(n - r, (k - b - 1))
        # subx = l * (n - r) * __nCr(l + (n - r) - 2, k - 3)
        # print(k, 'subx', subx)
        ttl -= subx
    ans.append(str(ttl % MOD))
ans.append(str(1))
print('\n'.join(ans))

Submission status: Time Limit Exceeded

Solution code:
n=int(raw_input())
aa=map(int,raw_input().split())
m={}
p=0
for i,a in enumerate(aa):
    if a not in m:
        m[a] = i
    else:
        p = m[a] + (n - i)
        break
b=n+1
c=1
for i in range(n+1):
    print (b-c)%1000000007
    b = b*(n-i)/(i+2)
    if i <= p:
        c = c * (p-i)/(i+1)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
for i in range(1,n+1):
	l = 0
	if A.count(i) > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)%mod*pow(k+1,mod-2,mod)
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)%mod*pow(k,mod-2,mod)
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
for i in range(1,n+1):
	l = 0
	if A.count(i) > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)%mod*pow(k+1,mod-2,mod)#n+1Ck
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)%mod*pow(k,mod-2,mod)
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    n = II()
    a = ILI()
    return n, a

d_comb = collections.defaultdict(int)

def nCr(n, r):
    global d_comb
    if n < 0 or r < 0 or n < r:
        return 0
    elif n == 0 or r == 0:
        return 1

    if (n - 1, r - 1) in d_comb:
        left = d_comb[(n - 1, r - 1)]
    else:
        left = nCr(n - 1, r - 1)
        d_comb[(n - 1, r - 1)] = left


    if (n - 1, r) in d_comb:
        right = d_comb[(n - 1, r)]
    else:
        right = nCr(n - 1, r)
        d_comb[(n - 1, r)] = right

    return left + right


def solve(n, a):
    d_check = collections.defaultdict(int)
    ind_double = None
    for ind, ele in enumerate(a):
        if ele in d_check:
            ind_double = (d_check[ele], ind)
            break
        else:
            d_check[ele] = ind

    len_left = ind_double[0]
    len_right = n - ind_double[1]

    ans = []
    for i in range(1, n + 2):
        if i == 1:
            ans.append(n)
        elif i == n + 1:
            ans.append(1)
        else:
            comb_0 = nCr(n - 1, i)
            comb_1 = nCr(n - 1, i - 1) * 2 - nCr(len_left + len_right, i - 1)
            comb_2 = nCr(n - 1, i - 2)
            ans.append((comb_0 + comb_1 + comb_2) % MOD)

    return ans


def main():
    params = read()
    ans = solve(*params)
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
for i in range(1,n+1):
	l = 0
	if A.count(i) > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)*pow(k+1,mod-2,mod)#n+1Ck
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)*pow(k,mod-2,mod)
		print((t - d)%mod)
	else:
		print(t%mod)

Submission status: Time Limit Exceeded

Solution code:
def nCk(n,k,mod=10**9+7):
    if n<k or k<0 or n<0:return 0
    return fact[n]/fact[n-k]%mod * pow(fact[k],mod-2,mod) % mod

mod = 10**9+7
n=int(raw_input())
a=map(int,raw_input().split())
cnt=[0]*(n+1)
for i in xrange(n+1):
    cnt[a[i]]+=1
dnum=0
for i in xrange(n+1):
    if cnt[i]==2:
        dnum=i
        break
idx=[]
fact=[0]*(n+5)
fact[0]=1
for i in xrange(n+1):
    fact[i+1] = (i+1)*fact[i]
for i in xrange(n+1):
    if dnum==a[i]:
        idx.append(i)

y=n-idx[1]
x=idx[0]

for i in xrange(n+1):
    #print nCk(y,i)
    print (nCk(n+1, i+1) - nCk(y,i)-x*nCk(y,i-1)%mod)%mod

Submission status: Time Limit Exceeded

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

def k_print(subset):
    length = len(subset) % int(1e9+7)
    print(length)

def k_search(previous_set):
    s = []
    for item in previous_set:
        temp = -1
        for i in item:
            temp += a[temp+1:].index(i) + 1
        else:
            left = set(a[temp+1:])
            exet = [item+[j] for j in left]
            s.extend(exet)
    return s

s = set(a)
s = [[i] for i in s]
k_print(s)

for k in range(n):
    s = k_search(s)
    k_print(s)

Submission status: Time Limit Exceeded

Solution code:
def nCk(n,k,mod=10**9+7):
    if n<k or k<0 or n<0:return 0
    return fact[n]%mod * pow(fact[n-k]*fact[k],mod-2,mod) % mod

mod = 10**9+7
n=int(raw_input())
a=map(int,raw_input().split())
cnt=[0]*(n+1)
for i in xrange(n+1):
    cnt[a[i]]+=1
dnum=0
for i in xrange(n+1):
    if cnt[i]==2:
        dnum=i
        break
idx=[]
fact=[0]*(n+5)
fact[0]=1
for i in xrange(n+1):
    fact[i+1] = (i+1)*fact[i]
for i in xrange(n+1):
    if dnum==a[i]:
        idx.append(i)

y=n-idx[1]
x=idx[0]

for i in xrange(n+1):
    #print nCk(y,i)
    print (nCk(n+1, i+1) - nCk(y,i)-x*nCk(y,i-1))%mod

Submission status: Time Limit Exceeded

Solution code:
M_MAX = 10001
INF   = 1000000007

n=int(input())
duet  = [False for i in range(n)]
duetTemp = [0 for i in range(n)]
duetPlace = [0 for i in range(2)]

def nCr(n,k):
	r=1
	for d in range(1,k+1):
		r*=n
		n-=1
		r=r//d
	return r

	
temp=[int(i)-1 for i in input().split()]
for i in range(n+1):
	if(duet[temp[i]]):
		duetPlace[0]=duetTemp[temp[i]]
		duetPlace[1]=i
	else:
		duet[temp[i]]=True
		duetTemp[temp[i]]=i
	
for k in range(1,n+2):
	ans=nCr(n+1,k)
	ans-=nCr(duetPlace[0]+(n-duetPlace[1]),k-1)
	ans%=INF
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = list(map(int,input().split()))
pos = [0 for _ in range(n+1)]

first = 0
second = 0
for i in range(n+1):
    if(pos[a[i]]):
        first = pos[a[i]]-1
        second = i
    pos[a[i]] = i+1

cnt = n+1
cnt2 = 1

MOD = 1000000007

for i in range(n+1):
    print((cnt-cnt2)%MOD)

    cnt = cnt*(n-i)//(i+2)
    cnt2 = cnt2*(n-second-i+first)//(i+1)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
n = int(raw_input())
d = {}
for i, ai in enumerate(int(_) for _ in raw_input().split()):
    if ai in d:
        stt = d[ai]
        end = i
        break
    d[ai] = i
del d, i, ai


def ncr(n, r):
    if r * 2 > n:
        return ncr(n, n - r)
    p = q = 1
    for i in xrange(n - r + 1, n + 1):
        p = p * i % MOD
    for i in xrange(1, r + 1):
        q = q * i % MOD
    return (p * pow(q, MOD - 2, MOD)) % MOD


l = stt
r = n - end

for k in xrange(1, n + 2):
    a = ncr(n + 1, k) % MOD
    if l + r >= k - 1:
        a -= ncr(l + r, k - 1) % MOD
    print a % MOD

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
n = int(raw_input())
a = [int(_) for _ in raw_input().split()]
d = {}
for i, ai in enumerate(a):
    if ai in d:
        stt = d[ai]
        end = i
        break
    d[ai] = i
del d, i, ai


def ncr(n, r):
    if r * 2 > n:
        return ncr(n, n - r)
    p = q = 1
    for i in xrange(n - r + 1, n + 1):
        p = p * i % MOD
    for i in xrange(1, r + 1):
        q = q * i % MOD
    return (p * pow(q, MOD - 2, MOD)) % MOD


l = stt
r = n - end

for k in xrange(1, n + 2):
    a = ncr(n + 1, k) % MOD
    if l + r >= k - 1:
        a -= ncr(l + r, k - 1) % MOD
    print a % MOD

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
n = int(raw_input())
a = [int(_) for _ in raw_input().split()]
d = {}
for i, ai in enumerate(a):
    if ai in d:
        stt = d[ai]
        end = i
        break
    d[ai] = i
del d, i, ai


def ncr(n, r):
    if r * 2 > n:
        return ncr(n, n - r)
    ans = 1
    for i in xrange(n - r + 1, n + 1):
        ans *= i
    for i in xrange(1, r + 1):
        ans //= i
    return ans


l = stt
r = n - end

for k in xrange(1, n + 2):
    a = ncr(n + 1, k) % MOD
    if l + r >= k - 1:
        s = max(0, k - 1 - r)
        while s <= l and s <= k - 1:
            e = k - 1 - s
            a -= (ncr(l, s) % MOD) * (ncr(r, e) % MOD) % MOD
            s += 1
    print a % MOD

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
xs = [int(c) for c in input().split()]

mod = (10 ** 9) + 7

c = Counter(xs)

for k, v in c.items():
    if v == 2:
        dup = k

dup_idx = [i for i, v in enumerate(xs) if v == dup]

facts = [1]
for i in range(1, n + 3):
    facts.append(facts[-1] * i % mod)

def inv(x):
    return pow(x, mod - 2, mod)

def comb(p, q):
    if (not 0 <= q <= p) or p < 0:
        return 0
    return facts[p] * inv(facts[q]) % mod * inv(facts[p - q]) % mod

tl = n + 1
for l in range(1, n + 2):
    use_no = comb(tl - 2, l)
    use_both = comb(tl - 2, l - 2)
    use_one = comb(tl - 2, l - 1) * 2 - comb(min(dup_idx) + (tl - 1 - max(dup_idx)), l - 1)
    print((use_no + use_both + use_one) % mod)
    # print(use_no,use_both ,use_one)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n_max, MOD=10 ** 9 + 7):
        """
        前処理 = O(n_max + log(MOD))
        :param self.fac[n]: n!
        :param self.facinv[n]: 1/n!
        """
        self.mod = MOD
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % MOD
            fac.append(f)
        f = pow(f, MOD - 2, MOD)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % MOD
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0                    # 範囲外という事はすなわち、そのような場合の数は無いはずなので、0を出力すればよい。（これが無いとREになる）
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

MOD = 10**9 + 7
N = int(input())
C = Combination(N+1)
v = {}
for i, a in enumerate(map(int, input().split()),start=1):
    if v.get(a,0)==0:
        v[a] = i
    else:
        L = i-v[a]
        break
for l in range(1,N+2):
    print((C(N+1,l)-C(N-L,l-1))%MOD)

Submission status: Accepted

Solution code:
from collections import Counter

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

def COMinit():
    """
    逆元テーブルをつくる前処理
    計算量はO(n)
    1 <= k <= n <= 1e7程度
    p: 素数
    """
    fac = [0]*MAX
    finv = [0]*MAX
    inv = [0]*MAX

    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[0], inv[1] = 1, 1
    for i in range(2, MAX):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD
    return fac, finv, inv



def comb(n, k):
    """
    nCk mod MODを求める.
    O(1)
    """
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return int(fac[n] * (finv[k] * finv[n-k] % MOD) % MOD)

fac, finv, inv = COMinit()


counter = dict(Counter(A))
dual = 0 # 重複してる数字
for key, value in counter.items():
    if value == 2:
        dual = key
        break

L = A.index(dual)
R = N - A.index(dual, L+1)

for K in range(1, N+2):
    ans = comb(N+1, K) - comb(L+R, K-1)
    
    print(ans%MOD)