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:
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])
	
	
	
	

if __name__=="__main__":
	main()

Submission status: Wrong Answer

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)

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

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+1 -(right-left) >= k ):
        cnt -= com(n+ -(right-left),k)
    ans[k] = cnt%mod

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

Submission status: Wrong Answer

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+1 -(right-left) >= k ):
        cnt -= com(n+1 -(right-left),k)
    ans[k] = cnt%mod

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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]
mod=10**9+7
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

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

Submission status: Wrong Answer

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):
  print(cmb(n+1,i,mod)-cmb(x+(n-y),i-1,mod))

Submission status: Wrong Answer

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**6
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(x+(n-y),i-1,mod))

Submission status: Wrong Answer

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**6
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(x+(n-y)-1,i-1,mod))

Submission status: Wrong Answer

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+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(x+(n-y),i-1,mod))

Submission status: Wrong Answer

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)
    ans -= ncr(d,k-1)
    print(ans)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
for i in range(1,n+1):
  if b[i-1]==b[i]:
    x=b[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 )
p=[0,0,0]
t=0
for i in range(n+1):
  if a[i]==x:
    t+=1
  else:
    p[t]+=1
for k in range(1,n+2):
  print(comb(n+1,k,mod)-comb(p[0]+p[2],k-1,mod))

Submission status: Wrong Answer

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 = [0 if not i else pow(f[i], mod - 2, mod) for i in range(200000)]


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

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

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))
# print(l, r)
# print(A[l], A[r])

Submission status: Wrong Answer

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-1+N-r, k-1))
# print(l, r)
# print(A[l], A[r])

Submission status: Wrong Answer

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))
# print(l, r)
# print(A[l], A[r])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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:]
print('\n'.join(answer.astype(str)))

Submission status: Wrong Answer

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]

for i in ans_list:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
N = int(input())
a = list(map(int, input().split()))
num = [[] for _ in range(N + 1)]
dnum = 0
mod = 10 ** 9 + 7
for i in range(N + 1):
  num[a[i]].append(i)
  if len(num[a[i]]) == 2:
    dnum = a[i]
class Factorial:
  def __init__(self, n, mod):
    self.f=[1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i=[pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(N + 1, mod)
for i in range(1, N + 2):
  t = f.combi(N + 1, i)
  u = 0
  if num[dnum][0] + (N + 1 - num[dnum][1]) >= i:
    u = f.combi(num[dnum][0] + (N + 1 - num[dnum][1]), i)
    if num[dnum][0] + (N + 1 - num[dnum][1] - 1) >= i:
      u -= f.combi(num[dnum][0] + (N + 1 - num[dnum][1] - 1), i)
  print(t - u)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import collections
import math
def main():
    N = int(input())
    A = list(map(int,input().split()))
    c = collections.Counter(A)
    m = c.most_common()[0][0]
    at_m = []
    pos = 0
    for i in range(N+1):
        if A[i] == m:
            at_m.append(i)
    for i in range(N+1):
        all_ = math.factorial(N+1)//(math.factorial(i+1)*math.factorial(N-i))
        if i <= (at_m[0]+(N-at_m[1])):
            de = math.factorial(at_m[0]+N-at_m[1])//(math.factorial(i)*math.factorial(at_m[0]+N-at_m[1]-i))
            print(all_-de)
        else:
            print(all_)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

def factorials(n,m):
    # 0~n!のリスト
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i%m)

    # 0~n!の逆元のリスト
    g = [1]
    for i in range(n):
        g.append(pow(f[i+1],m-2,m))

    return f,g


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

m = 10**9+7

f,g = factorials(n,m)

counter = Counter(a)

for x in a:
    if counter[x] == 2:
        b = x
        break

l,r = [i for i, x in enumerate(a) if x == b]

if r-l == 1:
    renzoku = True
else:
    renzoku = False

if renzoku:
    print(n)
    for k in range(2,n):
        x = f[n-1]*g[n-k-1]*g[k]
        y = f[n-1]*g[n-k]*g[k-1]
        z = f[n-1]*g[n-k+1]*g[k-2]
        print((x+y+z)%m)
    print(n)
    print(1)
else:
    print(n)
    for k in range(2,n):
        x = f[n-1]*g[n-k-1]*g[k]
        y = f[n-1]*g[n-k]*g[k-1] * 2
        z = f[n-1]*g[n-k+1]*g[k-2]
        if n-r + l >=k-1:
            y -= f[n-r+l]*g[n-r+l-k+1]*g[k-1]
        print((x+y+z)%m)
    print(n+1)
    print(1)

Submission status: Wrong Answer

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


import sys


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
N = n+1
A = list(map(int, input().split()))
MOD = 10**9+7
already = set()
for i, l in enumerate(A):
    if l in already:
        dup_ind = i
        dup_num = l
        break
    else:
        already.add(l)
before_first_dup_num = A.index(dup_num)
after_dup_num = N-dup_ind-1

F = FactMod(n+1, MOD)
for k in range(1, n+2):
    all_pattern = F.comb(N, k)
    rem_pattern = 0
    for first_rem in range(k):
        before_first_rem = F.comb(
            before_first_dup_num, first_rem) if before_first_dup_num >= first_rem else 0
        after_dup_rem = F.comb(
            after_dup_num, k-1-first_rem) if after_dup_num >= k-1-l else 0
        rem_pattern += before_first_rem*after_dup_rem
    print((all_pattern-rem_pattern+MOD) % MOD)

Submission status: Wrong Answer

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


import sys


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
N = n+1
A = list(map(int, input().split()))
MOD = 10**9+7
already = set()
for i, l in enumerate(A):
    if l in already:
        dup_ind = i
        dup_num = l
        break
    else:
        already.add(l)
after_dup_num = N-dup_ind-1

F = FactMod(n+1, MOD)
for k in range(1, n+2):
    all_pattern = F.comb(n+1, k)
    rem_pattern = F.comb(after_dup_num, k-1) if after_dup_num >= k-1 else 0
    print((all_pattern-rem_pattern+MOD) % MOD)

Submission status: Wrong Answer

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


import sys


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7
for i, l in enumerate(A):
    if A.count(l) == 2:
        dup_num = l
        dup_ind = A[i+1:].index(l)+i+1
        break
after_dup_num = n+1-dup_ind-1

F = FactMod(n+1, MOD)
for k in range(1, n+2):
    all_pattern = F.comb(n+1, k)
    rem_pattern = F.comb(after_dup_num, k-1) if after_dup_num >= k-1 else 0
    print((all_pattern-rem_pattern+MOD) % MOD)

Submission status: Wrong Answer

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


import sys


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))
for i, l in enumerate(A):
    if A.count(l) == 2:
        dup_num = l
        dup_ind = A[i+1:].index(l)+i+1
        break
after_dup_num = n+1-dup_ind-1

F = FactMod(n+1, 10**9+7)
for k in range(1, n+2):
    all_pattern = F.comb(n+1, k)
    rem_pattern = F.comb(after_dup_num, k-1) if after_dup_num >= k-1 else 0
    print(all_pattern-rem_pattern)