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: Wrong Answer

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 + 1):
        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


main()

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
n = int(input())
a = [int(i) for i in input().split(' ')]

for i in range(1, n+1):
    a.remove(i)

l = a[0]
for i in range(1, n+1):
    print((comb(n, i) - comb(l, i-1)) / (10**9+7))

Submission status: Wrong Answer

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

MOD = 1000000007
import math
def comb(n,r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)


dejavu = []
for i, a_i in enumerate(a):
    if a_i in dejavu:
        k = i+1
    else:
        dejavu.append(a_i)
        
print(k)
print(n)
for i in range(2, n+1):
    if n-k+1 >= i-1:
        print("%d"%((comb(n+1, i) - comb(n-k+1, i-1))%MOD))
    else:
        print("%d"%((comb(n+1, i))%MOD))
print (1)

Submission status: Wrong Answer

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

S = sum(A)
x = int(S - (n * (n + 1) / 2))

a = A.index(x)
A[a] = 0
b = A.index(x)
C = []
c = []

M = n + 1
N = 1

print(M - N)

for i in range(2, n + a - b + 2):
	M = (M * (n + 2 - i) / i) % 1000000007
	N = (N * (n + a - b + 1 - i) / (i - 1)) % 1000000007
	print(int((M - N + 1000000007) % 1000000007))
for i in range(n + a - b + 2, n + 2):
	M = (M * (n + 2 - i) / i) % 1000000007
	print(int(M))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

counter = Counter(src)
dup = counter.most_common(1)[0][0]
a = src.index(dup)
b = a+1 + src[a+1:].index(dup)
arr = src[:a] + src[b+1:]
n2 = len(arr)

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

def pow(a,n):
  ans = 1
  mag = a
  for b in reversed(str(bin(n))):
    if b == 'b': break
    if b == '1':
      ans = mul(ans, mag)
    mag = mul(mag, mag)
  return ans

def inv(a):
  return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,N+2):
  f = mul(fac[n-1], n)
  fac.append(f)
  fac_inv.append(inv(f))

def ncr(n,r):
  return mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])

for i in range(N+1):
    ans = ncr(N+1, i+1)
    if i <= n2:
        ans -= ncr(n2, i)
    print ans

Submission status: Wrong Answer

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) ]
print(flag)

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: Wrong Answer

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


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


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_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 calc_comb(n, k, same_indices):
    mod = 1000000007
    total = mod_binomial(n + 1, k, mod)

    if k == 1:
        return n

    former_c = same_indices[0]
    former_dup = 0
    if not former_c == 0:
        if k > 1:
            former_dup += mod_binomial(former_c, k - 1, mod)
        if k > 2:
            former_dup += mod_binomial(former_c, k - 2, mod)

    latter_c = n - same_indices[1]
    latter_dup = 0
    if not latter_c == 0:
        if k > 1:
            latter_dup += mod_binomial(latter_c, k - 1, mod)
    return (total - former_dup - latter_dup) % mod


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

    si = get_same_indices(a)

    for k in range(n + 1):
        print(calc_comb(n, k + 1, si))


main()

Submission status: Wrong Answer

Solution code:
import itertools
mod = 1000000007
n = int(input())
s = list(map(int,input().split()))
for i in range(n+1):
    print(len(list(itertools.combinations(s,i+1))))

Submission status: Wrong Answer

Solution code:
import itertools

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

for i in range(N+1):
    a.append(len(set(itertools.combinations(s,i+1))))

print(a)

Submission status: Time Limit Exceeded

Solution code:
import typing 
from typing import List
from itertools import count
mod = 1000000007

def getWhereW(n, a):
    Idx = [-1] * n
    for i in range(n+1):
        if Idx[a[i]-1] == -1:
            Idx[a[i]-1] = i
        else:
            return Idx[a[i]-1], i

def combinations(n) -> List[int]:
    Result: List[int] = [1] * (n+1)
    for i in count(1):
        if i > n: break
        Result[i] = Result[i-1] * (n+1-i) // i
    return Result


def main():
    with open(0) as f:
        n, *a = map(int, f.read().split())
    l, r = getWhereW(n, a)
    #ans = comb(n+1,k)-comb(n-r+l,k-1), l-r < 0
    Comb_1: List[int] = combinations(n+1)
    Comb_2: List[int] = combinations(n-r+l)
    for k in count(1):
        if k > n+1: break
        
        if k-1 <= n-r+l:
            ans = Comb_1[k] - Comb_2[k-1]
        else:
            ans = Comb_1[k]
        print(ans%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

for i in range(1, n+2):
  if i == n+1:
    print(1)
  else:
    combos = list(itertools.combinations(a, i))
    print(len(set(combos)))

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
N = 100000

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

d = {}
n1 = 0
n2 = 0
n3 = 0

for i, ai in enumerate(a):
    if ai not in d:
        d[ai] = i
    else:
        n1 = d[ai]
        n2 = i - d[ai] - 1
        n3 = n - i - 1
        break

for i in range(1, n+2):
    ans = 0
    # Xを選ばない
    ans += cmb(n-1, i) # 0
    # Xを2回選ぶ
    ans += cmb(n-1, i-2) # 2
    # Xを1回選ぶ
    ans += cmb(n-1-n2, i-1) # 
    for j in range(1, n2+1):
        ans += 2 * cmb(n2, j) * cmb(n-n2-1, i-j-1) % mod
        ans %= mod
    print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
cnt = Counter(A)
mod = 10**9 + 7

def comb(n,k,p):
    """power_funcを用いて(nCk) mod 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

for key, val in cnt.items():
    if val == 2:
        doubled_num = key
        break

left = None
for i, a in enumerate(A):
    if a == doubled_num:
        if left == None:
            left = i
        else:
            right = i

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

Submission status: Time Limit Exceeded

Solution code:
import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    sn=pk[0]+n-pk[1]
    for i in range(0,n+2):
        if i<n:
            ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
            ans1[i+1]=ans0[i]*2-(sn>=i)*(fact[sn]*ifact[sn-i]*ifact[i] % p)
            ans2[i+2]=ans0[i]
        if i>0:
            print((ans0[i]+ans1[i]+ans2[i]) % p)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i
    sn=pk[0]+n-pk[1]
    for i in range(1,n+2):
        if sn>=i-1:
            print(fact[n+1]*ifact[n+1-i]*ifact[i] % p - \
                  fact[sn]*ifact[sn-i+1]*ifact[i-1] % p)
        else:
            print(fact[n+1]*ifact[n+1-i]*ifact[i] % p)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    for i in range(n):
        ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
        ans1[i+1]=ans0[i]*2
        ans2[i+2]=ans0[i]
    sn=pk[0]+n-pk[1]
    for i in range(sn+1):
        ans1[i+1]-=fact[sn]*ifact[sn-i]*ifact[i] % p
    for i in range(1,n+2):
        print((ans0[i]+ans1[i]+ans2[i]) % p)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def memfact(a,m):
    temp = 1
    yield temp
    for i in range(1,a+1):
        temp = temp * i % m
        yield temp
def comb(n,r,m):
    if r == 0: return 1
    return (memf[n]*pow(memf[r],m-2,m)*pow(memf[n-r],m-2,m)) % m


n,*a = map(int, open(0).read().split())
m = 1000000007
checker = set()
for i in range(n+1):
    if a[i] in checker:
        left = a.index(a[i])
        right = n - i
        break
    else:
        checker.add(a[i])
memf = []
mfappend = memf.append
for x in memfact(n+1,m):
    mfappend(x)
for i in range(1,n+2):
    ans = comb(n+1,i,m)
    for j in range(max(0,i-right-1),min(left,i-1)+1):
        ans = (ans-comb(left,j,m)*comb(right,i-j-1,m)) % m
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))

    dup = 0
    for i in range(1, n + 2):
        if a.count(i) == 2:
            dup = i

    first = a.index(dup)
    second = a[first + 1:].index(dup) + first + 1

    print(n)

    p = first
    q = (n + 1) - second - 1

    c1 = n + 1
    c2 = 1

    for i in range(2, n + 2):
        c1 *= (n + 1 - (i - 1))
        c1 %= MOD
        c1 *= pow(i, MOD - 2, MOD)
        c1 %= MOD
        c2 *= (p + q - (i - 2))
        c2 %= MOD
        c2 *= pow(i - 1, MOD - 2, MOD)
        c2 %= MOD
        print((c1 - c2) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=pow(10,9)+7
def cmb(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
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1]
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 )
# 二つあるやつはどの場所にあるか検索
f=[-1]*(n+1)
l,r=0,0
for i in range(n):
  ai=a[i]
  if f[ai]==-1:
    f[ai]=i
  else:
    l=f[ai]
    r=n-i
    break
for k in range(1,n+2):
  a=cmb(n+1,k,mod)
  for i in range(k+1):
    a-=cmb(l,i,mod)*cmb(r,k-i-1,mod)
  print(a)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

def nCr(N,a,mod):
    if a == 0:return 1
    num = reduce(lambda x,y:x * y % mod,range(N,N-a,-1))
    den = reduce(lambda x,y:x * y % mod,range(1,a+1))
    return num * pow(den,mod-2,mod)%mod

def nHr(n,a,mod):
    return nCr(n-1+a,n-1,mod)

mod = 10 ** 9 + 7

n = int(input())
lis = list(map(int,input().split()))
li = [-1] * n

for i in range(n+1):
    if li[lis[i]-1] != -1:
        left = li[lis[i]-1]+1
        right = i+1
        break
    else:li[lis[i]-1] = i

for k in range(1,n+2):
  #     print(nCr(n+1,k,mod),nCr(left+n-right,k-1,mod))
    print(nCr(n+1,k,mod)-nCr(left+n-right,k-1,mod))

Submission status: Time Limit Exceeded

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

MOD = 1000000007
frac = [1] * (n+2)
for i in range(n+1):
  frac[i+1] = frac[i] * (i+1) % MOD
  
invf = [1] * (n+2)
invf[-1] = pow(frac[-1], MOD-2, MOD)
for i in range(n+1):
  invf[n-i] = invf[n-i+1] * (n-i+1) % MOD

fracn1 = frac[n+1]
bubuns = [fracn1*invf[i]*invf[n+1-i]%MOD for i in range(n+2)]

counts = [0]*(n+2)
for ai in a:
  counts[ai] += 1
for i in range(n+2):
  if counts[i] == 2:
    target = i
    break
l = -1
r = -1
for i in range(n+2):
  if a[i] == target:
    if l == -1:
      l = i
    else:
      r = i
      break 
bubuns[1] -= 1
if l >= 1:
  for li in range(2, l+2):
    now = frac[l] * invf[li-1] * invf[l-li+1] % MOD
    bubuns[li] = (bubuns[li] - now) % MOD
if r+1 <= n:
  for ri in range(2, (n-r)+2):
    now = frac[n-r] * invf[ri-1] * invf[n+1-r-ri] % MOD
    bubuns[ri] = (bubuns[ri] - now) % MOD

if (l>=1) and (r+1<=n):
  for lri in range(3, 1+l+(n-r)+1):
    for j in range(1, min(l+1, lri-1)):
      nowl = frac[l] * invf[j] * invf[l-j] % MOD
      nowr = frac[n-r] * invf[lri-1-j] * invf[n-r-lri+1+j] % MOD
      bubuns[lri] = (bubuns[lri] - nowl*nowr) % MOD

for i in range(1, n+2):
  print(bubuns[i])

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, p):
	if (r<0) or (n<r):
		return 0
	r=min(r, n-r)
	return fact[n]*factinv[r]*factinv[n-r]%p

p=10**9+7
N=10**6
fact=[1,1]
factinv=[1,1]
inv=[0,1]

for i in range(2, N+1):
	fact.append((fact[-1]*i)%p)
	inv.append((-inv[p%i]*(p//i)%p))
	factinv.append((factinv[-1]*inv[-1])%p)


N=int(input())
A=list(map(int,input().split()))
index=[[] for _ in range(N+1)]

for i in range(N+1):
    index[A[i]].append(i)

for i in range(1,N+1):
    if len(index[i])==2:
        dup=i

mod=10**9+7
n=index[dup][0]
m=N-index[dup][1]
l=n+m
for k in range(1,N+2):
    if k==1:
        print(N)
        continue   
    
    ans=cmb(N+1,k,mod)
    if l>=k-1:
        for i in range(k):
            ans-=cmb(n,i,mod)*cmb(m,k-1-i,mod)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def exteuc(a, b):
    # ax + by = gcd(a, b)
    if b == 0:
        return 1, 0, a
    y, x, v = exteuc(b, a % b)
    y -= (a//b) * x
    return x, y, v


def modinv(a, mod):
    x, _, _ = exteuc(a, mod)
    return x % mod


def comb(n, k, mod, precalc_modinvs):
    if k > n//2:
        return comb(n, n - k, mod, precalc_modinvs)
    ret = 1
    for i in range(k):
        ret *= n - i
        ret *= precalc_modinvs[k - i]
        ret %= mod
    return ret


def main():
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # calculate mod inverse
    precalc_modinvs = [modinv(i, MOD) for i in range(N + 2)]
    # calculate duplicate indices
    # Ex. [1, 4, 2, 1, 3] -> 0, 3
    dup_first_index, dup_second_index = -1, -1
    indices = [-1 for _ in range(N)]
    for i, a in enumerate(A):
        if indices[a - 1] != -1:
            dup_first_index, dup_second_index = indices[a - 1], i
            break
        indices[a - 1] = i
    # calculate answer
    ans = [0 for _ in range(N + 1)]
    for i in range(N + 1):
        ans[i] = comb(N + 1, i + 1, MOD, precalc_modinvs)
        # Ex. [1, 4, 2, 5, 4, 3, 6] -> [1] + [3, 6] -> 3
        s = dup_first_index + N - dup_second_index
        if s >= i:
            ans[i] -= comb(s, i, MOD, precalc_modinvs)
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def exteuc(a, b):
    # ax + by = gcd(a, b)
    if b == 0:
        return 1, 0, a
    y, x, v = exteuc(b, a % b)
    y -= (a//b) * x
    return x, y, v


def modinv(a, mod):
    x, _, _ = exteuc(a, mod)
    return x % mod


def comb(n, k, mod):
    if k > n//2:
        return comb(n, n - k, mod)
    ret = 1
    for i in range(k):
        ret *= n - i
        ret *= modinv(k - i, mod)
        ret %= mod
    return ret


def main():
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # calculate duplicate indices
    # Ex. [1, 4, 2, 1, 3] -> 0, 3
    dup_first_index, dup_second_index = -1, -1
    indices = [-1 for _ in range(N)]
    for i, a in enumerate(A):
        if indices[a - 1] != -1:
            dup_first_index, dup_second_index = indices[a - 1], i
            break
        indices[a - 1] = i
    # calculate answer
    ans = [0 for _ in range(N + 1)]
    for i in range(N + 1):
        ans[i] = comb(N + 1, i + 1, MOD)
        # Ex. [1, 4, 2, 5, 4, 3, 6] -> [1] + [3, 6] -> 3
        s = dup_first_index + N - dup_second_index
        if s >= i:
            ans[i] -= comb(s, i, MOD)
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
n= int(input())
a= list(map(int,input().split()))
check = [0]*(n+1)
g1=[1,1]
g2=[1,1]
inverse=[0,1]
for i in range(2,n+1+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)
def cmb2(n,r):
    mod = 1000000007
    if (r<0 or r>n ):return 0
    r = min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%mod
r=-1
jn=-1
for i in range(n+1):
    check[a[i]-1]+=1
    if check[a[i]-1]==2:
        jn,r=a[i],i
        break
l=a.index(jn)
s = min(l,n-r)
t = max(l,n-r)
print(n)

for p in range(2,n+1):
    w2=cmb2(n+1,p)
    x=p-t-1
    y=s
    yobun=0
    for k in range(max(p-t-1,0),s+1):
      if p-t-1<=k<=s:
        yobun+=cmb2(s,k)*cmb2(t,p-k-1)
    print(((w2+mod)-yobun) % mod)

print(1)

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k):
  p=1000000007
  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,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":res=(res*a) %p
  return res

n= int(input())
a= list(map(int,input().split()))
check= [0]*(n+1)
r=jn=-1
for i in range(n+1):
    check[a[i]-1]+=1
    if check[a[i]-1]==2:
        jn,r= a[i],i
        break
st=a.index(jn)+n-r
for k in range(1,n+2):print(comb(n+1,k)-comb(st,k-1) if st>=k-1 else comb(n+1,k))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
M = 10 ** 9 + 7


cache = {}

# Combination under a prime modulo: nCk % p
def combmod(n, k, p=M):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    if (n, k) in cache:
        return cache[n, k]
    num, den = 1, 1
    for i in range(k):
        num = num * (n - i) % p
        den = den * (i + 1) % p
    # By Fermat's little theorem,
    # a^(p-1) ≡ 1 mod p
    # i.e. a^(p-2) ≡ a^(-1) mod p
    inv_dev = pow(den, p - 2, p)
    res = num * inv_dev % p
    cache[n, k] = res
    return res


n = int(input())
a = list(map(int, input().split()))
assert len(a) == n + 1

b = [None] * (n + 1)
d1, d2 = -1, -1
for i in range(n + 1):
    if b[a[i]] is None:
        b[a[i]] = i
    else:
        d1 = b[a[i]]
        d2 = i
        break
assert d1 >= 0 and d2 >= 0 and a[d1] == a[d2]


def comb(n, k):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    if k == 0:
        return 1
    if k == 1:
        return n
    if (n, k) in cache:
        return cache[n, k]
    res = combmod(n - 1, k) + combmod(n - 1, k - 1)
    cache[n, k] = res
    return res


for k in range(1, n + 2):
    ans = comb(n + 1, k) - comb(n - d2 + d1, k - 1)
    print(ans % M)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
M = 10 ** 9 + 7


cache = {}
n = int(input())
a = list(map(int, input().split()))
assert len(a) == n + 1

b = [None] * (n + 1)
d1, d2 = -1, -1
for i in range(n + 1):
    if b[a[i]] is None:
        b[a[i]] = i
    else:
        d1 = b[a[i]]
        d2 = i
        break
assert d1 >= 0 and d2 >= 0 and a[d1] == a[d2]


def comb(n, k):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    if k == 0:
        return 1
    if k == 1:
        return n
    if (n, k) in cache:
        return cache[n, k]
    res = comb(n - 1, k) + comb(n - 1, k - 1)
    cache[n, k] = res
    return res


for k in range(1, n + 2):
    ans = comb(n + 1, k) - comb(n - d2 + d1, k - 1)
    print(ans % M)

Submission status: Time Limit Exceeded

Solution code:
M = 10 ** 9 + 7


cache = {}

# Combination under a prime modulo: nCk % p
def combmod(n, k, p=M):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    if (n, k) in cache:
        return cache[n, k]
    num, den = 1, 1
    for i in range(k):
        num = num * (n - i) % p
        den = den * (i + 1) % p
    # By Fermat's little theorem,
    # a^(p-1) ≡ 1 mod p
    # i.e. a^(p-2) ≡ a^(-1) mod p
    inv_dev = pow(den, p - 2, p)
    res = num * inv_dev % p
    cache[n, k] = res
    return res


n = int(input())
a = list(map(int, input().split()))
assert len(a) == n + 1

b = [None] * (n + 1)
d1, d2 = -1, -1
for i in range(n + 1):
    if b[a[i]] is None:
        b[a[i]] = i
    else:
        d1 = b[a[i]]
        d2 = i
        break
assert d1 >= 0 and d2 >= 0 and a[d1] == a[d2]

for w in range(1, n + 2):
    ans = combmod(n + 1, w) - combmod(n - d2 + d1, w - 1)
    print(ans % M)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

MOD = 1000000007
fact = []

def main():
    init_fact(200000)
    n = int(input())
    a = list(map(int, input().split()))
    sa = sorted(a)
    for i in range(n):
        if sa[i] == sa[i + 1]:
            double = sa[i]
            break
    idouble = []
    for i in range(n + 1):
        if a[i] == double:
            idouble.append(i)
    l = idouble[0]
    r = n - idouble[1]
    for k in range(1, n + 2):
        res = combi(n + 1, k) - combi(l + r, k - 1)
        res %= MOD
        print(res)

def combi(n, k):
    if k > n:
        return 0
    elif k == n:
        return 1
    numera = fact[n]
    denomi = (fact[n - k] * fact[k]) % MOD
    return (numera * inv(denomi)) % MOD

def init_fact(maxn):
    assert len(fact) == 0
    fact.append(1)
    for i in range(1, maxn + 1):
        fact.append((fact[i - 1] * i) % MOD)

def inv(n):
    return pow(n, MOD - 2)

def pow(n, p):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(n, p // 2)
        return (x * x) % MOD
    else:
        x = pow(n, p - 1)
        return (x * n) % MOD

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
id=0
frac=[1]*(10**5+10)
p=10**9+7
c=collections.Counter(a)
id=c.most_common()[0][0]
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
N=n+1
short=N-(max(buf)-min(buf))

#print(short,N)

for i in range(1,n+2,1):
    if short-i<0:
        sub1=0
    else:
        sub1 = (((frac[short] * modinv(frac[i], p)) % p) * modinv(frac[short - i], p)) % p

    if short-i-1<0:
        sub2=0
    else:
        sub2 = (((frac[short - 1] * modinv(frac[i], p)) % p) * modinv(frac[short - i - 1], p)) % p
    all=(((frac[N]*modinv(frac[i],p))%p)*modinv(frac[N-i],p))%p

    #print(all,sub1,sub2)
    print(((all-sub1)%p+sub2)%p)

Submission status: Time Limit Exceeded

Solution code:
import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
l=[0]*n
id=0
frac=[1]*(10**5+10)
p=10**9+7
c=collections.Counter(a)
id=c.most_common()[0][0]
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
N=n+1
short=N-(max(buf)-min(buf))

#print(short,N)

for i in range(1,n+2,1):
    if short-i<0:
        sub1=0
    else:
        sub1 = (((frac[short] * modinv(frac[i], p)) % p) * modinv(frac[short - i], p)) % p

    if short-i-1<0:
        sub2=0
    else:
        sub2 = (((frac[short - 1] * modinv(frac[i], p)) % p) * modinv(frac[short - i - 1], p)) % p
    all=(((frac[N]*modinv(frac[i],p))%p)*modinv(frac[N-i],p))%p

    #print(all,sub1,sub2)
    print(((all-sub1)%p+sub2)%p)

Submission status: Time Limit Exceeded

Solution code:
import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
l=[0 for _ in range(n)]
id=0
frac=[1 for _ in range(10**5+10)]
p=10**9+7
c=collections.Counter(a)
id=c.most_common()[0][0]
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
N=n+1
short=N-(max(buf)-min(buf))

#print(short,N)

for i in range(1,n+2,1):
    if short-i<0:
        sub1=0
    else:
        sub1 = (((frac[short] * modinv(frac[i], p)) % p) * modinv(frac[short - i], p)) % p

    if short-i-1<0:
        sub2=0
    else:
        sub2 = (((frac[short - 1] * modinv(frac[i], p)) % p) * modinv(frac[short - i - 1], p)) % p
    all=(((frac[N]*modinv(frac[i],p))%p)*modinv(frac[N-i],p))%p

    #print(all,sub1,sub2)
    print(((all-sub1)%p+sub2)%p)

Submission status: Time Limit Exceeded

Solution code:
import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
l=[0 for _ in range(n)]
id=0
frac=[1 for _ in range(10**5+10)]
p=10**9+7
c=collections.Counter(a)
id=c.most_common()[0][0]
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
short=(n+1)-(max(buf)-min(buf))
N=n+1
#print(short,N)

for i in range(1,n+2,1):
    all=(frac[N]*modinv(frac[i],p)*modinv(frac[N-i],p))%p
    sub1=(frac[short]*modinv(frac[i],p)*modinv(frac[short-i],p))%p
    sub2=(frac[short-1]*modinv(frac[i],p)*modinv(frac[short-i-1],p))%p
    if short-i<0:
        sub1=0
    if short-i-1<0:
        sub2=0
    #print(all,sub1,sub2)
    print(((all-sub1)%p+sub2)%p)