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:
def cmb(n, r, p):
	if (r<0) or (n<r):
		return 0
	r=min(r, n-r)
	return fact[n]*factinv[r]*factinv[n-r]%p

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

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


N=int(input())
A=list(map(int,input().split()))
index=[-1]*N
for i,a in enumerate(A):
    if index[a-1]!=-1:
        dup_first,dup_second=index[a-1],i
        break
    index[a-1]=i

mod=10**9+7
n=dup_first
m=N-dup_second
l=n+m
for k in range(1,N+2):
    if k==1:
        print(N)
        continue
    ans=cmb(N+1,k,mod)-cmb(l,k-1,mod)
    print(ans)

Submission status: Wrong Answer

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

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

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


N=int(input())
A=list(map(int,input().split()))
index=[-1]*N
for i,a in enumerate(A):
    if index[a-1]!=-1:
        dup_first,dup_second=index[a-1],i
        break
    index[a-1]=i

mod=10**9+7
n=dup_first
m=N-dup_second
l=n+m
for k in range(1,N+2):
    ans=cmb(N+1,k,mod)-cmb(l,k-1,mod)
    print(ans)

Submission status: Wrong Answer

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

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

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


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

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

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

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

Submission status: Wrong Answer

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

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

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


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

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

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

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

Submission status: Wrong Answer

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

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

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


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

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

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

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

Submission status: Wrong Answer

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    def find_duplicate(L):
        n = len(L)
        table = [None] * n
        for i, num in enumerate(L):
            if table[num] is not None:
                return table[num], i
            else:
                table[num] = i

    def make_factorial_table(size, mod):
        '''
        fact_mod[i] は i! % mod を表す。fact_mod[0] ~ facto_mod[size] まで計算可能なテーブルを返す
        >>> make_factorial_table(20, 10**9+7)
        [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 227020758, 178290591, 674358851, 789741546, 425606191, 660911389, 557316307, 146326063]
        '''
        fact_mod = [1] * (size + 1)
        for i in range(1, size + 1):
            fact_mod[i] = (fact_mod[i - 1] * i) % mod
        return fact_mod

    def combination(n, r, mod, fact_table):
        '''
        フェルマーの小定理 
        a ^ p-1 ≡ 1 (mod p)
        a ^ p-2 ≡ 1/a (mod p) (逆元)
        nCr = (n!) / ((n-r)! * r!) だが、mod p の世界ではこの分母を逆元を用いて計算しておくことが可能
        
        >>> m = 1000000007
        >>> fact_table = make_factorial_table(100, m)
        >>> combination(10, 5, m, fact_table)
        252
        >>> combination(100, 50, m, fact_table)
        538992043
        '''
        if r > n:
            return 0
        numerator = fact_table[n]
        denominator = (fact_table[n-r] * fact_table[r]) % mod
        # pow はすでに繰り返し二乗法で効率的に実装されている
        return (numerator * pow(denominator, mod-2, mod)) % mod

    n = ii()
    L = lmi_0()
    i, j = find_duplicate(L)
    fact = make_factorial_table(n+1, mod)

    for l in range(1, n+2):
        print(combination(n+1, l, mod, fact) - combination(i+n-j, l-1, mod, fact))




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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


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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


n = int(input())
*a, = map(int, input().split())
indices = [-1]*n
l, r = 0, 0
for i in range(n+1):
    if indices[a[i]-1] != -1:
        l = indices[a[i]-1]
        r = i
        break
    indices[a[i]-1] = i

MOD = 10**9+7
c = Combination(10**6, MOD)
for i in range(1, n+2):
    ans = c.choose(n+1, i) - c.choose(l+n-r, i-1)
    print(ans)

Submission status: Wrong Answer

Solution code:

class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


n = int(input())
*a, = map(int, input().split())
indices = [-1]*n
l, r = 0, 0
for i in range(n+1):
    if indices[a[i]-1] != -1:
        l = indices[a[i]-1]
        r = i
        break
    indices[a[i]-1] = i

MOD = 10**9+7
c = Combination(n+100, MOD)
for i in range(1, n+2):
    ans = c.choose(n+1, i) - c.choose(l+n-r, i-1)
    print(ans)

Submission status: Wrong Answer

Solution code:

class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


n = int(input())
*a, = map(int, input().split())
indices = [-1]*n
l, r = 0, 0
for i in range(n+1):
    if indices[a[i]-1] != -1:
        l = indices[a[i]-1]
        r = i
        break
    indices[a[i]-1] = i

MOD = 10**9+7
c = Combination(n+100, MOD)
for i in range(1, n+2):
    ans = c.choose(n+1, i) - c.choose(l-1+n-r, i-1)
    print(ans)

Submission status: Wrong Answer

Solution code:

class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


n = int(input())
*a, = map(int, input().split())
indices = [-1]*n
l, r = 0, 0
for i in range(n+1):
    if indices[a[i]-1] != -1:
        l = indices[a[i]-1]
        r = i
        break
    indices[a[i]-1] = i

MOD = 10**9+7
n += 1
c = Combination(n, MOD)
k = n-(r-l+1)
for i in range(1, n+1):
    ans = c.choose(n, i) - c.choose(k, i-1)
    print(ans)

Submission status: Wrong Answer

Solution code:

class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


n = int(input())
*a, = map(int, input().split())
indices = [-1]*n
l, r = 0, 0
for i in range(n+1):
    if indices[a[i]-1] != -1:
        l = indices[a[i]-1]
        r = i
        break
    indices[a[i]-1] = i

MOD = 10**9+7
n += 1
c = Combination(n, MOD)
k = n-(r-l+1)
for i in range(1, n+1):
    ans = c.choose(n, i)
    if i == 1:
        ans -= 1
    elif k >= (i-1):
        ans -= c.choose(k, i-1)
    print(ans)

Submission status: Wrong Answer

Solution code:

class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


n = int(input())
*a, = map(int, input().split())
indices = [-1]*n
l, r = 0, 0
for i in range(n+1):
    if indices[a[i]-1] != -1:
        l = indices[a[i]-1]
        r = i
        break
    indices[a[i]-1] = i

MOD = 10**9+7
n += 1
c = Combination(n, MOD)
k = l+n-r
for i in range(1, n+1):
    ans = c.choose(n, i)
    if i == 1:
        ans -= 1
    elif k >= i:
        ans -= c.choose(k-1, i-1)
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
d = {i:-1 for i in range(1, N+1)}
*l, = map(int, input().split())

MOD = 10**9+7
n = N+1
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD if a>=b else 0

for i, j in enumerate(l):
    if d[j] != -1:
        break
    d[j] = i

v = d[j]+N-i
for i in range(1, N+2):
    print(comb(N+1, i)-comb(v, i-1))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
a = list(map(int, input().split()))
#互いに素なa,bについて、a*x+b*y=1の一つの解
def mod_combination(n,k,mod):
    if k == 0:
        return 1
    return (n*mod_inv(k,mod) * mod_combination(n-1,k-1,mod) ) % mod
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
mod = 10**9+7
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
combi = [0 for i in range(n+2)]
combi[0] = 1
for i in range(1,n+2):
    combi[i] = (combi[i-1]*(n-i+2)*mod_inv(i,mod)) % mod
kind = set()
left = -1
right = -1
for i in range(n+1):
    if a[i] in kind:
        right = (n - i)
        left = a.index(a[i])
        break
    else:
        kind.add(a[i])
combi_remain = [0 for i in range(left + right+3)]
combi_remain[0] = 1
for i in range(1,left+right+2):
    combi_remain[i] = (combi_remain[i-1]*(left+right-i+1)*mod_inv(i,mod)) % mod
for i in range(1,n+2):
    if i-1 <= left+right:
        print(combi[i] - combi_remain[i-1])
    else:
        print(combi[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)
for i in range(n+1):
    if b[a[i]] == 0:
        b[a[i]] += 1
    else:
        d = a[i]

l = 0
r = 0
c = 0
for i in range(n+1):
    if a[i] != d and c == 0:
        l += 1
    elif a[i] != d and c == 2:
        r += 1
    elif a[i] == d:
        c += 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 = 100011
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(r+l, i-1, mod))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)
for i in range(n+1):
    if b[a[i]] == 0:
        b[a[i]] += 1
    else:
        d = a[i]

l = 0
r = 0
c = 0
for i in range(n+1):
    if a[i] != d and c == 0:
        l += 1
    elif a[i] != d and c == 2:
        r += 1
    if a[i] == d:
        c += 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 = 100011
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 )


print(n)
for i in range(2, n+2):
    print(cmb(n+1, i, mod)-max(0, r-i+2)-max(0, l-i+2))

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split());b={};M=10**9+7;p=n+1;q=r=1
for i,x in enumerate(a):
 if x in b:d=i-b[x];break
 b[x]=i
for k in range(n+1):print(p-q);q=q*(n-d-k)*r%M;r=pow(k+2,M-2,M);p=p*(n-k)*r%M

Submission status: Wrong Answer

Solution code:
M = 10 ** 9 + 7


cache = {}

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


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

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

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

Submission status: Wrong Answer

Solution code:
M = 10 ** 9 + 7


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


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

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

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

Submission status: Wrong Answer

Solution code:
M = 10 ** 9 + 7


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


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

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

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

    # ans = pow(2, n + 1, M) - pow(2, d1, M) * pow(2, n + 1 - d2)
    # print(ans)

Submission status: Wrong Answer

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


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


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

for i in range(1, n + 2):
    print(1)
#     print(mod_comb(n + 1, i))  # - mod_comb(x, (i - 1)))

Submission status: Wrong Answer

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


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


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

for i in range(1, n + 2):
    print(mod_comb(n + 1, i))  # - mod_comb(x, (i - 1)))

Submission status: Wrong Answer

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

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

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

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

val = sum(A) - sum(set(A))
i = -1
j = -1
for k in range(n):
    if A[k] == val:
        if i == -1:
            i = k
        elif j == -1:
            j = k
            break

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

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
MAX = 10**5+1
fact = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i)%mod
inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[mod%i]*(mod-mod//i)%mod
fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1]*inv[i]%mod
def comb(n, r):
    if n < r:
        return 0
    return fact[n]*fact_inv[n-r]*fact_inv[r] % mod

n = int(input())
L = list(map(int,input().split()))
M = []
for i in range(n+1):
    M.append(L[i])
M.sort()
dou = 1 #重複する数
for i in range(n+1):
    if M[i] == dou:
        dou += 1
    else:
        dou = M[i]
        break
l = 0
r = 0
cnt = 0
for i in range(n+1):
    if L[i] == dou and cnt == 0:
        l = i+1
        cnt += 1
    elif L[i] == dou and cnt == 1:
        r = i+1
        break
for i in range(1,n+1):
    print(comb(n+1,i)-comb(l+n-r-1,i-1))
print(1)