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

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

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

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

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


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

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

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

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

Submission status: Wrong Answer

Solution code:
def cmb(n,k):
    if n < k:
        return 0
    return fac[n]*inv_fac[n-k]*inv_fac[k] % mod
fac = [1]
mod = 10**9+7
n = int(input())
a = list(map(int,input().split()))
for i in range(1,n+2):
    fac.append(fac[-1]*i % mod)
inv_fac = [pow(fac[n+1],mod-2,mod)]
for i in range(1,n+2)[::-1]:
    inv_fac.append(inv_fac[-1]*i % mod)
inv_fac = inv_fac[::-1]
s = set()
num = -1
for i in range(n+1):
    if a[i] in s:
        idx = i
        break
    s.add(a[i])

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

Submission status: Wrong Answer

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

from collections import Counter
C = Counter(A)
for k, v in C.items():
    if v == 2:
        t = k

flag = False
for i in range(n+1):
    if not flag:
        if A[i] == t:
            l = i
            flag = True
    else:
        if A[i] == t:
            r = i

r = n-r

#print(l, r)

N = 10**5+50
fac = [1]*(N+1)
finv = [1]*(N+1)
for i in range(N):
    fac[i+1] = fac[i] * (i+1) % mod
finv[-1] = pow(fac[-1], mod-2, mod)
for i in reversed(range(N)):
    finv[i] = finv[i+1] * (i+1) % mod

def cmb1(n, r, mod):
    if r <0 or r > n:
        return 0
    r = min(r, n-r)
    return fac[n] * finv[r] * finv[n-r] % mod

for k in range(1, n+2):
    ans = cmb1(n+1, k, mod)-cmb1(l+r, k-1, mod)
    print(ans)

Submission status: Wrong Answer

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

MOD = 10 ** 9 + 7

factorials = [1]
fact_invs = [1]
for i in range(1, N+2):
    factorials.append((factorials[-1]*i) % MOD)
    fact_invs.append(pow(factorials[-1], MOD-2, MOD))
fact_invs.append(1)

def combi(n, k):
    if n < k:
        return 0
    ret = factorials[n]
    ret *= fact_invs[k]
    ret %= MOD
    ret *= fact_invs[n-k]
    return ret % MOD

ct = Counter(As)
mc = ct.most_common(1)[0][0]

L = R = None
for i, a in enumerate(As):
    if a == mc:
        if L is None:
            L = i
        else:
            R = N - i

for k in range(1, N+2):
    print(combi(N+1, k) - combi(L+R, k-1))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
comb = nCr(2 * n)
c = Counter(a)
num = c.most_common()[0][0]
l, r = a.index(num), n - list(reversed(a)).index(num)
m = n - (r - l)
print((comb.comb(n + 1, 1) - comb.comb(m, 0) - 1) % mod)
for i in range(2, n + 2):
    print((comb.comb(n + 1, i) - comb.comb(m, i - 1)) % mod)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
comb = nCr(2 * n)
c = Counter(a)
num = c.most_common()[0][0]
l, r = a.index(num) + 1, n - list(reversed(a)).index(num) + 1
for i in range(1, n + 2):
    print(comb.comb(n + 1, i) - comb.comb(n - (r - l) - 1, i - 1))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
comb = nCr(2 * n)
c = Counter(a)
num = c.most_common()[0][0]
l, r = a.index(num) + 1, n - list(reversed(a)).index(num) + 1
print(l, r)
for i in range(1, n + 2):
    print(comb.comb(n + 1, i) - comb.comb(n - (r - l) - 1, i - 1))

Submission status: Wrong Answer

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

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

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


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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


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

if __name__ == '__main__':
    for i, c in enumerate(combinations(10000)):
        print(f'{i}:{c}')

Submission status: Wrong Answer

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

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

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


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import Counter
two=0
a=Counter(A)
for k,v in a.items():
  if v==2:
    two=k
LR=[]
for i in range(N+1):
  if A[i]==two:
    LR.append(i)
L=LR[0]
R=LR[1]
mod=10**9+7
P=[1 for i in range(10**6+1)]
for i in range(10**6):
  P[i+1]=P[i]*(i+1)%mod
L+=1
R+=1
def comb(a,b):
  if a>=b:
    return P[a]*pow(P[a-b],mod-2,mod)*pow(P[b],mod-2,mod)%mod
  else:
    return 0

for i in range(1,N+2):
  print(comb(N+1,i)-comb(N+L-R,i-1))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

cnt=Counter(a)

mod=10**9+7

def modinv(x):
    return pow(x,mod-2,mod)

for k,v in cnt.items():
    if v==1:
        continue

    for i in range(n+1):
        if a[i]==k:
            left=i
            break
    
    for i in range(n,-1,-1):
        if a[i]==k:
            right=n-i
            break
    
    break

allcomb=1
lrcomb=[1]*(n+1)
for i in range(1,n+1):
    lrcomb[i]=(left+right-i+1)*modinv(i)*lrcomb[i-1]
    lrcomb[i]%=mod

for k in range(1,n+2):
    allcomb*=(n-k+2)*modinv(k)
    allcomb%=mod

    if left+right>=k-1:
        print(allcomb-lrcomb[k-1])
    else:
        print(allcomb)

Submission status: Wrong Answer

Solution code:
n, *a = map(int, open(0).read().split())

left = 0
right = 0
val = 0
seen = [False] * (n + 1)
for i in range(n + 1):
    if seen[a[i]]:
        right = i
        val = a[i]
        break
    seen[a[i]] = True
for i in range(n):
    if a[i] == val:
        left = i
        break

mod = 10 ** 9 + 7

fac = [1] * (n + 5)
for i in range(1, n + 3):
    fac[i] = fac[i - 1] * i % mod
def inv(x):
    return pow(x, mod - 2, mod)
def c(n, k):
    if n < k:
        return 0
    return fac[n] * inv(fac[k] * fac[n - k]) % mod

right = n - right
for i in range(1, n + 2):
    print(c(n + 1, i) - c(left  + right, i - 1))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
index=[]
z=[0]*(n+1)
for i in a:
    z[i]+=1

for i in range(n+1):
    if z[i]==2:
        pin=i
        break

for i in range(n+1):
    if a[i]==pin:
        index.append(i)


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

def combinations(n,r):
  if n<r:
      return 0
  xxx=lst[n]
  xxx*=pow(lst[n-r],mod-2,mod)
  xxx%=mod
  xxx*=pow(lst[r],mod-2,mod)
  xxx%=mod

  return xxx

for i in range(1,n+2):
    if i==1:
        print(n)
    elif i==n+1:
        print(1)
    elif i==2:
        print((combinations(n,2)+index[1]-index[0])%mod)



    else:
        ans=combinations(n+1,i)-combinations(n-index[1],i-1)-combinations(index[0],i-1)-combinations(n-index[1]+index[0]-2,i-2)
        if n-index[1]+index[0]+1>=i:
            ans-=1

        ans%=mod
        print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
index=[]
z=[0]*(n+1)
for i in a:
    z[i]+=1

for i in range(n+1):
    if z[i]==2:
        pin=i
        break

for i in range(n+1):
    if a[i]==pin:
        index.append(i)


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

def combinations(n,r):
  if n<r:
      return 0
  xxx=lst[n]
  xxx*=pow(lst[n-r],mod-2,mod)
  xxx%=mod
  xxx*=pow(lst[r],mod-2,mod)
  xxx%=mod

  return xxx

for i in range(1,n+2):
    if i==1:
        print(n)
    elif i==n+1:
        print(1)
    elif i==2:
        print((combinations(n,2)+index[1]-index[0])%mod)
    
    elif i==3:
        ans=combinations(n+1,i)-combinations(n-index[1],i-1)-2
        ans%=mod
        print(ans)
    
    elif i==4:
        ans=combinations(n+1,i)-combinations(n-index[1],i-1)-1
        ans%=mod
        print(ans)


    else:
        ans=combinations(n+1,i)-combinations(n-index[1],i-1)
        ans%=mod
        print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
index=[]
z=[0]*(n+1)
for i in a:
    z[i]+=1

for i in range(n+1):
    if z[i]==2:
        pin=i
        break

for i in range(n+1):
    if a[i]==pin:
        index.append(i)


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

def combinations(n,r):
  xxx=lst[n]
  xxx*=pow(lst[n-r],mod-2,mod)
  xxx%=mod
  xxx*=pow(lst[r],mod-2,mod)
  xxx%=mod

  return xxx

for i in range(1,n+2):
    if i==1:
        print(n)
    elif i==n+1:
        print(1)
    elif i==2:
        print((combinations(n,2)+index[1]-index[0])%mod)
    elif i==3:
        ans=combinations(n,i)+combinations(n-1,i-2)+combinations((index[1]-index[0]-1)+(n-index[1])+1,i-1)-1
        ans%=mod
        print(ans)
    elif i==4:
        ans=combinations(n,i)+combinations(n-1,i-2)+combinations((index[1]-index[0]-1)+(n-index[1])+1,i-1)-1
        ans%=mod
        print(ans)

    else:
        ans=combinations(n,i)+combinations(n-1,i-2)+combinations((index[1]-index[0]-1)+(n-index[1])+1,i-1)
        ans%=mod
        print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
index=[]
z=[0]*(n+1)
for i in a:
    z[i]+=1

for i in range(n+1):
    if z[i]==2:
        pin=i
        break

for i in range(n+1):
    if a[i]==pin:
        index.append(i)


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

def combinations(n,r):
  xxx=lst[n]
  xxx*=pow(lst[n-r],mod-2,mod)
  xxx%=mod
  xxx*=pow(lst[r],mod-2,mod)
  xxx%=mod

  return xxx

for i in range(1,n+2):
    if i==1:
        print(n)
    elif i==n+1:
        print(1)
    elif i==2:
        print((combinations(n,2)+index[1]-index[0])%mod)
    elif i==3:
        ans=combinations(n,i)+combinations(n-1,i-2)+combinations((index[1]-index[0]-1)+(n-index[1])+1,i-1)-(n-index[1])-1
        ans%=mod
        print(ans)
    elif i==4:
        ans=combinations(n,i)+combinations(n-1,i-2)+combinations((index[1]-index[0]-1)+(n-index[1])+1,i-1)-index[0]
        ans%=mod
        print(ans)

    else:
        ans=combinations(n,i)+combinations(n-1,i-2)+combinations((index[1]-index[0]-1)+(n-index[1])+1,i-1)
        ans%=mod
        print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
index=[]
z=[0]*(n+1)
for i in a:
    z[i]+=1

for i in range(n+1):
    if z[i]==2:
        pin=i
        break

for i in range(n+1):
    if a[i]==pin:
        index.append(i)


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

def combinations(n,r):
  xxx=lst[n]
  xxx*=pow(lst[n-r],mod-2,mod)
  xxx%=mod
  xxx*=pow(lst[r],mod-2,mod)
  xxx%=mod

  return xxx

for i in range(1,n+2):
    if i==1:
        print(n)
    elif i==2:
        print((combinations(n,2)+index[1]-index[0])%mod)
    elif i==n+1:
        print(1)
    elif i==3:
        ans=combinations(n,i)+combinations(n-1,i-2)+combinations((index[1]-index[0]-1)+(n-index[1])+1,i-1)-(n-index[1])-1
        ans%=mod
        print(ans)
    elif i==4:
        ans=combinations(n,i)+combinations(n-1,i-2)+combinations((index[1]-index[0]-1)+(n-index[1])+1,i-1)-index[0]
        ans%=mod
        print(ans)

    else:
        ans=combinations(n,i)+combinations(n-1,i-2)+combinations((index[1]-index[0]-1)+(n-index[1])+1,i-1)

Submission status: Wrong Answer

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

v = [-1 for _ in range(n+1)]
for i in range(n+1):
  if v[a[i]] >= 0:
    A = v[a[i]]
    C = n-i
    break
  v[a[i]] = i

MAX_NUM = n+100
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

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

for i in range(2,MAX_NUM):
    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 comb(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

for k in range(1,n+2):
  print(comb(n+1, k) - comb(A+C, k-1))

Submission status: Wrong Answer

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

v = [-1 for _ in range(n+1)]
A = 0
C = 0
for i in range(n+1):
  if v[a[i]] >= 0:
    A = v[a[i]]
    C = n-i
    break
  v[a[i]] = i

MAX_NUM = n+10
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

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

for i in range(2,MAX_NUM):
    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 comb(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

#b = [int(input()) for _ in range(n+1)]
for k in range(1,n+2):
  #print(k)
  print(comb(n+1, k) - comb(A+C, k-1))

Submission status: Wrong Answer

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

v = [-1 for _ in range(n+1)]
A = 0
C = 0
for i in range(n+1):
  if v[a[i]] >= 0:
    A = v[a[i]]
    C = n-i
    break
  v[a[i]] = i

MAX_NUM = n+10
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

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

for i in range(2,MAX_NUM):
    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 comb(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

for k in range(1,n+2):
  #print(k)
  print(comb(n+1, k) - comb(A+C, k-1))

Submission status: Wrong Answer

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

v = [-1 for _ in range(n+1)]
A = 0
C = 0
for i in range(n+1):
  if v[a[i]] >= 0:
    A = v[a[i]]
    C = n-i
    break
  v[a[i]] = i

MAX_NUM = n+10
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

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

for i in range(2,MAX_NUM):
    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 comb(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

for k in range(1,n+1):
  #print(k)
  print(comb(n+1, k) - comb(A+C, k-1))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
MOD = 10**9 + 7
def cmb(n,r,mod):
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod
 
ans = 0
INF = 10**9
x,y = 0,0
l = [-1]*(N+1)
for i in range(N+1):
  if l[A[i]-1] != -1:
    x = l[A[i]-1]
    y = i+1
    break
  l[A[i]-1] = i+1
print(x,y)
for i in range(1,N+2):
  if i == 1:
    print(N)
  elif i == N+1:
    print(1)
  elif N+x-y < i:
    print(cmb(N+1,i,MOD)%MOD)
  else:
    print((cmb(N+1,i,MOD) - cmb(N+x-y,i-1,MOD))%MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
MOD = 10**9 + 7
def cmb(n,r,mod):
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod
 
ans = 0
INF = 10**9
x,y = 0,0
l = [INF]*(N+1)
for i in range(N+1):
  if l[A[i]-1] != INF:
    x = l[A[i]-1]
    y = i+1
    break
  l[A[i]-1] = i+1
print(x,y)
for i in range(1,N+2):
  if i == 1:
    print(N)
  elif i == N+1:
    print(1)
  elif N+x-y < i:
    print(cmb(N+1,i,MOD)%MOD)
  else:
    print((cmb(N+1,i,MOD) - cmb(N+x-y,i-1,MOD))%MOD)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    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

comb = Combination(10**5 + 5)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    pre_idx = 0
    idx = 0
    appeared = [-1] * (N + 1)
    for i, a in enumerate(A):
        if appeared[a] == -1:
            appeared[a] = i
        else:
            pre_idx, idx = appeared[a], i
            break

    """
    dpする前に計算量を見積もる癖はつけた方が良さそう。
    TLEした後に引き返せる時間が残っていない。。。

    問題が「同じ表現を含まない」のネガティブなので、全体から
    表現が被るケースを除くべきでした。
    同じ表現になるのは、２回出てくる数をaとして、aが２回出てくるまでの範囲を見た時に
    aを一回選びかつ2つのaの間の数を全く選ばない時。
    """

    for k in range(1, N + 2):
        if k == 1:
            print(N)
            continue
        rem = (N + 1) - (idx - pre_idx + 1)
        if rem < k - 1:
            print(comb(N + 1, k))
        else:
            print(comb(N + 1, k) - comb(rem, k - 1))





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

n = int(input())
mod = pow(10, 9)+7
ct = [1]*(n+1)
for i in range(1, n+1):
  ct[i] = ct[i-1]*i%mod

def comb(n, k):
  res = ct[n]*pow(ct[n-k], mod-2, mod)%mod*pow(ct[k], mod-2, mod)%mod
  return res

def main():
  a = [int(x) for x in input().split()]

  already = [-1]*n
  for i in range(n+1):
    if already[a[i]-1] != -1:
      f, s = i-already[a[i]-1], n-i
      break
    already[a[i]-1] = i
    
  ans = [0]*(n+1)
  c = 1
  for i in range(n+1):
    c = c*(n+1-i)%mod*pow(i+1, mod-2, mod)%mod
    ans[i] += c%mod
  
  for i in range(n):
    if s < i:
      break
    ans[i] += mod-(comb(s, i))%mod 
    ans[i] %= mod
  for a in ans:
    print(a)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
s = set()
for i in range(N+1):
    a = As[i]
    if a in s:
        r = N-i
        l = As.index(a)
        break
    s.add(a)
mod = 10**9+7
rest = l+r

pos = {}
neg = {}
pos[0] = 1
neg[0] = 1
c = 1
for i in range(1, 10**5+5):
    c *= i
    c %= mod
    pos[i] = c
    neg[i] = pow(c, mod-2, mod)

for i in range(1, N+2):
    All = pos[N+1]*neg[i]*neg[N+1-i]%mod
    if rest-i+1>=0:
        kaburi = pos[rest]*neg[i-1]*neg[rest-i+1]%mod
    else:
        kaburi = 0
    print(All-kaburi)

Submission status: Wrong Answer

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

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

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

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

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

t = sum(a)-n*(n+1)//2
m = a.index(t) + a[::-1].index(t)
print(t, m)
for k in range(1, n+2):
    print((comb(n+1, k)-comb(m, k-1))%mod)

Submission status: Wrong Answer

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

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

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

t = sum(a)-n*(n+1)//2
m = a.index(t) + a[::-1].index(t)
for k in range(1, n+2):
    print(comb(n+1, k)-comb(m, k-1))

Submission status: Wrong Answer

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

"""
どこかに同じ数値が出てくる。
AAAxBBBxCCC
xが同一文字とする
・xがどちらか1つ登場
・Bを使用しない
ものについてはどちらのxを使用しても同じ数列になるので除く
"""
modp = mod
max_n = 2*10 ** 5               # 必要分だけ用意する
fact = [1, 1] + [0]*max_n     # fact[n] = (n! mod modp)
factinv = [1, 1] + [0]*max_n  # factinv[n] = ((n!)^(-1) mod modp)
inv = [0, 1] + [0]*max_n      # factinv 計算用

def cmb(n, r, p):
    assert n < p, 'n is less than modp'
    assert n < max_n, 'n in less than max_n'
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

for i in range(2, max_n + 1):
    fact[i] = (fact[i-1] * i) % modp
    inv[i] = (-inv[modp % i] * (modp // i)) % modp
    factinv[i] = (factinv[i-1] * inv[i]) % modp

counter = [0] * n
for i in range(n+1):
    counter[a[i]-1]+=1
    if counter[a[i]-1] == 2:
        second = i
        first = a.index(a[i])
        break

# xの重複を考慮せず全てカウント
ans = [cmb(n+1, i, mod) for i in range(1, n+2)]

n_left = first
n_right = n-second
n_lr = n_left + n_right

# i個の重複する組合せはn_lrからi-1個選び、xをどちらか1つ選ぶ。
doubled = [1]+[cmb(n_lr, i, mod) for i in range(1, n_lr+1)]

for i in range(n_lr+1):
    ans[i] -= doubled[i]

for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
N=10**5+3
mod=10**9+7
fac=[1]*(N+1)
for i in range(1,N+1):
    fac[i]=fac[i-1]*i%mod
inv_fac=[1]*(N+1)
inv_fac[N]=pow(fac[N],mod-2,mod)
for i in range(N-1,0,-1):
    inv_fac[i]=inv_fac[i+1]*(i+1)%mod
def nCr(n,r):
    if n<0 or r<0 or r>n:
        return 0
    return fac[n]*inv_fac[r]%mod*inv_fac[n-r]%mod
n=int(input())
A=list(map(int,input().split()))
used=[0]*n
for i in range(n+1):
    a=A[i]
    if used[a-1]==0:
        used[a-1]=[1,i]
    else:
        x=a
        y=used[a-1][1]
        z=i
        break
print(n)
for i in range(2,n+2):
    ans=nCr(n+1,i)-nCr(n-z+y,i-1)
    print(ans)

Submission status: Wrong Answer

Solution code:
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


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)


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

appeared = set()
dup_right = 0
dup = 0
for i, x in enumerate(a):
    if x in appeared:
        dup_right = n - i
        dup = x
        break
    appeared.add(x)
dup_left = 0
for i, x in enumerate(a):
    if x == dup:
        dup_left = i
        break

for k in range(1, n + 2):
    print(comb(n + 1, k, MOD) - comb(dup_right + dup_left, k - 1, MOD) + MOD % MOD)