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: Accepted

Solution code:
import collections

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 #出力の制限
K = 2*(10**5)
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, K + 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())
print(n)
nCk=n
R=list()
L=list(map(int,input().split()))
c = collections.Counter(L)
nikai=c.most_common()[0][0]#2回出てくる数
for i in range(n+1):
  if L[i]==nikai:
    R.append(i)
#Rに二個のindがある。それぞれR[0]こ、N-R[1]
k=n-R[1]+R[0]
for i in range(1,n):
  nCk=cmb(n+1,i+1,mod)
  a = cmb(k,i,mod)
  print((nCk-a)%mod)
print(1)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


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


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))

# rstrip().decode('utf-8')
def main():
	
	n=II()
	A=LI()
	m=10**9+7
	
	x=sum(A)-n*(n+1)//2
	#print(x)
	l=A.index(x)
	r=A.index(x,l+1)
	#print(l,r)
	lr=l+n-r
	
	C=[1]
	D=[1]
	
	for i in range(1,n+2):
		C.append((C[-1]*(n+2-i)*pow(i,m-2,m))%m)
	
	for i in range(1,n+2):
		if i>lr:
			D.append(0)
		else:
			D.append((D[-1]*(lr+1-i)*pow(i,m-2,m))%m)
	
	#print(C,D)
	
	
	
	for i in range(1,n+2):
		print((C[i]-D[i-1])%m)
	
	
	
	

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
def examC():
    ans = 0
    print(ans)
    return

def examD():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    N = I()
    A = LI()
    D = {}
    l = -1; r = -1
    for i,a in enumerate(A):
        if a in D:
            l = D[a]
            r = i
            break
        D[a] = i
    #print(l,r)
    C = combination(N+2,mod)
    ans = [0]*(N+1)
    for i in range(1,N+2):
        ans[i-1] = (C.comb(N+1,i) - C.comb(l+N-r,i-1) + mod) % mod

    for v in ans:
        print(v)
    return

def examE():
    N, M = LI()
    A = LI()
    S = [0]*(M+2)
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        S[a0+1] += 1
        S[a1] -= 1
        if a1<a0:
            S[0] += 1
    #print(S)
    for i in range(M):
        S[i+1] += S[i]
    for i in range(M+1):
        if S[i]<0:
            S[i] = 0
    D = defaultdict(int)
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        cost = (a1 + M - a0) % M - 1
        D[a1] += cost
    start = 0
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        cost = min(a1, (a1+M-a0)%M)
        start += cost
    #print(S)
    #print(D)
    #print(start)
    cost = start
    ans = start
    for i in range(1,M):
        cost += (D[i] - S[i])
        #print(cost)
        if ans>cost:
            ans = cost
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
SIZE=10**5+10; MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    fac[i] = fac[i-1]*i%MOD
finv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(SIZE-1,0,-1):
    finv[i-1] = finv[i]*i%MOD
    inv[i] = finv[i]*fac[i-1]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

r = [-1]*(n+1)
for i,ai in enumerate(a):
    if r[ai]==-1:
        r[ai] = i
    else:
        p = r[ai]
        q = i
        break


for i in range(1,n+2):
    ans = choose(n+1,i)
    ans -= choose(p+n-q,i-1)
    print(ans%MOD)

Submission status: Accepted

Solution code:
from collections import Counter
import numpy as np

N = 10 ** 6
Nsq = 10 ** 3
mod = 10 ** 9 + 7

fac = np.arange(N, dtype=np.int64).reshape(Nsq, Nsq)
fac[0, 0] = 1
for i in range(1, Nsq):
    fac[:, i] *= fac[:, i - 1]
    fac[:, i] %= mod
for i in range(1, Nsq):
    fac[i] *= fac[i - 1, -1]
    fac[i] %= mod
fac = fac.ravel()

finv = np.arange(1, N + 1, dtype=np.int64)[::-1].reshape(Nsq, Nsq)
finv[0, 0] = pow(int(fac[N - 1]), mod - 2, mod)
for i in range(1, Nsq):
    finv[:, i] *= finv[:, i - 1]
    finv[:, i] %= mod
for i in range(1, Nsq):
    finv[i] *= finv[i - 1, -1]
    finv[i] %= mod
finv = finv.ravel()[::-1]


def nCr(a, b):
    if b > a:
        return 0
    else:
        comb = fac[a] * finv[b] % mod * finv[a - b] % mod
        return comb


n = int(input())
A = list(map(int, input().split()))
C = Counter(A)

ind = 0
for i, x in enumerate(A):
    if C[x] > 1:
        ind = i - ind

for i in range(1, n + 2):
    res = nCr(n + 1, i) - nCr(n - ind, i - 1)
    res %= mod
    print(res)

Submission status: Accepted

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

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 1 * 10**5 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

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

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ind = [-1] * (1+n)
for i,ai in enumerate(a,1):
    if(ind[ai]==-1):
        ind[ai] = i
    else:
        left = ind[ai]
        right = i
        break

ans = [0] * (n+2)
for k in range(1,n+2):
    cnt = com(n+1,k)
    if(n -(right-left) >= k-1 ):
        cnt -= com(n-(right-left),k-1)
    ans[k] = cnt%mod

print('\n'.join(map(str,ans[1:])))

Submission status: Accepted

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

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 1 * 10**5 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

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

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ind = [-1] * (1+n)
for i,ai in enumerate(a,1):
    if(ind[ai]==-1):
        ind[ai] = i
    else:
        left = ind[ai]
        right = i
        break

ans = [0] * (n+2)
for k in range(1,n+2):
    cnt = com(n-1,k) + com(n-1,k-1)*2 - com(n - (right-left),k-1)
    if(k >= 2):
        cnt += com(n-1,k-2)
    ans[k] = cnt%mod

print('\n'.join(map(str,ans[1:])))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import defaultdict
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    A = list(map(int, readline().split()))

    d = defaultdict(list)
    for i in range(N+1):
        d[A[i]].append(i)

    for i in range(1,N+1):
        if len(d[i]) == 2:
            left, right = d[i]
            break

    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]

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

    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

    for k in range(1,N+2):
        ans = cmb(N+1,k,MOD) - cmb(left-1+N-right+1,k-1,MOD)
        print(ans%MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

n = I()
a = LI()
mod = 10**9+7

from collections import defaultdict

d = defaultdict(list)

for i in range(n+1):
    d[a[i]].append(i)

for i in range(1,n+1):
    if len(d[i]) == 2:
        b,c = d[i]  # 重複する数字があるindex

kaijou = [1]  # kaijou[i] = i!
for i in range(1,n+2):
    kaijou.append((kaijou[-1]*i) % mod)

def comb(m,i):  # comb(m,i) = m_C_i
    if m < i:
        return 0
    else:
        return (kaijou[m]*pow(kaijou[i],mod-2,mod)*pow(kaijou[m-i],mod-2,mod)) % mod

for i in range(1,n+2):
    print((comb(n+1,i)-comb(n-c+b,i-1)) % mod)

Submission status: Accepted

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

def make_array_for_comb(N, mod=10**9+7):
    fact = [1,1]
    fact_inv = [1,1]
    inv = [0,1]
    for i in range(2, N+1):
        fact.append((fact[-1]*i) % mod)
        # モジュラ逆数の性質
        inv.append((-inv[mod%i] * (mod//i)) % mod)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

fact, fact_inv = make_array_for_comb(n+1,mod)
c = Counter(a)
k = c.most_common()[0][0]
t = 0
for i,ai in enumerate(a):
  if ai == k:
    if t == 0:
      L = i
    elif t == 1:
      R = n-i
      break
    t += 1
    
print(n)
for i in range(1,n+1):
  print((comb(n+1,i+1,mod)-comb(L+R,i,mod))%mod)

Submission status: Accepted

Solution code:
N = int(input())
A = tuple(map(int, input().split()))

MOD = 10 ** 9 + 7
MAX = 10 ** 5 + 10
modinv = lambda a, mod=MOD: pow(a, mod - 2, mod)
fac, inv = [1] * MAX, [1] * MAX
for i in range(1, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = modinv(fac[i])


def comb(n, k, error=0):
    if not 0 <= k <= n:
        return error
    return fac[n] * inv[k] * inv[n - k] % MOD


d_tmp = {}
for i, a in enumerate(A):
    if a in d_tmp:
        double = a
        lr_sections_len = d_tmp[a] + N - i
        break
    else:
        d_tmp[a] = i

for k in range(1, N + 2):
    print((comb(N + 1, k) - comb(lr_sections_len, k - 1)) % MOD)

Submission status: Accepted

Solution code:
#!python3

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

# input
N = int(input())
A = LI()

MOD = 10 ** 9 + 7
MAX = 10 ** 5 + 5
fac, finv, inv = [None] * MAX, [None] * MAX, [None] * MAX


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


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


def main():
    comb_init()
    d = {i: [] for i in range(1, N + 1)}
    x, y = [None] * 2
    for i in range(N + 1):
        d[A[i]].append(i)
        if len(d[A[i]]) == 2:
            x, y = d[A[i]]
            break
    
    for i in range(1, N + 2):
        ans = comb(N + 1, i)
        ans -= comb(N + x - y, i - 1)
        ans %= MOD
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

c = Counter(a)
twice_num = c.most_common(1)[0][0]

left_cnt = 0
right_cnt = 0
state = 0
for i in a:
    if i == twice_num and state == 0:
        state = 1
        continue
    if i == twice_num and state == 1:
        state = 2
        continue

    if state == 0:
        left_cnt += 1
    if state == 2:
        right_cnt += 1


#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 = n+2 #必要な数
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 )


for i in range(1,n+2):
    print((cmb(n+1,i,mod) - cmb(left_cnt + right_cnt,i-1,mod))%mod)

Submission status: Accepted

Solution code:
from collections import Counter

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

MOD = 10 ** 9 + 7

# 逆元を利用してcomb(nCk)をO(1)計算
# https://qiita.com/ophhdn/items/5622ac22cce8fc9432bf
n = nn + 3
fac = [1] * (n + 1) 
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = (fac[j - 1] * j) % MOD

inv[n] = pow(fac[n], MOD-2, MOD)
for j in range(n - 1, -1, -1):
    inv[j] = (inv[j + 1] * (j + 1)) % MOD

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

duple = Counter(A).most_common()[0][0]

l = A.index(duple)
r = A.index(duple, l+1)

outer = nn - (r - l)

for i in range(1, nn + 2):
  print((comb(nn + 1, i) - comb(outer, i - 1)) % MOD)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int, input().split()))
B=sorted(A)
for i in range(n+1):
  if B[i]!=i+1:
    a=i
    break
d=[i for i, x in enumerate(A) if x==a]
x=d[0]
y=d[1]

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+10
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)

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

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int, input().split()))
B=sorted(A)
for i in range(n+1):
  if B[i]!=i+1:
    a=i
    break
d=[i for i, x in enumerate(A) if x==a]
x=d[0]
y=d[1]

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+10
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)

for i in range(1,n+2):
  ans=cmb(n+1,i,mod)-cmb(x+(n-y),i-1,mod)
  if ans<0:
    print(mod+ans)
  else:
    print(ans)

Submission status: Accepted

Solution code:
nmax = 10**6
mod = 10**9+7

fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        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 ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod

ncr_pre()
n = int(input())
A = list(map(int,input().split()))
co = [0]*(n+2)
id2 = -1
for i in  range(n+1):
    a = A[i]
    co[a]+=1
    if co[a]==2:
        id2 = i
        break
id1 = A.index(a)
d = n-id2 +id1

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

Submission status: Accepted

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

MOD = 10**9+7
 
MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
 
def nCr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD




idxs = [[] for _ in range(N)]
for i,a in enumerate(A):
    idxs[a-1].append(i)

for i in range(N):
    if len(idxs[i]) == 2:
        first = idxs[i][0]
        second = idxs[i][1]
        break

for i in range(1, N+2):
    if i == 1:
        print(N)
    elif i == N+1:
        print(1)

    else:
        a = nCr(N+1, i)
        # firstより左にある数字とsecondより右にある数字からi-1個、firstかsecondを選んで長さiの部分列が作れる場合
        cnt = first + (N-second)
        if cnt >= i-1:
            a -= nCr(cnt, i-1)
            a %= MOD
        
        print(a)

Submission status: Accepted

Solution code:
import copy
def comb(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
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
b=copy.deepcopy(a)
b.sort()
x=0
s=[]
for i in range(1,n+1):
  if b[i-1]==b[i]:
    x=b[i]
for i in range(n+1):
  if a[i]==x:
    s.append(i)
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 )
for k in range(1,n+2):
  print((comb(n+1,k,mod)-comb(n-s[1]+s[0],k-1,mod))%mod)

Submission status: Accepted

Solution code:
#14:00
n = int(input())
n += 1
a = list(map(int,input().split()))
b = []
for i in range(n):
  b.append([a[i],i])
b.sort()
for j in range(n-1):
  if b[j][0] == b[j+1][0]:
    k = b[j+1][1] - b[j][1] - 1
mod = 10 ** 9 + 7
now = [ n-k-2 , 1 , 0 , n , n-k ]
#print(now)
print(sum(now)-2*now[-1])
now = [ (n-k-2)*(n-k-3)//2 , n-k-2 , 1 , n*(n-1)//2 , (n-k)*(n-k-1)//2 ]
#print(now)
print((sum(now)-2*now[-1]) % mod)

def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y

for i in range(3,n+1):
  last = now
  now = [0 for _ in range(5)]
  now[0] = last[0] * (n-k-i-1) * inv(i)
  now[1] = last[1] * (n-k-i)   * inv(i-1)
  now[2] = last[2] * (n-k-i+1) * inv(i-2)
  now[3] = last[3] * (n  -i+1) * inv(i)
  now[4] = last[4] * (n-k-i+1) * inv(i)
  for d in range(5):
    now[d] %= mod
  #print(now)
  print((sum(now)-2*now[-1]) % mod)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
L=[0 for i in range(n+1)]
for i in range(n+1):
    L[a[i]]+=1
#print(L)
D=0
for i in range(1,n+1):
    if L[i]==2:
        D=i
#print(a)
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+10
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 )

P=[0,0,0]
One=0
#print(a)
for i in range(n+1):
    if a[i]==D:
        One+=1
    else:
        P[One]+=1
#print(P)
for i in range(1,n+2):
    print((cmb(n+1,i,mod)-cmb(P[0]+P[2],i-1,mod))%mod)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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


def C(n, m):
    if n < m or m < 0: return 0
    return f[n] * inv[m] * inv[n - m] % mod

n = int(input())
a = list(map(lambda x: int(x) - 1, input().split()))
pos = [[] for _ in range(n)]

for idx, x in enumerate(a):
    pos[x].append(idx)

for _ in pos:
    if len(_) == 2:
        l, r = _

for i in range(1, n + 2):
    print(((C(n + 1, i) - C(n + l - r, i - 1)) % mod + mod) % mod)

Submission status: Accepted

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

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

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

NNN = (2*10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

N, = map(int, input().split())
ps = list(map(int, input().split()))
p2i = dict()
i = 0
for p in ps:
    if p not in p2i:
        i += 1
        p2i[p] = i
        continue
    x = p2i[p]
    break
X = min(x-1, i-1)
Y = min(N-x, N-i)
for i in range(1, N+2):
    print((cmb(N+1, i) - cmb(X+Y, i-1))%mod)

Submission status: Accepted

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
from collections import Counter
MAX = 310000
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
count = sorted(count.items(), key=lambda x: x[1], reverse=True)
# 唯一2回出ている値を取得する
dual = count[0][0]
t = 0
for i in range(len(A)):
    if A[i] == dual:
        if t == 0:
            l = i
        else:
            r = i
        t += 1
for k in range(1, N+2):
    print((COM(N+1, k) - COM(l+N-r, k-1) + MOD) % MOD)
# print(l, r)
# print(A[l], A[r])

Submission status: Accepted

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
MAX = 310000
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
count = sorted(count.items(), key=lambda x: x[1], reverse=True)
# 唯一2回出ている値を取得する
dual = count[0][0]
t = 0
for i in range(len(A)):
    if A[i] == dual:
        if t == 0:
            l = i
        else:
            r = i
        t += 1
for k in range(1, N+2):
    print((COM(N+1, k) - COM(l+N-r, k-1) + MOD) % MOD)
# print(l, r)
# print(A[l], A[r])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import Counter

import numpy as np

MOD = 10 ** 9 + 7

N = int(readline())
A = np.array(read().split(),np.int32)

counter = np.bincount(A)
x = np.argmax(counter)
I,J = np.where(A == x)[0]

L = I
M = J - I - 1
R = N - J

# 長さ k での重複は、(L+R)C(k-1)

def cumprod(A, MOD = MOD):
    L = len(A); Lsq = int(L**.5+1)
    A = np.resize(A, Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        A[:,n] *= A[:,n-1]; A[:,n] %= MOD
    for n in range(1,Lsq):
        A[n] *= A[n-1,-1]; A[n] %= MOD
    return A.ravel()[:L]
def make_fact(U, MOD = MOD):
    x = np.arange(U, dtype = np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact,fact_inv

fact, fact_inv = make_fact(10 ** 5 + 100)

answer = fact[N+1] * fact_inv[:N+2] % MOD * fact_inv[:N+2][::-1] % MOD
LR = L + R
x = fact[LR] * fact_inv[:LR+1] % MOD * fact_inv[:LR+1][::-1] % MOD
answer[1:LR+2] -= x

answer = answer[1:]
answer %= MOD
print('\n'.join(answer.astype(str)))

Submission status: Accepted

Solution code:
N = int(input())
X = [-1] * N
A = [int(a)-1 for a in input().split()]
a, b, c = 0, 0, 0
for i in range(N+1):
    if X[A[i]] >= 0:
        a = X[A[i]]
        b = i - X[A[i]] - 1
        c = N - i
        break
    else:
        X[A[i]] = i

P = 10**9+7
fa = [1]
for i in range(1, N + 10):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, N + 10)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]

def C(i, j):
    if j < 0 or j > i: return 0
    return fa[i] * fainv[j] % P * fainv[i-j] % P

for K in range(1, N+2):
    ans = C(N-1, K)
    ans += C(a+c, K-1) + 2 * (C(a+b+c, K-1) - C(a+c, K-1))
    ans += C(a+b+c, K-2)
    ans %= P
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from collections import deque

class SegTree():
    def __init__(self, n):
        self.value = [0 for i in range(n*2)]

MOD = 10 ** 9 + 7

def getinvmod(n):
    return [pow(i, MOD-2, MOD) for i in range(n+1)]


def main():
    n = getN()
    nums = getList()
    index = [-1 for i in range(n)]

    for i, num in enumerate(nums):
        if index[num - 1] == -1:
            index[num - 1] = i
        else:
            ida = i
            idb = index[num - 1]
            break

    side = n - (ida - idb)

    invmod = getinvmod(n+1)

    # print(invmod)
    #
    # print([(i * iv) % MOD for i, iv in enumerate(invmod)])
    ans = n + 1
    minus = 1
    print((ans - minus)%MOD)
    # print(side, ida, idb,"side")
    for i in range(1, n + 1):
        ans *= (n - i + 1)
        ans *= invmod[i + 1]
        ans %= MOD
        if i <= side:
            minus *= side - i + 1
            minus *= invmod[i]
            minus %= MOD

        else:
            minus = 0

        print((ans - minus) % MOD)
        # print(ans, minus)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10**9+7
n = int(input())
num = [ int(v) for v in input().split() ]

dup = [ None for i in range(n) ]
for i, v in enumerate(num):
    if dup[v-1] == None:
        dup[v-1] = i
    else:
        l, r = dup[v-1], n-i
        break

def all_combination_with_mod(m):
    ret_list = [ 1 for i in range(m+1) ]
    for i in range(m):
        a = ret_list[i] * (m-i) * pow(i+1,mod-2,mod)
        ret_list[i+1] = a % mod
    return ret_list

ans_list = all_combination_with_mod(n+1)[1:]
sub_list = all_combination_with_mod(l+r)


for i in range(l+r+1):
    ans_list[i] -= sub_list[i]
    ans_list[i] %= mod

for i in ans_list:
    print(i)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9+7
fun = [1]*(n+1)
for i in range(1,n+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n+1)
rev[n] = pow(fun[n],mod-2,mod)
for i in range(n-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

l = list(map(int,input().split()))
db = sum(l) - n*(n+1)//2
idx = [i for i in range(n+1) if l[i] == db]
a,b,c = idx[0],idx[1]-idx[0]-1,n-idx[1]
print(n)
for k in range(2,n+2):
  print((nCr(a+b+c,k)+nCr(a+b+c,k-2)+nCr(a+b+c,k-1)*2-nCr(a+c,k-1))%mod)

Submission status: Accepted

Solution code:
n = 10**5+1
mod = 10**9+7
fun = [1]*(n+1)
for i in range(1,n+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n+1)
rev[n] = pow(fun[n],mod-2,mod)
for i in range(n-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

n = int(input())
l = list(map(int,input().split()))
db = sum(l) - n*(n+1)//2
idx = [i for i in range(n+1) if l[i] == db]
a,b,c = idx[0],idx[1]-idx[0]-1,n-idx[1]
print(n)
for k in range(2,n+2):
  print((nCr(a+b+c,k)+nCr(a+b+c,k-2)+nCr(a+b+c,k-1)*2-nCr(a+c,k-1))%mod)