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 re

n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0
mask = 10**9 + 7

com = [1]*(n+2)

tmp = 1
for i in range(1, n+2):
        tmp *= i % mask
        com[i] = tmp

for i in range(0, n + 1):
        x = a.index(a[i])
        if a[i] in a[x+1:]:
                left = i
                right = a[x+1:].index(a[i]) + x + 1
                break

for i in range(1, n + 2):
        ans = (com[n + 1] / (com[i] * com[n + 1 - i]))
        m = com[i - 1] * com[left + n - right - i + 1]
        x = 0
        if m != 0:
                x = (com[left + n - right] / m)
        print (ans - x) % mask

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import re

def comb(n, k):
        a = [0] * 100
        if (n - k < k):
                k = n - k
        if (k == 0):
                return 1
        if (k == 1):
                return n
        if (k > 100):
                return 0
        for i in range(1, k):
                a[i] = i + 2
        for i in range(3, (n - k + 2)):
                a[0] = i
                for j in range(1, k):
                        a[j] += a[j - 1]
        return a[k - 1]

n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0
mask = 10**9 + 7

for i in range(0, n + 1):
        x = a.index(a[i])
        if a[i] in a[x+1:]:
                left = i
                right = a[x+1:].index(a[i]) + x + 1
                break

for i in range(1, n + 2):
        ans = comb(n + 1, i)
        ans -= comb(left + n - right, i - 1)
        print ans % mask

Submission status: Time Limit Exceeded

Solution code:
import math

def nCm(n, m):
    return fact[n] // (fact[m] * fact[n - m])

def calcFact(i):
    fact.append(fact[i-1]*i)

n = int(input())
l = list(map(int, input().split()))
fact = [1]

tmp = [-1]*n

for i in range(1, n+2):
    calcFact(i)

for i in range(n+1):
    if(tmp[l[i]-1] == -1):
        tmp[l[i]-1] = i
    else:
        j = tmp[l[i]-1]
        k = i
        break

for i in range(1, n+2):
    if(j+n-k < i-1):
        print((nCm(n+1, i)) % 1000000007)
    else:
        print((nCm(n+1, i) - nCm(j+n-k, i-1)) % 1000000007)

Submission status: Time Limit Exceeded

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

fact = [1] * (n + 2)

for i in range(1, n + 2):
    fact[i] = i * fact[i - 1]

def nCm(n, m):
    global fact
    return fact[n] // (fact[m] * (fact[n - m]))

saw = [-1] * n
left = 0
right = 0
for i in range(n):
    if saw[a[i] - 1] == -1:
        saw[a[i] - 1] = i
    else:
        left, right = saw[a[i] - 1], n - i
        break

for i in range(1, n + 2):
    if i == 1:
        print(n)
    elif left + right >= i - 1:
        print((nCm(n + 1, i) - nCm(left + right, i - 1) % 1000000007))
    else:
        print(nCm(n + 1, i) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math

def nCm(n, m):
    return math.factorial(n) // (math.factorial(m) * (math.factorial(n - m)))

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

tmp = [-1]*n

for i in range(n+1):
    if(tmp[l[i]-1] == -1):
        tmp[l[i]-1] = i
    else:
        j = tmp[l[i]-1]
        k = i
        break

for i in range(1, n+2):
    if(j+n-k < i-1):
        print((nCm(n+1, i)) % 1000000007)
    else:
        print((nCm(n+1, i) - nCm(j+n-k, i-1)) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k):
  if k == 0:
    return 1
  if n < k:
    return 0

  ret = 1
  for i in xrange(k):
    ret *= n-i
  for i in xrange(1,k+1):
    ret /= i
  return ret % 1000000007

n = int(raw_input())
a = map(int,raw_input().split())

b = sorted(a)
t = -1
for i in xrange(len(b)-1):
  if b[i] == b[i+1]:
    t = b[i]

L = 0
M = 0
R = 0
c = 0
for i in xrange(len(a)):
  if a[i] == t:
    c += 1
  elif c == 0:
    L += 1
  elif c == 1:
    M += 1
  elif c == 2:
    R += 1

# lc = {}
# rc = {}
# for i in xrange(0,L+1):
#   lc[i] = comb(L,i)
# for i in xrange(0,R+1):
#   rc[i] = comb(R,i)



for k in xrange(1,n+2):
  total = 0
  # for i in xrange(k):
  #   K = k-1
  #   if i not in lc:
  #     lc[i] = 0
  #   if K-i not in rc:
  #     rc[K-i] = 0
  #   # print i,K-i," ",lc[i],rc[K-i],lc[i] * rc[K-i]
  #   total += lc[i] * rc[K-i]
    # total %= 1000000007
  print (comb(n+1,k) - comb(L+R,k-1)) % 1000000007

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k):
  if k == 0:
    return 1
  if n < k:
    return 0

  ret = 1
  for i in xrange(k):
    ret *= n-i
  for i in xrange(1,k+1):
    ret /= i
  return ret % 1000000007

n = int(raw_input())
a = map(int,raw_input().split())

b = sorted(a)
t = -1
for i in xrange(len(b)-1):
  if b[i] == b[i+1]:
    t = b[i]

L = 0
M = 0
R = 0
c = 0
for i in xrange(len(a)):
  if a[i] == t:
    c += 1
  elif c == 0:
    L += 1
  elif c == 1:
    M += 1
  elif c == 2:
    R += 1

lc = {}
rc = {}
for i in xrange(0,L+1):
  lc[i] = comb(L,i)
for i in xrange(0,R+1):
  rc[i] = comb(R,i)



for k in xrange(1,n+2):
  total = 0
  for i in xrange(k):
    K = k-1
    if i not in lc:
      lc[i] = 0
    if K-i not in rc:
      rc[K-i] = 0
    # print i,K-i," ",lc[i],rc[K-i],lc[i] * rc[K-i]
    total += lc[i] * rc[K-i]
    total %= 1000000007
  print comb(n+1,k) - total

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
A = tuple(map(int, input().split()))
mod = 10 ** 9 + 7
n2 =  sum(A) - N * (N + 1) //2
l = A.index(n2)
r = A[l+1:].index(n2) + l + 1

table = [None for _ in range(N + 2)]
table2 = [None for _ in range(N + 2)]

def f(a, n, mod):
    if n == 0:
        return 1
    elif n == 1:
        return a
    else:
        if n % 2 == 0:
            return (f(a, n//2, mod) ** 2) % mod
        else:
            return (f(a, n//2, mod) ** 2 * a) % mod

def comb(n, r):
    if 0 <= r <= n:
        return (table[n] * table2[r] * table2[n-r]) % mod
    return 0

for i in range(N + 2):
    if i == 0:
        table[i] = 1
    else:
        table[i] = i * table[i-1]

for j in range(N + 2):
    if j == 0 :
        table2[N] = f(table[N], mod-2, mod)
    else:
        table2[N-j] = (table2[N-j + 1] * (N-j + 1)) % mod

for k in range(1, N + 1):
    print(comb(N + 1, k) - comb(l + N - r, k - 1))
print(1)

Submission status: Time Limit Exceeded

Solution code:
#11
n = int(input())
a = list(map(int, input().split()))
 
flag = [a.count(a[i])-1 for i in range(n+1) ]
p = flag.index(1) + list(reversed(flag)).index(1)
 
mod = 10**9+7
    
def memoize(f): #メモ化関数
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def easyFact(n):
    if ( n==0 ): 
        return 1
    else: 
        return n*easyFact(n-1)

g = [easyFact(i) for i in range(n+2)]

def combination(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return ( g[n] /( g[r] * g[n-r] ) )
 
 
for i in range(n+1):
    if ( p>=i ):
        c =( combination(n+1, i+1) - combination(p, i) ) % mod
    else:
        c =( combination(n+1, i+1) ) % mod
    print( int(c) )

Submission status: Time Limit Exceeded

Solution code:
#11
n = int(input())
a = list(map(int, input().split()))
 
flag = [a.count(a[i])-1 for i in range(n+1) ]
p = flag.index(1) + list(reversed(flag)).index(1)
 
mod = 10**9+7
    
def memoize(f): #メモ化関数
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def easyFact(n):
    if ( n==0 ): 
        return 1
    else: 
        return n*easyFact(n-1)

g = [easyFact(i) for i in range(n+3)]

def combination(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return ( g[n] /( g[r] * g[n-r] ) )
 
 
for i in range(n+1):
    if ( p>=i ):
        c =( combination(n+1, i+1) - combination(p, i) ) % mod
    else:
        c =( combination(n+1, i+1) ) % mod
    print( int(c) )

Submission status: Time Limit Exceeded

Solution code:
#11
n = int(input())
a = list(map(int, input().split()))
 
flag = [a.count(a[i])-1 for i in range(n+1) ]
p = flag.index(1) + list(reversed(flag)).index(1)
 
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
mod = 10**9 + 7
for i in range( 2, n + 2 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
def combination(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
 
for i in range(n+1):
    if ( p>=i ):
        c = combination(n+1, i+1) - combination(p, i)
    else:
        c = combination(n+1, i+1)
    print( int(c) )

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Here your code !

l=int(input())+1
if l==2:
    print(1)
    print(1)
    exit()
mod = 10**9+7
N = 10**5+2
g1 = [1, 1]  #0! と1!
g2 = [1, 1]  #(0!)^-1 と(1!)^-1
inverse = [0, 1]
data=list(map(int,input().split()))
for i in data:
    if data.count(i)==2:
        x=i
        break
for i in range( 2, N + 1 ):
    #元テーブルは，最後尾の要素にiを乗算したのを加える
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    #逆元テーブルは，最後尾の要素にinverseの最後尾を乗算したのを加える
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
def combination(n,r,mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % mod
 
c1=[1]
l-=1
for i in range(1,l+2):
    c1.append(combination(l+1,i,mod))
t1=data.index(x,2)
t2=data.index(x)
for i in range(1,l+2):
    print(c1[i]-combination(t2+l-t1,i-1,mod))

Submission status: Time Limit Exceeded

Solution code:
import scipy.misc as scm
mod = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

num = [-1] * (n+1)
l = r = -1
for i in range(len(a)):
    if num[a[i]] != -1:
        l, r = num[a[i]], i
        break
    num[a[i]] = i

for k in range(1, len(a)+1):
   print(scm.comb(len(a), k, True) % mod - scm.comb(l+len(a)-r-1, k-1, True) % mod)

Submission status: Time Limit Exceeded

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

flag = [a.count(a[i])-1 for i in range(n+1) ]
p = flag.index(1) + list(reversed(flag)).index(1)

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
mod = 10**9 + 7
for i in range( 2, n + 2 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def combination(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


for i in range(n+1):
    if ( p>=i ):
        c = combination(n+1, i+1) - combination(p, i)
    else:
        c = combination(n+1, i+1)
    print( int(c) )

Submission status: Time Limit Exceeded

Solution code:
import math
f = math.factorial

def comb(n, k):
    return (f(n) % mod)//((f(k) % mod) * (f(n-k) % mod))% mod

mod = 10**9 + 7

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

d = [i for i in range(len(a)) if a.count(a[i]) == 2]

na = d[0]
nb = (n+1) - (d[1] + 1)

tot = 1
for k in range(1, n+2):
    tot = (tot *  ((n+1)-(k-1)) //k) 
    minus = 0
    if (k - 1) <= (na + nb):
        minus = comb((na + nb), (k-1))
    print((tot - minus) % mod)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
M = 10**9 + 7

def calc_index(a):
    t = sorted(a)
    for i, x in enumerate(t[1:]):
        if t[i] == x:
            break
    result = []
    for i, v in enumerate(a):
        if v == x:
            result.append(i)
    return result

f, e = calc_index(a)
out = n - e + f
memo1 = [False for x in range(10**5 + 1)]
def fact1(b):
    if memo1[b] == False:
        memo1[b] = fact(range(2, b + 1))
    return memo1[b]

memo2 = [{} for x in range(10**5 + 1)]
def fact2(a, b):
    if memo2[a].get(b) == None:
        memo2[a][b] = fact(range(a, a - b, -1))
    return memo2[a][b]

def fact(a):
    result = 1
    for i in a:
        result *= i
        if result > M:
            result %= M
    return result

def powmod(a, b):
    if b == 0:
        return 1
    elif b & 1:
        return (powmod(a, b - 1) * a) % M
    else:
        return powmod(a, b // 2)**2 % M

def c(a, b):
    return fact(range(a, a - b, -1)) * powmod(fact(range(2, b + 1)) % M, M - 2) % M

for i in range(1, n + 1):
    c1, c2 = c(n + 1, i), c(out, i - 1)
    r = c1 - c2
    if r < 0:
        r += M
    print(r)
print(1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import scipy.misc as scm

D = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

dict = Counter(a).most_common()
dd = dict[0][0]

indexs = [i for i in range(n+1) if a[i] == dd]
for i in range(1,n+2) :
    print((scm.comb(n+1,i,1) - scm.comb(indexs[0]+(n-indexs[1]), i-1, 1))%D)

Submission status: Time Limit Exceeded

Solution code:

import sys

def get_repeating_indexes(ax):
    elements = [-1] * (len(ax))

    for i, a in enumerate(ax):
        if elements[a] != -1:
            return elements[a], i
        else:
            elements[a] = i


MOD = 10 ** 9 + 7
memo = {}

def nck(a, b):
    if (a, b) in memo:
        return memo[(a,b)]
    elif b > a:
        return 0
    elif a == b or b == 0:
        return 1
    elif a-b < b:
        return nck(a, a-b)
    else:
        up = 1
        for i in range(a, a-b, -1):
            up *= i

        lo = 1
        for i in range(2, b+1):
            lo *= i

        memo[(a, b)] = up / lo % MOD
        return memo[(a, b)]


def main():
    n = int(raw_input())
    ax = [int(x) for x in raw_input().split()]

    i, j = get_repeating_indexes(ax)
    oob = i + (len(ax) - j - 1)

#    import pdb; pdb.set_trace()

    for i in range(1, n+2):
        if i == 1:
            print n
        else:
            print nck(n + 1, i) - nck(oob, i - 1)


if __name__ == "__main__":
    sys.setrecursionlimit(10 ** 5 + 1)
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys

def get_repeating_indexes(ax):
    elements = [-1] * (len(ax))

    for i, a in enumerate(ax):
        if elements[a] != -1:
            return elements[a], i
        else:
            elements[a] = i


MOD = 10 ** 9 + 7
memo = {}

def nck(a, b):
    if (a, b) in memo:
        return memo[(a,b)]
    elif b > a:
        return 0
    elif a == b or b == 0:
        return 1
    elif a-b < b:
        return nck(a, a-b)
    else:
        memo[(a, b)] = (nck(a - 1, b - 1) % MOD + nck(a - 1, b) % MOD) % MOD
        return memo[(a, b)]


def main():
    n = int(raw_input())
    ax = [int(x) for x in raw_input().split()]

    i, j = get_repeating_indexes(ax)
    oob = i + (len(ax) - j - 1)

#    import pdb; pdb.set_trace()

    for i in range(1, n+2):
        if i == 1:
            print n
        else:
            print nck(n + 1, i) - nck(oob, i - 1)


if __name__ == "__main__":
    sys.setrecursionlimit(10 ** 5 + 1)
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import math

n = int(input())
a = [int(x) for x in input().split()]

low = 0
high = 0

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

for i, x in enumerate(a):
	for j in range(i+1,n+1):
		if x == a[j]:
			low = i
			high = j
			break
		else:
			pass

ll = low
hh = n-high
d = ll+hh

for k in range(1,n+2):
	c = nCr(n+1, k)
	if k > d+1:
		m = 0
	else:
		m = nCr(d, k-1)
	print((c-m)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as f
N=int(input())
a=[0 for _ in range(N+1)]
temp=[0 for i in range(N+1)]
l=list(map(int,input().split()))
for i in range(N+1):
    a[i]=l[i]
    temp[l[i]]+=1
    if(temp[l[i]])==2:
        o=i+1
        index=l[i]
p=a.index(index)+1
l=p-1
r=N+1-o
q=l+r
for i in range(1,N+2):
    if(i==N+1):
        print(1)
        continue
    if(i==1):
        print(N)
        continue
    nck=int(f(N+1)/(f(N+1-i)*f(i)))
    try:
        other=int(f(q)/(f(q-(i-1))*f(i-1)))
    except:
        other=0
    print((nck-other)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def f(a, b):
	s = 1
	for i in range(a - b + 1, a + 1):
		s = (s * i / (i - (a - b))) % int(10e8 + 7)
	return s

a = input()
l = map(int, raw_input().split())

d = sum(l) - (1 + a) * a / 2

c = 0

for i in l:
	if i != d:
		c += 1
	else:
		break

for i in reversed(l):
	if i != d:
		c += 1
	else:
		break

t = a + 1
print a
p = 1
s = t
temp = 0


for i in range(2, a + 2):
	t -= 1
	p += 1
	s = (s + temp * int(10e8 + 7)) * t / p
	temp = s / int(10e8 + 7)
	s = s % int(10e8 + 7)
	if i - 1 <= c:
		print s - f(c, i - 1)
	else:
		print s

Submission status: Time Limit Exceeded

Solution code:
def f(a, b):
	s = 1
	for i in range(a - b + 1, a + 1):
		s = (s * i / (i - (a - b))) % int(10e8 + 7)
	return s

a = input()
l = map(int, raw_input().split())

dic = {}
for i in l:
	if i in dic:
		d = i
		break
	else:
		dic[i] = 1

c = 0

for i in l:
	if i != d:
		c += 1
	else:
		break

for i in reversed(l):
	if i != d:
		c += 1
	else:
		break

t = a + 1
print a
p = 1
s = t
temp = 0


for i in range(2, a + 2):
	t -= 1
	p += 1
	s = (s + temp * int(10e8 + 7)) * t / p
	temp = s / int(10e8 + 7)
	s = s % int(10e8 + 7)
	if i - 1 <= c:
		print s - f(c, i - 1)
	else:
		print s

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from math import factorial

def nPk(n, k) :
    return factorial(n)/factorial(n-k)

def combination(n,k) :
    if n < k :
        return 0
    return int(nPk(n,k)/factorial(k))

D = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

dict = Counter(a).most_common()
dd = dict[0][0]

indexs = [i for i in range(n+1) if a[i] == dd]
for i in range(1,n+2) :
    print((combination(n+1,i) - combination(indexs[0]+(n-indexs[1]), i-1))%D)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def combination(a,b):
    c = 1
    for i in range(b):
        c *= a-i
        c /= i+1
    return c

n = input()
a = map(int, raw_input().split())
mod = 10**9+7
acnt =[0]*(n+1)
for i in range(n+1):
    acnt[a[i]] += 1
    if(acnt[a[i]]==2):
        same = a[i]
        break
lr = []
for i in range(n+1):
    if(a[i]==same):
        lr.append(i)
     
left = lr[0]
right = n-lr[1]
print(n)
for i in range(1,n+1):
    c = int(combination(n+1,i+1)%mod)
    plc = int(combination(left+right,i)) if left+right>=i else 0
    ans = (c-plc)%mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
def get_ln_inputs():
    return input().split()


def mod_pow(a, x, p):
    # return a^x mod p
    res = 1
    while x > 0:
        if(x & 1):
            res = (res * a) % p
        a = (a * a) % p;
        x >>= 1;
    return res
 
 
def mod_inverse(a, p):
    return mod_pow(a, p-2, p);
 
 
def mod_binomial(n, k, p):
    numerator = 1;
    for i in range(k):
        numerator = (numerator * (n - i)) % p;
 
    denominator = 1;
    for i in range(k):
        denominator = (denominator * (i + 1)) % p;
 
    res = mod_inverse(denominator, p);
    res = (res * numerator) % p;
    return res;


def get_ln_int_inputs():
    return list(map(int, get_ln_inputs()))


def get_same_indices(arr):
    mem = [-1 for _ in arr]
    for i in range(len(arr)):
        n = arr[i]
        if not mem[n] == -1:
            return (mem[n], i)
        mem[n] = i


def main():
    n = get_ln_int_inputs()[0]
    a = get_ln_int_inputs()

    si = get_same_indices(a)

    former_c = si[0]
    latter_c = n - si[1]
    rem_c = former_c + latter_c
    mod = 1000000007

    for k in range(1, n + 2):
        total = mod_binomial(n + 1, k, mod)

        if k == 1:
            print(n)
            continue

        dup = 0
        if rem_c >= k - 1:
            dup = mod_binomial(rem_c, k - 1, mod)

        ans = (total - dup) % mod
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import math

N = input()
s = map(int, raw_input().split(" "))

sd=list(set(s))
daburi=sum(s)-sum(sd)

o = [ i for i, v in enumerate(s) if v == daburi]

a=[]
out=o[0]+N-o[1]
#print(out)


def nck(n, k):
    return math.factorial(n)/(math.factorial(k)*math.factorial(n-k))

for i in range(out+1):
    a.append(int((nck(N+1,i+1)-nck(out,i))%(7+1e9)))

for i in range(out+1, N+1):
    a.append(int(nck(N+1,i+1)%(7+1e9)))

for i in range(N+1):
    print(a[i])

Submission status: Time Limit Exceeded

Solution code:
import math

div = 10**9+7 
def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1: 
            result = (result * numerator[k]) % div
    return result

n = int(input())
al = input().split()
s = {}
for i,ai in enumerate(al):
    if (ai in s):
        k1 = s[ai]
        k2 = i+1
        break
    else:
        s[ai] = i + 1

for m in range(1,n+2):
    
    if(m == 1):
        res = n%div
    elif((k1 - 1)+(n+1 - k2) >= m - 1):
        res = int((nCr(n+1,m) - nCr((k1 - 1)+(n+1 - k2),m - 1)) % div)
    else:
        res = int(nCr(n+1,m) % div)
    
    print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

n = int(input())
a = input().split()
b = []
c = []
for i in range(n + 2):
    c.append(0)
ex = 10 ** 9
for i in range(1,n + 2):
    for j in combinations(a, i):
        b.append(j)
b = list(set(b))

for i in range(len(b)):
    b[i] = list(b[i])
for i in range(n + 2):
    for j in range(len(b)):
        if len(b[j]) == i:
            c[i] += 1

for i in range(1,n + 2):
    print(int(c[i]) % ex)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
from collections import Counter
n = int(input())
a = list(map(int, input().split()))

b = [key for key,val in Counter(a).items() if val > 1]
c = [i for i, x in enumerate(a) if x == b[0]]
B = c[1] - c[0] - 1
X = n + c[0] - c[1]

for k in range(1,n+2):
	if k <= X+1:
		Y = (factorial(n+1) // (factorial(k) * factorial(n+1-k))) - (factorial(X) // (factorial(k-1) * factorial(X-k+1)))
		print(Y % (pow(10, 9)+7))
	else:
		Y = (factorial(n+1) // (factorial(k) * factorial(n+1-k)))
		print(Y % (pow(10, 9)+7))

Submission status: Time Limit Exceeded

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

import math

flag = [a.count(a[i])-1 for i in range(n+1) ]
for i in range(n+1):
    p = flag.index(1) + list(reversed(flag)).index(1)
    if ( p>=i ):
        c = math.factorial(n+1)/math.factorial(i+1)/math.factorial(n-i) - math.factorial(p)/math.factorial(i)/math.factorial(p-i)
    else:
        c = math.factorial(n+1)/math.factorial(i+1)/math.factorial(n-i)
    print( int(c)%(10**9+7) )

Submission status: Time Limit Exceeded

Solution code:
import math
f = math.factorial

def comb(n, k):
    return (f(n)//(f(k) * f(n-k))) % mod

mod = 10**9 + 7

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

d = [i for i in range(len(a)) if a.count(a[i]) == 2]

na = d[0]
nb = (n+1) - (d[1] + 1)

for k in range(1, n+2):
    tot = comb(n+1, k)
    minus = 0
    if (k - 1) <= (na + nb):
        minus = comb((na + nb), (k-1))
    print((tot - minus) % mod)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
k = 1

b = [key for key,val in Counter(a).items() if val > 1]
c = [i for i, x in enumerate(a) if x == b[0]]
B = c[1] - c[0] - 1
X = n + c[0] - c[1]

while k <= n + 1:
	if k <= X+1:
		Y = (factorial(n+1) // (factorial(k) * factorial(n+1-k))) - (factorial(X) // (factorial(k-1) * factorial(X-k+1)))
		print(Y % (pow(10, 9)+7))
		k += 1
	else:
		Y = (factorial(n+1) // (factorial(k) * factorial(n+1-k)))
		print(Y % (pow(10, 9)+7))
		k += 1

Submission status: Time Limit Exceeded

Solution code:
def f(a, b):
	s = 1
	for i in range(a - b + 1, a + 1):
		s = (s * i / (i - (a - b))) % int(10e8 + 7)
	return s

a = input()
l = map(int, raw_input().split())

dic = {}
for i in l:
	if i in dic:
		d = i
		break
	else:
		dic[i] = 1

c = 0

for i in l:
	if i != d:
		c += 1
	else:
		break

for i in reversed(l):
	if i != d:
		c += 1
	else:
		break

print a
for i in range(2, a + 2):
	if i - 1 <= c:
		result = f(a + 1, i) - f(c, i - 1)
		result = result % int(10e8 + 7)
	else:
		result = f(a + 1, i) % int(10e8 + 7)
	print result

Submission status: Time Limit Exceeded

Solution code:
def f(a, b):
	s = 1
	for i in range(a - b + 1, a + 1):
		s = (s * i / (i - (a - b))) % int(10e8 + 7)
	return s

a = input()
l = map(int, raw_input().split())

d = [x for x in l if l.count(x) > 1][0]
c = 0

for i in l:
	if i != d:
		c += 1
	else:
		break

for i in reversed(l):
	if i != d:
		c += 1
	else:
		break

print a
for i in range(2, a + 2):
	if i - 1 <= c:
		result = f(a + 1, i) - f(c, i - 1)
		result = result % int(10e8 + 7)
	else:
		result = f(a + 1, i) % int(10e8 + 7)
	print result

Submission status: Memory Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

fac = [-1] * (10**7+1)
inv = [-1] * (10**7+1)
finv = [-1] * (10**7+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

def NCMMod(n, k):
    if n < k:
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

initNCMMod(100000)

def main():
    n = I()
    a = LI()
    tmp_set = set()
    e = -1
    i1, i2 = -1, -1
    for i in range(n+1):
        if a[i] in tmp_set:
            i2 = i
            e = a[i]
        tmp_set.add(a[i])
    for i in range(n+1):
        if a[i] == e:
            i1 = i
            break
    left = i1
    middle = i2 - i1 - 1
    right = n + 1 - i2 - 1
    # import pdb
    # pdb.set_trace()
    for k in range(1, n+2):
        if k == 1:
            print(n)
            continue

        cnt = NCMMod(n+1, k)
        r_rem = (n+1 - 1 - k) - middle
        if r_rem >= 0:
            l_rem = r_rem - right
            if l_rem >= 0:
                cnt -= NCMMod(left, l_rem)
            else:
                cnt -= NCMMod(right, r_rem)
        
        l_lem = (n+1 - 1 - k) - middle
        if l_lem >= 0:
            r_rem = l_lem - left
            if r_rem >= 0:
                cnt -= NCMMod(right, r_rem)
            else:
                cnt -= NCMMod(left, l_rem)
        print(cnt)
main()

Submission status: Accepted

Solution code:
# 全部違う要素なら、k個から成る部分列の数は単純に (n+1) C kである
# ここである2つが同じ数であった場合、それに寄って同一視される条件はなにか?
# 同じ数を1つだけ含む かつ 2つの間の数を含まない である。
# 2つの外側にある要素の数をjとすると 、j個の中からk-1個を選ぶから j C (k-1)である。
# j < k-1の場合は、同一視されるものは無いので0と見なせばよい。

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

max_len = n+5  # 適宜変更する
mod = 10**9 + 7

# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))
modinv_table = [-1] * (max_len + 1)
modinv_table[0] = None  # 万が一使っていたときにできるだけ早期に原因特定できるようにしたいので、Noneにしておく。
factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
    factori_table[i] = factori_table[i-1] * (i) % mod

modinv_table[1] = 1
for i in range(2, max_len + 1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod
    factori_inv_table[i] = factori_inv_table[i-1] * modinv_table[i] % mod


def binomial_coefficients(n, k):
    '''
    n! / (k! * (n-k)! )
    0 <= k <= nを満たさないときは変な値を返してしまうので、先にNoneを返すことにする。
    場合によっては0のほうが適切かもしれない。
    '''
    if not 0 <= k <= n:
        return None
    return (factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]) % mod

# 重複要素を探索
appearance = [-1] * (n+1)
for idx, num in enumerate(nums):
    if appearance[num] == -1:
        appearance[num] = idx
    else:
        dup = [appearance[num], idx]
        break

j = n+1 - (dup[1] - dup[0] + 1)

for k in range(1, n+1+1):
    if k-1 > j:
        print(binomial_coefficients(n+1, k))
    else:
        print((binomial_coefficients(n+1, k) - binomial_coefficients(j, k-1)) % mod)