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:
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
for i in range(n+1):
    x=a[i]-1
    l[x]=l[x]+1
for i in range(n):
    if l[i]==2:
        id=i+1
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+sub2)%p)

Submission status: Time Limit Exceeded

Solution code:
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
for i in range(n+1):
    l[a[i]-1]=l[a[i]-1]+1
for i in range(n):
    if l[i]==2:
        id=i+1
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+sub2)%p)

Submission status: Time Limit Exceeded

Solution code:
n= int(input())
a=list(map(int, input().split( )))
if n==1:
    print(1)
    print(1)
    exit()
from collections import Counter
ac = Counter(a)
ex = 0
for i in range(1,n+1):
    if ac[i]==2:
        ex = i 
        break
d1,d2 = -1,-1

for i in range(n):
    if a[i]==ex:
        if d1<0:
            d1=i
        else:
            d2=i
            break
        
c1=0#例外なし
c2=0#左例外使う
c3=0#右例外
c4=0#両方例外
mod = 10**9+7
comb_n = []
deno = 1
nume = 1
for i in range(n-1,-1,-1):
    deno *= i 
    nume *= pow(n-i,mod-2,mod)
    comb_n.append(deno*nume)
comb_n.extend([0,0])
comb_x = []
deno = 1
nume = 1
for i in range(n-(d2-d1),0,-1):
    deno *= i 
    nume *= pow(n-(d2-d1)-i+1,mod-2,mod)
    comb_x.append(deno*nume)
comb_x.extend([0]*n)
print(n)
for k in range(1,n+1):
    c1 = comb_n[k]
    c2 = comb_n[k-1]
    c3 = comb_n[k-1]
    c23= comb_x[k-1]
    c4 = comb_n[k-2]
    if k==1:
        c1+=1
    print((c1+c2+c3-c23+c4)%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 10**9+7
def comb(p,q):
    if p >= q:
        a = math.factorial(p)%mod
        b = math.factorial(q)%mod
        c = math.factorial(p-q)%mod
        return ((a*pow(b*c, mod-2, mod))%mod)
    else:
        return 0
n = int(input())
L = list(map(int,input().split()))
M = []
for i in range(n+1):
    M.append(L[i])
M.sort()
dou = 1 #重複する数
for i in range(n+1):
    if M[i] == dou:
        dou += 1
    else:
        dou = M[i]
        break
l = 0
r = 0
cnt = 0
for i in range(n+1):
    if L[i] == dou and cnt == 0:
        l = i+1
        cnt += 1
    elif L[i] == dou and cnt == 1:
        r = i+1
        break
for i in range(1, n+1):
    print(comb(n+1,i)-comb(l+n-r, i-1))
print(1)

Submission status: Time Limit Exceeded

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

dup=[0]*n
for num in a:
    dup[num-1]+=1
    if dup[num-1]>1:
        break

A=-1
B=-1
for i in range(len(a)):
    if a[i]==num:
        if A==-1:
            A=i
        else:
            B=i
B=n-B
def find_power(n,mod=10**9+7):
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n,mod=10**9+7):
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

mod = 10**9+7
NUM = (10**5)+100
p_lis=find_power(NUM,mod)
ip_lis=find_inv_power(NUM,mod)
def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (p_lis[n]*ip_lis[r]*ip_lis[n-r])%(mod)

print(n)
for k in range(2,n+2):
    base=comb(n+1,k)
    for i in range(k):
        j=k-i-1
        base-= comb(A,i) *comb(B,j)

    print(base)

Submission status: Time Limit Exceeded

Solution code:
# 繰り返し二乗法 (mod 有り)
def mod_rep_pow(a, n, mod=(10 ** 9 + 7)):
    res = 1
    while n > 0:
        if n % 2 == 0:
            a = a ** 2 % mod
            n //= 2
        else:
            res = res * a % mod
            n -= 1
    return (res % mod)


# 繰り返し二乗法 (mod 有り) を利用して nCk を高速に返す
# mod が素数のときのみ利用可能 (フェルマーの小定理を利用しているため)
def mod_comb(n, k, mod=(10 ** 9 + 7)):
    res1 = 1
    for i in range(n, (n - k), -1):
        res1 *= i
        res1 %= mod
    res2 = 1
    for i in range(1, (k + 1)):
        res2 *= i
        res2 %= mod
    return ((res1 * mod_rep_pow(res2, (mod - 2), mod)) % mod)


n = int(input().strip())
a = list(map(int, input().split()))
not_unique = sum(a) - sum([i for i in range(1, n + 1)])
b = []
for i in range(n + 1):
    if a[i] == not_unique:
        b.append(i)
x = n - (b[1] - b[0])
for i in range(1, n + 2):
    print(mod_comb(n + 1, i) - mod_comb(x, (i - 1)))

Submission status: Time Limit Exceeded

Solution code:
# 繰り返し二乗法 (mod 有り)
def mod_rep_pow(a, n, mod=(10 ** 9 + 7)):
    res = 1
    while n > 0:
        if n % 2 == 0:
            a = a ** 2 % mod
            n //= 2
        else:
            res = res * a % mod
            n -= 1
    return (res % mod)


# 繰り返し二乗法 (mod 有り) を利用して nCk を高速に返す
# mod が素数のときのみ利用可能 (フェルマーの小定理を利用しているため)
def mod_comb(n, k, mod=(10 ** 9 + 7)):
    res1 = 1
    for i in range(n, (n - k), -1):
        res1 *= i
        res1 %= mod
    res2 = 1
    for i in range(1, (k + 1)):
        res2 *= i
        res2 %= mod
    return ((res1 * mod_rep_pow(res2, (mod - 2), mod)) % mod)


n = int(input().strip())
a = list(map(int, input().split()))
b = {}
length = -1
for i in range(n + 1):
    if b.get(a[i]) is None:
        b[a[i]] = i
    else:
        length = i - b[a[i]]
        break
x = n - length
for i in range(1, n + 2):
    print(mod_comb(n + 1, i) - mod_comb(x, (i - 1)))

Submission status: Time Limit Exceeded

Solution code:
# 繰り返し二乗法 (mod 有り)
def mod_rep_pow(a, n, mod=(10 ** 9 + 7)):
    res = 1
    while n > 0:
        if n % 2 == 0:
            a = a ** 2 % mod
            n //= 2
        else:
            res = res * a % mod
            n -= 1
    return (res % mod)


# 繰り返し二乗法 (mod 有り) を利用して nCk を高速に返す
# mod が素数のときのみ利用可能 (フェルマーの小定理を利用しているため)
def mod_comb(n, k, mod=(10 ** 9 + 7)):
    res1 = 1
    for i in range(n, (n - k), -1):
        res1 *= i
        res1 %= mod
    res2 = 1
    for i in range(1, (k + 1)):
        res2 *= i
        res2 %= mod
    return ((res1 * mod_rep_pow(res2, (mod - 2), mod)) % mod)


n = int(input().strip())
a = list(map(int, input().split()))
b = {}
length = -1
for i in range(n + 1):
    if a[i] not in b:
        b[a[i]] = i
    else:
        length = i - b[a[i]]
        break
x = n - length
for i in range(1, n + 2):
    print(mod_comb(n + 1, i) - mod_comb(x, (i - 1)))

Submission status: Time Limit Exceeded

Solution code:
# 繰り返し二乗法 (mod 有り)
def mod_rep_pow(a, n, mod=(10 ** 9 + 7)):
    res = 1
    while n > 0:
        if n % 2 == 0:
            a = a ** 2 % mod
            n //= 2
        else:
            res = res * a % mod
            n -= 1
    return (res % mod)


# 繰り返し二乗法 (mod 有り) を利用して nCk を高速に返す
# mod が素数のときのみ利用可能 (フェルマーの小定理を利用しているため)
def mod_comb(n, k, mod=(10 ** 9 + 7)):
    res1 = 1
    for i in range(n, (n - k), -1):
        res1 *= i
        res1 %= mod
    res2 = 1
    for i in range(1, (k + 1)):
        res2 *= i
        res2 %= mod
    return ((res1 * mod_rep_pow(res2, (mod - 2), mod)) % mod)


n = int(input().strip())
a = list(map(int, input().split()))
b = {}
length = -1
for i in range(n + 1):
    if a[i] not in b:
        b[a[i]] = i
    else:
        length = i - b[a[i]]
        break
x = n - length
for i in range(1, n + 2):
    ans = mod_comb(n + 1, i) - mod_comb(x, (i - 1))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ma=0
dic={}
for i in range(m):
    if not a[i] in dic:
        dic[a[i]]=i
    else:
        ma=i-dic[a[i]]-1

for k in range(1,m+1):
    if k==1:
        print(n)
        continue
    ans=0
    ans+=cmb(m-2,k)
    ans+=cmb(m-2,k-2)
    if m-ma-2>=k-1:
        ans+=cmb(m-ma-2,k-1)
    for i in range(1,ma+1):
        if k-1-i>=0 and m-ma-2>=k-1-i:
            ans+=2*cmb(ma,i)*cmb(m-ma-2,k-1-i)
    print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k:return 0
  if n==0 or k==0:return 1
  a=factorial(n)%p
  b=factorial(k)%p
  c=factorial(n-k)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return (d*d)%p
  if b%2==1:
    return (a*power_func(a,b-1,p))%p
import copy
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
b=copy.deepcopy(a)
b.sort()
tmp=-1
for i in range(n):
  if b[i]==b[i+1]:
    tmp=b[i]
r=[]
for i in range(n+1):
  if a[i]==tmp:
    r.append(i)
y=abs(r[1]-r[0]-1)
for k in range(1,n+2):
  ans=(comb(n-1,k,mod)+comb(n-1,k-2,mod)+comb(n-1,k-1,mod)*2-comb(n-1-y,k-1,mod))%mod
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
fac = [1] * (10 ** 5 + 10)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD


def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fac[n] * pow(fac[n - k], MOD - 2, MOD) * pow(fac[k], MOD - 2, MOD) % MOD


n = int(input())
a = list(map(int, input().split()))
d = [-1] * n
for i, x in enumerate(a):
    if d[x - 1] != -1:
        p = d[x - 1]
        q = i
    else:
        d[x - 1] = i
print(n)
for k in range(2, n + 2):
    ans = 0
    ans += comb(n - 1, k - 2)
    ans += comb(n - 1, k - 1) * 2 - comb(p + n - q, k - 1)
    ans += comb(n - 1, k)
    print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

N = 10 ** 5 + 10
fact = [0] * (N)
fact[0] = 1
for i in range(1, N):
    fact[i] = (fact[i-1] * i) % mod

def comb(a, b):
    return moddiv(moddiv(fact[a], fact[a-b]), fact[b])

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

searched = set()
for dup, x in enumerate(a):
    if x in searched:
        break
    else:
        searched.add(x)
first = a.index(a[dup])

for k in range(1, n+2):
    ans = comb(n+1, k)
    if k - 1 <= n - dup + first:
        ans -= comb(n - dup + first, k - 1)
    print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
#abc066d
mod=10**9+7

def com(n,r,m):
 f=[1,1]
 for i in range(2,n+1):
  f.append(f[i-1]*i%m)
 return f[n]*pow(f[r]*f[n-r]%m,m-2,m)%m


N=int(raw_input())
A=map(int,raw_input().split())
c=[-1]*N
for i in range(N+1):
 if c[A[i]-1]!=-1:
  break
 c[A[i]-1]=i
j=c[A[i]-1]
i=N-i
for k in range(1,N+2):
 res=com(N+1,k,mod)
 if k-1<=i+j:
  res-=com(i+j,k-1,mod)
 print res%mod

Submission status: Time Limit Exceeded

Solution code:
#abc066d
mod=10**9+7
def combi(n,r,mod):
 return fact[n]*pow(fact[r],mod-2,mod)*pow(fact[n-r],mod-2,mod)
fact=[1]
for i in range(1,10**6):
 fact.append(i*fact[-1]%mod)

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

N=int(raw_input())
A=map(int,raw_input().split())
c=[-1]*N
for i in range(N+1):
 if c[A[i]-1]!=-1:
  break
 c[A[i]-1]=i
j=c[A[i]-1]
i=N-i
for k in range(1,N+2):
 res=comb(N+1,k,mod)
 if k-1<=i+j:
  res-=comb(i+j,k-1,mod)
 print res%mod

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    a=LI()
    def cmb(n, r, mod):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return (fact[n] * factinv[r] * factinv[n-r])%mod

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]
    
    for i in range(2, N + 5):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
        
    loc=[-1]*N
    mu=[-1,-1]
    for i in range(N+1):
        if loc[a[i]-1]==-1:
            loc[a[i]-1]=i
        else:
            mu[0]=loc[a[i]-1]
            mu[1]=i
    N1=mu[0]
    N2=N-mu[1]
    for i in range(N+1):
        if i==0:
            print(N)
        else:
            temp=0
            for j in range(i+1):
                temp+=cmb(N1,j,mod)*cmb(N2,i-j,mod)
                temp%=mod
                
            print((cmb(N+1,i+1,mod)-temp)%mod)
        
            
    
            
            
        


main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = tuple(map(int, input().split()))
mod = 10 ** 9 + 7

U = N + 10
fact = [1] * (U + 1)
inv = [1] * (U + 1)

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

inv[U] = pow(fact[i], mod - 2, mod)
for i in range(U, 0, -1):
    inv[i - 1] = inv[i] * i % mod


def comb(N, r):
    if r < 0 or r > N:
        return 0
    res = fact[N] * inv[r] % mod
    res = res * inv[N - r] % mod
    return res


X = max(set(A), key=A.count)
left = A.index(X)
right = A[::-1].index(X)
LR = left + right

for i in range(1, N + 2):
    ans = comb(N+1, i)-comb(LR, i-1)
    ans = (ans + mod) % mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    N = int(input())
    A = tuple(map(int, input().split()))
    mod = 10 ** 9 + 7

    X = max(set(A), key=A.count)
    left = A.index(X)
    right = A[::-1].index(X)
    LR = left + right

    comb = Combination(10 ** 5 + 10)
    for i in range(1, N + 2):
        ans = comb(N+1, i)-comb(LR, i-1)
        ans = (ans + mod) % mod
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    N = int(input())
    A = tuple(map(int, input().split()))
    mod = 10 ** 9 + 7

    X = max(set(A), key=A.count)
    left = A.index(X)
    right = A[::-1].index(X)
    LR = left + right

    comb = Combination(10 ** 5 + 10)
    ans = [-1] * (N + 1)
    for i in range(1, N + 2):
        ans[i - 1] = (comb(N + 1, i) - comb(LR, i - 1) + mod) % mod

    print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * \
                modinv[self.mod % i] % self.mod
        return modinv


if __name__ == "__main__":
    N = int(input())
    N += 1
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    comb = Combination(10 ** 5 + 10)
    ans = [comb(N, i) for i in range(1, N + 1)]

    X = max(set(A), key=A.count)
    left = A.index(X)
    right = N - A.index(X, left + 1) - 1
    LR = left + right

    diff = [comb(LR, i) for i in range(LR + 1)]
    for i, d in enumerate(diff):
        ans[i] = (ans[i] - d + mod) % mod

    print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

# とりあえず二項係数を答えにぶち込む
fact = [1]
for i in range(1, N + 2):
    fact.append(fact[-1] * i % mod)


ans = [0] * (N + 2)
fN = fact[N + 1]
for i in range(1, N + 2):
    div = fact[i] * fact[N - i + 1] % mod
    value = fN * pow(div, mod - 2, mod) % mod
    ans[i] = value

# 数列Aの中に2つあるやつx
# xの左側、右側にあるやつをカウントする
x = max(set(A), key=A.count)
left = A.index(x)
right = N - A.index(x, left + 1)
M = left + right

for i in range(0, M + 1):
    num = fact[M]
    div = fact[i] * fact[M - i] % mod
    comb = num * pow(div, mod - 2, mod) % mod
    ans[i + 1] = (ans[i + 1] - comb + mod) % mod

print(*ans[1:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x


fact = [1] * 100100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - n*(n+1)//2

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


'''
fact = [1] * 200100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD
'''


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return math.factorial(n) * modinv(math.factorial(n - r)) * modinv(math.factorial(r)) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - n*(n+1)//2

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


fact = [1] * 200100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - n*(n+1)//2

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


fact = [1] * 100100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) % MOD * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - n*(n+1)//2

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


fact = [1] * 200100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) % MOD * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - sum(i for i in range(1, n + 1))

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


fact = [1] * 200100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) % MOD * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - sum(i for i in range(1, n + 1))

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n - 1, k)
    ans += 2 * comb(n - 1, k - 1)
    if ans >= MOD:
        ans -= MOD
    if ans >= MOD:
        ans -= MOD

    if k >= 2:
        ans += comb(n - 1, k - 2)
        if ans >= MOD:
            ans -= MOD

    ans -= comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


fact = [1] * 200100
for i in range(1, 200100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) % MOD * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - sum(i for i in range(1, n + 1))

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n - 1, k)
    ans += 2*comb(n-1, k-1)
    if k >= 2:
        ans += comb(n - 1, k - 2)
    ans %= MOD

    ans -= comb(l + r, k - 1)
    ans += MOD
    ans %= MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
########   modあり modは素数  ###############
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

mod = 10**9+7 #出力の制限
N = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


n=int(input())
A=list(map(int,input().split()))
v=[-1]*n
for i,a in enumerate(A):
    #print(i,a)
    if v[a-1]!=-1:
        s=v[a-1]
        f=i
    if v[a-1]==-1:
        v[a-1]=i

#print(s,f)
mod=10**9+7
for i in range(1,n+1):
    """sousuu=cmb(n+1,i,mod)
    tyouhuku=cmb(s+n-f,i-1,mod)"""
    if i==1:
        sousuu=n+1
        tyouhuku=1
    else:
        sousuu*=(n+2-i)
        sousuu//=i
        tyouhuku*=(s+n-f+1-i+1)
        tyouhuku//=(i-1)
    #print(sousuu,tyouhuku)
    print((sousuu-tyouhuku)%mod)
print(1)

Submission status: Time Limit Exceeded

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


n=int(input())
A=list(map(int,input().split()))
v=[-1]*n
for i,a in enumerate(A):
    #print(i,a)
    if v[a-1]!=-1:
        s=v[a-1]
        f=i
    if v[a-1]==-1:
        v[a-1]=i

#print(s,f)
mod=10**9+7
for i in range(1,n+1):
    """sousuu=cmb(n+1,i,mod)
    tyouhuku=cmb(s+n-f,i-1,mod)"""
    if i==1:
        sousuu=n+1
        tyouhuku=1
    else:
        sousuu*=(n+2-i)
        sousuu//=i
        tyouhuku*=(s+n-f+1-i+1)
        tyouhuku//=(i-1)
    #print(sousuu,tyouhuku)
    print((sousuu-tyouhuku)%mod)
print(1)

Submission status: Time Limit Exceeded

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


def cmb(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

n=int(input())
A=list(map(int,input().split()))
v=[-1]*n
for i,a in enumerate(A):
    #print(i,a)
    if v[a-1]!=-1:
        s=v[a-1]
        f=i
    if v[a-1]==-1:
        v[a-1]=i

#print(s,f)
mod=10**9+7
for i in range(1,n+1):
    sousuu=cmb(n+1,i,mod)
    tyouhuku=cmb(s+n-f,i-1,mod)
    print(sousuu-tyouhuku)
print(1)