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.readline
sys.setrecursionlimit(10**9)
from collections import Counter
mod=10**9+7
n=int(input())
A=list(map(int,input().split()))
factorial=[1]
for i in range(1,n+2):
    factorial.append(factorial[i-1]*i%mod)
inverse=[0]*(n+2)
inverse[n+1]=pow(factorial[n+1],mod-2,mod)
for i in range(n,-1,-1):
    inverse[i]=inverse[i+1]*(i+1)%mod
def comb(n,r):
    if n<r or n==0 or r==0:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod
C=Counter(A)
i=C.most_common()[0][0]
idx=[k for k, x in enumerate(A) if x==i]
for k in range(1,n+2):
    print((comb(n+1,k)-comb(n+idx[0]-idx[1],k-1))%mod)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import Counter
mod=10**9+7
n=int(input())
A=list(map(int,input().split()))
factorial=[1]
for i in range(1,n+2):
    factorial.append(factorial[i-1]*i%mod)
inverse=[0]*(n+2)
inverse[n+1]=pow(factorial[n+1],mod-2,mod)
for i in range(n,-1,-1):
    inverse[i]=inverse[i+1]*(i+1)% mod
def comb(n,r):
    if n<r or n==0 or r==0:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod
C=Counter(A)
i=C.most_common()[0][0]
idx=[k for k, x in enumerate(A) if x==i]
for k in range(1,n+2):
    print((comb(n+1,k)%mod-comb(n+idx[0]-idx[1],k-1)%mod)%mod)

Submission status: Wrong Answer

Solution code:
#<!` _<<!~     _?1<1zwvvvzvzzzzI`         `(<-`.C(<~.~.~.~.~.~~~<~.~~.~_~~.~~.~~.~~~.~~<_jZZ!.`.<>;!.``..-dyyyyyyyyyyyyyyyyyXVtzwyV
#:__` `````    ` `` (zrrrrrvvvrt ` `  ` `  .-~ (/_.._``_`    `.-_--.._... ```    ```_.~~?-jI.`(>;<_..``..JuZZZZZZZZyZZZZZZZyZZZZZZy
#   ````````. .-((+zztttttrtrttt.`  `  `  `  `(!``` ...<.~~-J~->~~~~(_~(-~~~_~.~_..  ``` __>.-;>+(<``..-wuuuuuuuuuuuZZuuuuXXZ<<<<??
# ```.-_---(++++lttltltttltttttl_`        ` _(!..__+<_J~~~-j>~j>~.~~(_~(>~~~_1~~~~~~~.__...--z<!.``..-zrvvzzzzzzzwwvwZv<<<<?1z<_``
#----((+(+1zllllllllllllllllllll:` `  `   ` 1>(~~~(I~(l~~_J1~(Z~~.~~j<~~<-~~~zx~~.~~.~(~~~~(1.. ..(vzttttrrrrtOI<<<1z<_`...-__----(
#========ll==ll=l=l==l=l========}   `  `   `>_>~~(tI(w<~~J!<_v(_~~~~zl~~><~~~zr<~~~<~~(:~~~~j-.`-?<_1zz<1ll=z<<_..````  _<++zzttOww
#=?????????==??=????????????????>`       `  _(~~~jvIjw(<j!`<(=?<~~.~zI~~< 1(<JXX+-~(_~(I~~~_~>.```.-<z+<+???????=1+++++zzwwvrvrrvuZ
#??>>?>?>>>>>>>>>>>>>>>>>>>>>>>;<`` `  `  ``.2~~(wzwzI~(:``<<` >~<~~jvl~(  <~~vzw<<1;~_r<~~(~(+i..`` jz???????=1zzwwrrwwzXZOwwwrrrr
#wOOOztzz++>;;;;;;;;;;<+++++++;;<`  ` `  `  .>~~(vuXz$~;  `<:` (~>~~(zw+~_``(_((Xw<~>~(rl~~(l(<_<i.`..I>?>?1zwwXuuXXzzvOrrttwzzzXXk
#fkuuzvwXXXXXXAA&++uswwZXZyyyVXAu_ `   `  `  >~~(zuXX6(`` .(-.` >(-~(zz?-(` `._<_Ir+>~(vI~~~v<:``._.`.(zzwwuXX0VwrwXXWyXXwrrvrwXXfW
#kWWuuvrrZU0UX0XWWHWWyZXUZuZyZZX&;`  `  `  ``<~((zuXZ?TYWYM@M9$`.-<_~zv|.(i....+&.jwr~(zZ~~~w$;.``````.jzzuzvvrrOwwzXWWUZtOwwwXfWHk
#qHkHkkkwwOwwvvuuuXWWUUUZXXXXZyyX}`  `  `   `.~+(zuXr `.n.dMM-` `.<._(rI` 1-P?WHMY"Yr(wuZ:<~wXk-...`.`. OvwwvwXXXWkXWHWXwXkWWkqmmHH
#HHkbWHpWXwwXWXwuVwvzwXXXXXXuuXU$(`   `  `  `._d2zkz\` JHXH@W}     !`~?Z_``,HQMMM]` >jkuZ(<:XXSI_~-...`.(XbWU0XwXWpWqqqHkkHWWbWWWHm
#WWWbpWfWkwXWkwwvwwwwvXUWkXyXZZX>( ` `  `  ` `IdXwXkl` .WXXdf ` `    ` ?I `(WdM8W\`.JXuu$d<(UuuX<~~~~~<j-JkkZOXUWHHHHUZWWWpWWWHmmgg
#gHWWHWWWXXrwuuXyXXwZZXuXVfWHWXZ~~_`  `  `  ``(kWUkfw.`` ?7^`` ` ` `  ` ` `.4ZZX%`.OXuXkjW:JuuuuI~~~~~~(wUSXwwkXVVUWppHHHkWHHHqqqgH
#ggHHWWHUXZXXuzXZZuZyWyZXuXWWkHt~~~ `  `  `  `.XWkXW/1.``````  `  `  `   ````` `` ?(uXW0SW+Suuuuw_~~~~~(wXHHHHkwrtdHHVU9WHH@HSVWHHX
#UUXuXZXXkXXWuXZ0UZXf0XuXZWWWWX<~~(  `  `  `  `?cCzz}``````````  `    `` `````````.ZUXHV>SXuuuuuzl~~~~~(HkH@HWkwwwWHHklzwWHg@Hz?OWH
#VwW0lwWWXwzXzrOwwXXOOOOXuXkOzC~~~_;`  `  ` `` (C~~jw.`````` `  `  `    ` ```````.`,dSI~(WRuuuuuuI~~~~~~WHg@HWUUZdWH@KOdHgMHHMkOvWH
#wtwW0V0U0OwOZUZkrZvOXXyyyWH&u<~~~(w ` ` `   .(_-:~(vl``` ` `  `  `  ``  ` ```````,_yuI~~dWuuuuuuz<~~~~~dWkHHSwXwXH@HkwH@HHHHMkAwku
#kwXWHRwOzzzOwZVTCzzwuudHHHHMP~~~~zw;.  `  .~>_ _1-~jvl`   `  `  ` `  `  `    ` `,zURuI~:dWuuuuuuzl~~~~~(UUzZZUuXHHH@HHXHHHM@@HkWKC
#HHHMMMHXuwzzzwwrrZZZOwXUMMMM3~~~(wX6~~.~.~(<! _~._<:zv,```  `  `` ``   ` `  ` `.wwWSzl~>dgKuuuuuuI~~~~~(yzzdWWWXWHHHHWHHHHXUW9WWAd
#yWbqHMMkHHWWW0OwzllzzdHMMHHM<~~~zXc<:~~._(-! ~~`.. ((OdI..`` `      `  ` ````.JWWHHuz>~IWgHuuuuuuv<~~~~~VTTWHkwwzlOXHMHMHWmeWSWKWH
#wWH@@HMkkXWU0VOOOzlwQWHHMMHD~~~(zuI?J--(__`.~_`.`.  >?wXzzO+. ` ` `  ``` ..+ijz+XHHuZ<(<HHHuuuuukzl~~~~~jczXHHWHkZwXHNwOv4ZHHRgdHM
#UHH@@HHWWUUZXkwXwAQHHMMHHMM>~~~(uuh?1.>_`._~``.``  `<~juSrtO~~<~.. .._<<(llllllltORuI~J(TVOSuuuuRuI~~~~~(HkfyWbWHkWHHHHHHdHUmMMMNM
#kHMHHHHWWXOttrrOIdHHHqHHHH#~~~(wuuZC1--._:`` _```  `(~~zXy7z~~.~.~.~~.~~jttttlttOduv>(Z(zzzwzuuuXuX_~~~~(HHWWWWHMHHmKUpWMMMMHMMMMM
#WqHWg@HHWWWXXtwWkXHHHHMHHM$~~~(uuX%.-_<<~ `.!` `   `--_(wr~_~-~.~.~.~~._(zOOOOlI1dzZ~(RdXkAdkuuuXkz>~~~~~dHH@@HMMMHYCx1XdKC?wHMMNW
#HMHWWH@H@HHkAQXHHH@HMHMHHH<~~~zuuX!``.<---<`` ```  `(1>_jw` . ~-~~._`  ``??!?wwuXSz>(WKHHWWWWuuuuRuI~~~~~?qHM@HWVXvCodXY<j&jHNMMHZ
#HHHWHMMMHHHgmHkHHWWHMHHHM$~~~(zuuZ``` ..~._` ` ` ```_(o<(k-``-.`_-.` .._``` .`-?XzC~yrkvrvrtZkuuuXuZ~~~~~~XWW99UWHHK1jxdkdMMVBO4mW
#@MMmHMHHHHMHkHWp01dkHHHHH<~~~(uuzr` `..... `` ` `` `<_1<(U>`  ` ~.``` ``..~ ```.XZ<?7jSOrrrrrXuuuXkX<~~~~~(wO+++zvWHkmMMMMM+(mdKWO
#qgg@@HHHHHH@HHHHHkXWWWHHP~~~_yuuuI``  .~~. ` ` `` ``: ((((: `` ` __~~~!` ``  `.ww3!``(`.1trttwWuuuWul~~~~~~XRWzdHMWHMMMMH83jgH>vIk
#HMHSVXvrwXWmH@HHVWyWHHpV>~~~(zuuuz;``` ... ` ` `` ` <`.+(.~ `` ` <_ -~  ` ``` Jvz!`` ````(trrrdXuuXXI~~~~~~(udXS6zWMBN+dMMWMMMMHHH
#qHHXwwXWbH@MHHUHHkHMHHHf~~~~juXuuuXe ``_.~_` ` ` `  ~`.z:.``` ` `<_.(_ `` ` `(</``` ` `  `(rzXrWuuZKX_~~~~~_WWNdNMHHNVDdMRuJumvzUH
#pWXwXZyUWHMmHkXXHHMHHWX>~~~_wuXuuZHMk.` _.< ` `  `` ` z>```  ````<.~> ` `` `  ``` ` `` .`` wzZXvWuuXul~~~~~~?WMWMmMMMNHQQM#7UOgdMM
#WWSOOZOOwWHH@@HHMM@HXWP~~~~(zXSuudHHNV+  .(_ ``    `` ``` `` ` ``~ (_`  ` ``  ` ` `` ``_ ``OvXXzZkuXKI~~~~~~(w40WNNMMNMM##Ozj+:?dM
#MSIzzzIzXwwVHHHHHMMMgq>~~~~(uXuuXMMHXXXm, ~<_ `.` ` `` ` ` `` `  - ( ` ` ` `` `` `  `  : ``jvzZuvdkuWX-~~~~~~GW#MNMNMMVMCu-uJ?WNyQ
#SOOZOwOZwwzuZUWbWWVXU9~~~~~zukuuWM@HHMMMHm_(.  _ `  `   ` ` `` ``. ;` `` ``  ` `` ``  .`` `,vzXuzzXkXkI~~~~~~JHMMMMMNmJjRH9aZamWMM
#kwwwUXZz11wUUXyJXmdHWl~~~~(zXSuXg@ggmHH@H@NJ<_ _` `  ``  `  ` ` `. :` ` ` ` ``  `  ` `.````.(vvXXuzXkWI~~~~~~(VYWWHHSQgH8GW9<w9UNK
#0VIwXI+XHU<zryZ6?uQWR:~~~~(uXuZW@gMM@HHHHMN#b_ _`` `` ``` `` ` `` (~`` ` ` ` ` ` ``` `_`  `.`(wwXXXXWXX_~~~~~:XQMMWHNMMMd9CjkQgMNg

Submission status: Wrong Answer

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

n = int(input())
A = tuple(map(int,input().split()))
p = 10**9+7
used = [-1]*n
for i in range(n+1):
    if used[A[i]-1]>=0:
        a = used[A[i]-1]
        b = i
        break
    used[A[i]-1] = i


#互いに素なa,bについて、a*x+b*y=1の一つの解
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は互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

######################################################


#pは素数とする

#fact[i] : i! modp (0<= i <p) O(p)
fact = [1]
k = 1
for i in range(1,n+2):
    k = k*i%p
    fact.append(k)


#n! = a p^eとしたときのeを求める (O(logp n)
def mod_e(n,p):
    res = 0
    while n >= p:
        res += n//p
        n = n//p
    return res

#n! = a p^eとしたときのa mod pを求める  (O(logp n)
def mod_fact(n,p):
    if n==0:
        return 1
    
    
    res = mod_fact(n//p,p)
    
    if n//p %2 != 0:
        return res*(p-fact[n%p])%p
    return res*fact[n%p]%p
    
######################################################

#nCk mod p
def mod_comb(n,k,p):
    if n < 0 or k < 0 or n<k:
        return 0
    e1 = mod_e(n,p)
    e2 = mod_e(k,p)
    e3 = mod_e(n-k,p)
    #pで割り切れる場合
    if e1 > e2 + e3:
        return 0

    #pで割り切れない場合
    a1 = mod_fact(n,p)
    a2 = mod_fact(k,p)
    a3 = mod_fact(n-k,p)
    return a1 * mod_inv(a2*a3%p,p) %p
#print(a,b)
for k in range(1,n+2):

    res = mod_comb(n+1,k,p)-mod_comb(a+n-b,k-1,p)
    print(res)

Submission status: Wrong Answer

Solution code:

from collections import Counter
mod=10**9+7
N=10**5+11
fac,finv,inv = [0]*N,[0]*N,[0]*N

def cmb_init():
        fac[0]=fac[1]=finv[0]=finv[1]=inv[1]=1
        for i in range(2,N):
                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 cmb_mod(n,k):
        if n<k : return 0
        return fac[n]*(finv[k]*finv[n-k]%mod)%mod

n=int(input())
a=list(map(int,input().split()))
ac = Counter(a).most_common()[0][0]
sames=[i for i,x in enumerate(a) if x==ac]
same_len = sames[0]+(n-sames[1])
cmb_init()
print(n)

for i in range(1,n):
        print(cmb_mod(n+1,i+1) - cmb_mod(same_len,i))
print(1)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
mod=10**9+7
N=10**5+11
fac,finv,inv = [0]*N,[0]*N,[0]*N

def cmb_init():
        fac[0]=fac[1]=finv[0]=finv[1]=inv[1]=1
        for i in range(2,N):
                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 cmb_mod(n,k):
        if n<k : return 0
        return fac[n]*(finv[k]*finv[n-k]%mod)%mod

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

sames=[i for i,x in enumerate(a) if x==sums-(n*(n+1)//2)]
same_len = sames[0]+(n-sames[1])
cmb_init()
print(n)

for i in range(1,n):
        print(cmb_mod(n+1,i+1) - cmb_mod(same_len,i))
print(1)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
mod=10**9+2
def cmb(n,r):
    if r>n: return 0
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


n=int(input())
a=list(map(int,input().split()))
sums=0
for aa in a:
        sums+=aa

sames=[i for i,x in enumerate(a) if x==sums-(n*(n+1)//2)]
same_len = sames[0]+(32-sames[1])

print(n)

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

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]

n = int(input())
a = ai()

dup = sum(a)-n*(n+1)//2
ant = a.index(dup)
post = a[::-1].index(dup)
print(ant,post)

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

inverse = [0]*(n+2)
inverse[n+2-1] = pow(factorial[n+2-1], mod-2,mod)
for i in range(n+2-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod


def nCr(n,r):
    if n<r or n==0 or r==0:
        return 0
    return factorial[n] * inverse[r] * inverse[n-r] % mod


for k in range(1,n+2):
    if k == 1:
        print(n)
    else:
        ans = nCr(n+1,k) - nCr(ant+post,k-1)
        if ans < 0:
            ans += mod
        print(ans)

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]


n = int(input())
a = ai()

from collections import Counter
dup = list(Counter(sorted(a)).values()).index(2)+1
ant = a.index(dup)
post = a[::-1].index(dup)


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

inverse = [0]*(n+2)
inverse[n+2-1] = pow(factorial[n+2-1], mod-2,mod)
for i in range(n+2-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod


def nCr(n,r):
    if n<r or n==0 or r==0:
        return 0
    return factorial[n] * inverse[r] * inverse[n-r] % mod


for k in range(1,n+2):
    if k == 1:
        print(n)
    else:
        ans = nCr(n+1,k) - nCr(ant+post,k-1)
        print(ans)

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]


n = int(input())
a = ai()

from collections import Counter
dup = list(Counter(sorted(a)).values()).index(2)+1
ant = a.index(dup)
post = a[::-1].index(dup)


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

inverse = [0]*(n+2)
inverse[n+2-1] = pow(factorial[n+2-1], mod-2,mod)
for i in range(n+2-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod


def nCr(n,r):
    if n<r or n==0 or r==0:
        return 0
    return factorial[n] * inverse[r] * inverse[n-r] % mod


for k in range(1,n+2):
    ans = nCr(n+1,k) - nCr(ant+post,k-1)
    print(ans)

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]


n = int(input())
a = ai()

from collections import Counter
dup = list(Counter(sorted(a)).values()).index(2)+1
ant = a.index(dup)
post = a[::-1].index(dup)

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

inverse = [0]*(n+2)
inverse[n+2-1] = pow(factorial[n+2-1], mod-2,mod)
for i in range(n+2-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod


def nCr(n,r):
    if n<r or n==0 or r==0:
        return 0
    return factorial[n] * inverse[r] * inverse[n-r] % mod


for k in range(1,n+2):
    if k == 1:
        print(n)
    else:
        ans = nCr(n+1,k)
        if ant+post+1 >= k:
            ans -= nCr(ant+post,k-1)
        print(ans)

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]


n = int(input())
a = ai()
MOD = 10**9+7

from collections import Counter
dup = list(Counter(sorted(a)).values()).index(2)+1
ant = a.index(dup)
post = a[::-1].index(dup)

fac = [1, 1] + [0] * n
finv = [1, 1] + [0] * n
inv = [0, 1] + [0] * n
for i in range(2, n + 2):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = -inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD


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


for k in range(1,n+2):
    if k == 1:
        print(n)
    else:
        ans = nCb(n+1,k)
        if ant+post+1 >= k:
            ans -= nCb(ant+post,k-1)
        print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
import collections
m=10**9+7
f=[0 for i in range(10**5+3)]
f[0]=1
for i in range(1,10**5+2):
  f[i]=f[i-1]*i%m
def bp(a,n):
        r=1
        while(n):
           if n%2:
              r=r*a%m
           a=a*a%m
           n>>=1
        return r

c = collections.Counter(a)
b=c.most_common()[0][0]
kk=a.index(b)
k=n-a[::-1].index(b)


def C(n, r):
    return ((f[n]%m) * bp(f[n - r],10**9+5)* bp(f[r],10**9+5))%m
print(n)
for i in range(n):
 x=C(n+1,i+2)
 if kk+n-k>=i+1:x-=C(kk+n-k,i+1)
 
 print(x)

Submission status: Wrong Answer

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

c = [1,n-1]
#c[i]:n-1 C i
for i in range(1,n+1):
    if n < i+2:
        c.append(0)
    else:
        r = (c[-1]*(n-1-i)//(i+1))
        r = r%(10**9+7)
        c.append(r)
k = sum(a)- n*(n+1)//2

pp = []
for i in range(n+1):
    if a[i] == k:
        pp.append(i)
w = pp[1]-pp[0]-1

d = [1,n-w-1]
#d[i]:n-w-1 C i
for i in range(1,n+1):
    if n-w-1  < i+1:
        d.append(0)
    else:
        r = (d[-1]*(n-w-1-i)//(i+1))
        r = r%(10**9+7)
        d.append(r)

    

print(n)
for i in range(2,n+2):
    #nagasa k = i
    ass = 0
    ass += c[i] + c[i-1]*2 -d[i-1] + c[i-2]
    ass = ass % (10**9+7)
    print(ass)

Submission status: Wrong Answer

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

c = [1,n-1]
#c[i]:n-1 C i
for i in range(1,n+1):
    if n < i+2:
        c.append(0)
    else:
        r = (c[-1]*(n-1-i)//(i+1))%(10**9+7)
        c.append(r)
k = sum(a)- n*(n+1)//2

pp = []
for i in range(n+1):
    if a[i] == k:
        pp.append(i)
w = pp[1]-pp[0]-1

d = [1,n-w-1]
#d[i]:n-w-1 C i
for i in range(1,n+1):
    if n-w-1  < i+1:
        d.append(0)
    else:
        r = (d[-1]*(n-w-1-i)//(i+1))%(10**9+7)
        
        d.append(r)

print(n)
for i in range(2,n+2):
    #nagasa k = i
    ass = 0
    ass += c[i] + c[i-1]*2 -d[i-1] + c[i-2]
    ass = ass % (10**9+7)
    print(ass)

Submission status: Wrong Answer

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

c = [1,n-1]
#c[i]:n-1 C i
for i in range(1,n+1):
    if n - 1 < i+1:
        c.append(0)
    else:
        r = c[-1]*(n-1-i)//(i+1)
        c.append(r)
k = sum(a)- n*(n+1)//2
pp = []
for i in range(n+1):
    if a[i] == k:
        pp.append(i)
w = pp[1]-pp[0]-1

d = [1,n-w-1]
#d[i]:n-w-1 C i
for i in range(1,n+1):
    if n-w-1  < i+1:
        d.append(0)
    else:
        r = d[-1]*(n-w-1-i)//(i+1)
        d.append(r)
#print('w',w)
#print('c',c)
#print('d',d)
print(n)
for i in range(2,n+2):
    #nagasa k = i
    ass = 0
    ass += c[i]
    ass += c[i-1]
    ass += c[i-1]- d[i-1]
    ass += c[i-2]
    print(ass)

Submission status: Wrong Answer

Solution code:
MOD = (10 ** 9) + 7

f_list = [1] * 100000
f_r_list = [1] * 100000

for i in range(99999):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, 100001):
	f_r_list[-i] = int((f_r_list[-i + 1] * (100002 - i)) % MOD)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

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

for i in range(1, n + 1):
	x = a.index(i)
	y = a_r.index(i)
	if x + y != n:
		break

num = x + y

print(n)

for i in range(2, n + 2):
	if num >= i - 1:
		print(comb(n + 1, i) - comb(num, i - 1))
	else:
		print(comb(n + 1, i))

Submission status: Wrong Answer

Solution code:
import math

def LI(): return list(map(int, input().split()))
def LS(): return input().split()
def I(): return int(input())
def S(): return input()
def combi(n,k):
    f = math.factorial
    return f(n) // f(k) // f(n-k)

n = I()
a = LI()

two = 0
for i in range(1, n + 1):
    if a.count(i) == 2:
        two = i
        break
L = a.index(two)
R = a[::-1].index(two)

ans = []
combi_all = [0]*(n+2)
combi_all[0] = 1
for i in range(1, n+2):
    combi_all[i] = combi_all[i - 1]*(n+1-i+1)//i

combi_L = [1]*(L+1)
combi_R = [1]*(R+1)
for i in range(1, L+1):
    combi_L[i] = combi_L[i - 1]*(L-i+1)//i
for i in range(1, R+1):
    combi_R[i] = combi_R[i - 1]*(L-i+1)//i


for k in range(1, n+2):
    all = combi_all[k]
    if k == 1:
        all -= 1
    else:
        if k <= R + L + 1:
            for i in range(max(0, k-1 - R), min(k - 1, L) + 1 ):
                all -= combi_L[i]*combi_R[k-1 - i]
    ans.append(all%(10**9 + 7))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter

# 参考サイト
# http://arc058.contest.atcoder.jp/data/arc/058/editorial.pdf

N = int(input())
As = list(map(int, input().split()))
cnt = Counter(As)
dup, _ = cnt.most_common(1)[0]
# print(cnt.most_common(1)[0])
a = As.index(dup) #重複数字の最初の場所
As[a] = -1
b = As.index(dup) #重複数字の次の場所

MOD = 1000000007

if N == 1:
    print(1)
    print(1)
    exit()


# def nCr(n, r):
#     # 10C7 = 10C3
#     r = min(r, n-r)
#     # Calculate the numerator.
#     numerator = 1
#     for i in range(n, n-r, -1):
#         numerator *= i
#     for i in range(r, 1, -1):
#         numerator //= i
#     return numerator
def modc(a,b,m):
    b = min(b, a-b)
    c = 1
    for i in range(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

#print(a,b)
print(N) #文字列1
for k in range(2, N):
    #tmp1 = nCr(N+1, k)
    #tmp2 = nCr(N-1+a-b, k-1)
    #tmp1 = C(N+1, k)
    #tmp2 = C(N-1+a-b, k-1)
    tmp1 = modc(N+1, k, MOD)
    tmp2 = modc(N-1+a-b, k-1, MOD)
    #print(tmp1, tmp2)
    print(tmp1-tmp2)
print(N+1) #文字列N
print(1) #文字列N+1

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter

# 参考サイト
# http://arc058.contest.atcoder.jp/data/arc/058/editorial.pdf

N = int(input())
As = list(map(int, input().split()))
cnt = Counter(As)
dup, _ = cnt.most_common(1)[0]
# print(cnt.most_common(1)[0])
a = As.index(dup) #重複数字の最初の場所
As[a] = -1
b = As.index(dup) #重複数字の次の場所

MOD = 1000000007

if N == 1:
    print(1)
    print(1)
    exit()


# def nCr(n, r):
#     # 10C7 = 10C3
#     r = min(r, n-r)
#     # Calculate the numerator.
#     numerator = 1
#     for i in range(n, n-r, -1):
#         numerator *= i
#     for i in range(r, 1, -1):
#         numerator //= i
#     return numerator
def modc(a,b,m):
    c = 1
    for i in range(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

#print(a,b)
print(N) #文字列1
for k in range(2, N):
    #tmp1 = nCr(N+1, k)
    #tmp2 = nCr(N-1+a-b, k-1)
    #tmp1 = C(N+1, k)
    #tmp2 = C(N-1+a-b, k-1)
    tmp1 = modc(N+1, k, MOD)
    tmp2 = modc(N-1+a-b, k-1, MOD)
    #print(tmp1, tmp2)
    print(tmp1-tmp2)
print(N+1) #文字列N
print(1) #文字列N+1

Submission status: Wrong Answer

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

def comb(n,r):
    ans = 0
    if n < r:
        pass
    elif n <= 0 or r <= 0:
        ans = 1
    else:
        i = 0
        x = 1
        while i < r:
            x = x * (n-i)
            i += 1
        i = 0
        y = 1
        while i < r:
            y = y * (i+1)
            i += 1
        ans = x / y
    return(ans)


n = raw_input()
n = int(n)


a = raw_input()
a = a.split()
a = map(int,a)
a = np.array(a,dtype=np.int64)

if n == 1:
    print "1"
else:
    i = 0
    while i < n + 1:
        if np.where(a==i)[0].size == 2:
            d = np.where(a==i)[0]
        i += 1

    d[1] = n-d[1]
    d = sum(d)

    i = 0
    while i < n + 1:
        #ans = kai(n+1) / (kai(i+1)*kai(n-i)) - kai(d) / ((kai(i))*kai(d-i))
        ans = comb(n+1,i+1) - comb(d,i)
        ans = ans % (10 ** 9 + 7)
        print ans
        i += 1

Submission status: Wrong Answer

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

def comb(n,r):
    ans = 0
    if n < r:
        pass
    elif n <= 0 or r <= 0:
        ans = 1
    else:
        i = 0
        x = 1
        while i < r:
            x = x * (n-i)
            i += 1
        i = 0
        y = 1
        while i < r:
            y = y * (i+1)
            i += 1
        ans = x / y
    return(ans)


n = raw_input()
n = int(n)


a = raw_input()
a = a.split()
a = map(int,a)
a = np.array(a,dtype=np.int64)

if n == 1:
    print 1
else:
    i = 0
    while i < n + 1:
        if np.where(a==i)[0].size == 2:
            d = np.where(a==i)[0]
        i += 1

    d[1] = n-d[1]
    d = sum(d)

    i = 0
    while i < n + 1:
        #ans = kai(n+1) / (kai(i+1)*kai(n-i)) - kai(d) / ((kai(i))*kai(d-i))
        ans = comb(n+1,i+1) - comb(d,i)
        ans = ans % (10 ** 9 + 7)
        print ans
        i += 1

Submission status: Wrong Answer

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

def kai(n):
    if n <= 0:
        return(1)
    else:
        j = n
        while j > 1:
            j -= 1
            n = n * j
        return(n)

n = raw_input()
n = int(n)


a = raw_input()
a = a.split()
a = map(int,a)
a = np.array(a,dtype=np.int64)

if n == 1:
    print 1
else:
    i = 0
    while i < n + 1:
        if np.where(a==i)[0].size == 2:
            d = np.where(a==i)[0]
        i += 1

    d[1] = n-d[1]
    d = sum(d)

    i = 0
    while i < n + 1:
        ans = kai(n+1) / (kai(i+1)*kai(n-i)) - kai(d) / ((kai(i))*kai(d-i))
        ans = ans % (10 ** 9 + 7)
        print ans
        i += 1

Submission status: Wrong Answer

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

def kai(n):
    if n <= 0:
        return(1)
    else:
        j = n
        while j > 1:
            j -= 1
            n = n * j
        return(n)

n = raw_input()
n = int(n)

a = raw_input()
a = a.split()
a = map(int,a)
a = np.array(a,dtype=np.int64)

i = 0
while i < n + 1:
    if np.where(a==i)[0].size == 2:
        d = np.where(a==i)[0]
    i += 1

d[1] = n-d[1]
d = sum(d)

i = 0
while i < n + 1:
    ans = kai(n+1) / (kai(i+1)*kai(n-i)) - kai(d) / ((kai(i))*kai(d-i))
    ans = ans % (10 ** 9 + 7)
    print ans
    i += 1

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[int(i) for i in input().split()]
for i in range(1,n+1):
    k=s.count(i)
    if k==2:
        a=s.index(i)
        b=s.index(i,a+1)
f=[1]
t=1
for i in range(1,n+2):
    t=t*i
    f.append(t)


for i in range(1,n+2):
    x=round(f[n+1]/(f[i]*f[n+1-i]))
    y=round(f[a+n-b]/(f[i-1]*f[a+n-b-i+1]))
    print(x-y)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb

n=int(input())
s=[int(i) for i in input().split()]
for i in range(1,n+1):
    k=s.count(i)
    if k==2:
        a=s.index(i)
        b=s.index(i,a+1)

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

Submission status: Wrong Answer

Solution code:
import scipy.misc as scm
from collections import Counter

n=int(input())
s=[int(i) for i in input().split()]
c = Counter(s)
j=-1
for i in range(1, n + 1):
    if c[i] == 2:
        j = i
        break
a,b = [i for i in range(n + 1) if s[i] == j]

for i in range(1,n+2):
    print(scm.comb(n+1,i,1)-scm.comb(a+n-b,i-1,1))

Submission status: Wrong Answer

Solution code:
import scipy.misc as scm
import sys

n=int(input())
s=[int(i) for i in input().split()]
for i in range(1,n+1):
    k=s.count(i)
    if k==2:
        a=s.index(i)
        b=s.index(i,a+1)
        print(a,b)

for i in range(1,n+2):
    print(scm.comb(n+1,i,1)-scm.comb(a+n-b,i-1,1))

Submission status: Wrong Answer

Solution code:
import scipy.misc as scm
import sys

n=int(input())
s=[int(i) for i in input().split()]
for i in range(1,n+1):
    k=s.count(i)
    if k==2:
        a=s.index(i)
        b=s.index(i,a+1)
        print(a,b)
z=a+n-b
print(z)
if n==1:
    print(1)
    print(1)
    sys.exit()
if n==2:
    print(2)
    print(scm.comb(n+1,i,1)-z)
    print(1)
    sys.exit()

for i in range(1,n+1):
    ans=scm.comb(n+1,i,1)
    if z>=i-1:
        ans=ans-scm.comb(z,i-1,1)
    fa=ans%(10**9+7)
    print(fa)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int,stdin.readline().split()))

MOD = 10**9+7

class Comb:
    def __init__(self, size):
        self.fact = [0 for i in range(size + 1)]
        self.inv_fact = [0 for i in range(size + 1)]
        self.factrical(size)

    def nCr(self, n,r):
        ret = self.fact[n]
        ret *= self.inv_fact[n-r]
        ret %= MOD
        ret *= self.inv_fact[r]
        ret %= MOD
        return ret

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

    def inv(self, a):
        return pow(a, MOD-2, MOD)

N = ni()
a = na()
c = [-1 for i in range (N)]
index = [-1,-1]

for i, x in enumerate(a):
    if (c[x-1]!=-1):
        index[0] = c[x-1]
        index[1] = i
        break

    c[x-1] = i

co = Comb(N+1)
for i in range(1, N+2):
    ans = co.nCr(N+1,i)
    if ((N-index[1]) + (index[0])>=i-1 ):
        ans -= co.nCr((N-index[1]) + (index[0]),i-1) 
    
    print (ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int,stdin.readline().split()))

MOD = 10**9+7

class Comb:
    def __init__(self, size):
        self.fact = [0 for i in range(size + 1)]
        self.inv_fact = [0 for i in range(size + 1)]
        self.factrical(size)

    def nCr(self, n,r):
        ret = self.fact[n]
        ret *= self.inv_fact[n-r]
        ret %= MOD
        ret *= self.inv_fact[r]
        ret %= MOD
        return ret

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

    def inv(self, a):
        return pow(a, MOD-2, MOD)

N = ni()
a = na()
c = [-1 for i in range (N)]
index = [-1,-1]

for i, x in enumerate(a):
    if (c[x-1]!=-1):
        index[0] = c[x-1]
        index[1] = i
        break

    c[x-1] = i

co = Comb(N+1)
print (co.fact[N])
for i in range(1, N+2):
    ans = co.nCr(N+1,i)
    if ((N-index[1]) + (index[0])>=i-1 ):
        ans -= co.nCr((N-index[1]) + (index[0]),i-1) 
    
    print (ans)