Problem:


Score : 600 points

Problem Statement

You are given an integer sequence of length n+1, a_1,a_2,...,a_{n+1}, which consists of the n integers 1,...,n.
It is known that each of the n integers 1,...,n appears at least once in this sequence.

For each integer k=1,...,n+1, find the number of the different subsequences (not necessarily contiguous) of the given sequence with length k, modulo 10^9+7.

Notes

If the contents of two subsequences are the same, they are not separately counted even if they originate from different positions in the original sequence.

A subsequence of a sequence a with length k is a sequence obtained by selecting k of the elements of a and arranging them without changing their relative order. For example, the sequences 1,3,5 and 1,2,3 are subsequences of 1,2,3,4,5, while 3,1,2 and 1,10,100 are not.

Constraints

1 \leq n \leq 10^5

1 \leq a_i \leq n

Each of the integers 1,...,n appears in the sequence.

n and a_i are integers.

Input

Input is given from Standard Input in the following format:

n
a_1 a_2 ... a_{n+1}

Output

Print n+1 lines.
The k-th line should contain the number of the different subsequences of the given sequence with length k, modulo 10^9+7.

Sample Input 1

3
1 2 1 3

Sample Output 1

3
5
4
1

There are three subsequences with length 1: 1 and 2 and 3.

There are five subsequences with length 2: 1,1 and 1,2 and 1,3 and 2,1 and 2,3.

There are four subsequences with length 3: 1,1,3 and 1,2,1 and 1,2,3 and 2,1,3.

There is one subsequence with length 4: 1,2,1,3.

Sample Input 2

1
1 1

Sample Output 2

1
1

There is one subsequence with length 1: 1.

There is one subsequence with length 2: 1,1.

Sample Input 3

32
29 19 7 10 26 32 27 4 11 20 2 8 16 23 5 14 6 12 17 22 18 30 28 24 15 1 25 3 13 21 19 31 9

Sample Output 3

32
525
5453
40919
237336
1107568
4272048
13884156
38567100
92561040
193536720
354817320
573166440
818809200
37158313
166803103
166803103
37158313
818809200
573166440
354817320
193536720
92561040
38567100
13884156
4272048
1107568
237336
40920
5456
528
33
1

Be sure to print the numbers modulo 10^9+7.



Sample input:
3
1 2 1 3


Sample output:
3
5
4
1

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
INF = float("inf")

MOD = 1000000007  # type: int


class Combination(object):
    def __init__(self, N, mod):
        self.N = N
        self.MOD = mod
        self.fac = [0] * (N+1)
        self.finv = [0] * (N+1)
        self.inv = [0] * (N+1)
        self.cmb_init()

    def cmb_init(self):
        self.fac[0] = 1
        self.fac[1] = 1
        self.finv[0] = 1
        self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, self.N+1):
            self.fac[i] = self.fac[i-1]*i % self.MOD
            self.inv[i] = -self.inv[self.MOD % i]*(self.MOD//i) % self.MOD
            self.finv[i] = self.finv[i-1]*self.inv[i] % self.MOD

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


def solve(n: int, a: "List[int]"):
    (m, _), = Counter(a).most_common(1)
    left = a.index(m)
    right = a.index(m, left+1)
    cmb = Combination(n+1, MOD)
    for i in range(1, n+2):
        print((cmb(n+1, i)-cmb(n-right+left, i-1)) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(n+1)]  # type: "List[int]"
    solve(n, a)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

fact = [1 for _ in range(N + 10)]
invFact = [0 for _ in range(N + 10)]

def modInv(a):
    b = MOD
    u = 1
    v = 0
    while b :
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= MOD
    return u

for i in range(1, N + 10):
    fact[i] = (fact[i - 1] * i) % MOD
    invFact[i] = modInv(fact[i])

index = [[] for _ in range(N + 1)]

for i, a in enumerate(A):
    index[a].append(i)

left = 0
right = 0
for count in index:
    if len(count) == 2:
        left = min(count)
        right = max(count)

def comb(n, r):
    if 0 < r < n:
        return (fact[n] * invFact[r] % MOD) * invFact[n - r] % MOD
    if r == 0 or r == n:
        return 1
    return 0

les = left + (N - right)

for k in range(1, N + 2):
    r = comb(les, k - 1)
    ans = comb(N + 1, k) - r
    print(ans % MOD)

Submission status: Accepted

Solution code:
import collections
n=int(input())
A=[int(i) for i in input().split()]
a=collections.Counter(A).most_common()[0][0]
AA=[i for i, x in enumerate(A) if x==a]
a1,a2,d=AA[0],AA[1],AA[1]-AA[0]

mod=10**9+7
n_max=2*10**5
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

for i in range(n+1):
  ans=comb(n+1,i+1)%mod
  if 0<=i<=a1+n-a2:
    ans-=comb(a1+n-a2,i)
  print(ans%mod)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a_list=list(map(int,input().split()))
num=[[] for i in range(n)]
for i in range(n+1):
    num[a_list[i]-1].append(i)
for i in num:
    if len(i)==2:
        x=i[0]
        y=n-i[1]
INF=10**9+7
z=x+y
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m
a=n+1
b=1
for i in range(n+1):
    print((a-b)%INF)
    a=(a*(n-i)*modinv(i+2,INF))%INF
    b=(b*(z-i)*modinv(i+1,INF))%INF

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
SIZE=300000; MOD=10**9+7 #998244353 #ここを変更する

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

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


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())
a = [int(i)-1 for i in readline().split()]

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

#print(p,q)

"""
for k in range(1,n+2):
    res = 0
    for l in range(k):
        res += choose(p,l)*choose(q,k-1-l)
    
    print((choose(n+1,k) - res)%MOD)
"""

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
N, mod = 10**5+1, 10**9+7
fac = [1, 1] + [None] * N
inv = [0, 1] + [None] * N
facInv = [1, 1] + [None] * N
for i in range(2, N+1):
    fac[i] = i*fac[i-1]%mod
    inv[i] = mod-(inv[mod%i]*(mod//i))%mod
    facInv[i] = facInv[i-1]*inv[i]%mod
def modCom(n, k):
    return 0 if n < k else fac[n] * facInv[k] * facInv[n-k] % mod
n = int(input())
a = list(map(int, input().split()))
dic = defaultdict(int)
for i, x in enumerate(a):
    if dic[x] > 0:
        fi = dic[x]
        si = i+1
        break
    dic[x] = i+1
print(n)
for k in range(2, n+1):
    print((modCom(n+1, k) - modCom(fi+n-si, k-1)) % mod)
print(1)

Submission status: Accepted

Solution code:
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD

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

L = [-1] * (n + 1)
for i in range(n + 1):
  if L[a[i]] == -1:
    L[a[i]] = i
  else:
    l = L[a[i]]
    r = i

s = n - r + l
com = comb(n + 1, MOD)
for i in range(1, n + 2):
  #lrを使わない
  if i < n:
    ans = com.com(n - 1, i)
  else:
    ans = 0
  #lrのうち片方を使う
  if 1 <= i <= n:
    ans+= com.com(n - 1, i - 1) * 2
    if i - 1 <= s:
      ans -= com.com(s, i - 1)
    ans %= MOD
  #lrを両方使う
  if 1 < i:
    ans = (ans + com.com(n - 1, i - 2)) % MOD
  print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
mod=10**9+7
c=[-1]*(n+1)
for i,j in enumerate(l,1):
    if(c[j]==-1):
        c[j]=i
    else:
        i1,i2=c[j],i
        break
fra=[1]*(n+2)
inv=[1]*(n+2)
c=1
t=1
for i in range(1,n+2):
    c*=i
    c%=mod
    t*=pow(i,mod-2,mod)
    t%=mod
    fra[i]=c
    inv[i]=t
def comb(n,r):
    return fra[n]*inv[n-r]*inv[r]%mod
for i in range(1,n+2):
    t=n-i2+i1
    if t+1<i:
        print(comb(n+1,i))
    else:
        print((comb(n+1,i)-comb(t,i-1))%mod)

Submission status: Accepted

Solution code:
mod = 10**9+7
fact = [1]*(10**5+2)
for n in range(1,10**5+2):
    fact[n] = n*fact[n-1]%mod
def comb(n,k):
    return fact[n]*pow(fact[k],mod-2,mod)*pow(fact[n-k],mod-2,mod)%mod

N = int(input())
a = list(map(int,input().split()))
c = [-1]*N
for j in range(N+1):
    if c[a[j]-1] != -1:
        break
    c[a[j]-1] = j
i = c[a[j]-1]
j = N-j

for k in range(1,N+2):
    ans = comb(N+1,k)
    if k-1<=i+j:
        ans -= comb(i+j,k-1)
    print(ans%mod)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]
mod = 10**9 + 7

f = [1] * (N + 2)
fi = [1] * (N + 2)
for i in range(2, N + 2):
    f[i] = i * f[i - 1]
    f[i] %= mod
for i in range(2, N + 2):
    fi[i] = fi[i - 1] * pow(i, mod - 2, mod)
    fi[i] %= mod


def comb(n, r):
    if 0 <= n and 0 <= r and 0 <= n - r:
        return (f[n] * fi[r] * fi[n - r]) % mod
    else:
        return 0


b = set()
for a in A:
    if a in b:
        break
    b.add(a)
c = []
for i in range(N + 1):
    if A[i] == a:
        c += [i]
i, j = c
for x in range(1, N + 2):
    print((comb(N + 1, x) - (comb(N - j + i, x - 1))) % mod)

Submission status: Accepted

Solution code:
from collections import Counter, deque, defaultdict
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7
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
 
size = 2*10**5 + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD


N = int(input())
A = inpl()
C = Counter(A)
for k, v in C.items():
    if v == 2:
        break
l = A.index(k)
r = N - A[::-1].index(k)

d = r - l - 1

print(N)
print((1 + N-1 + d + cmb(N-1, 2, MOD))%MOD)
for k in range(3, N+2):
    X = cmb(N-1, k-1, MOD)
    Y = cmb(N-1-d, k-1, MOD)
    Z = X - Y
    tmp = cmb(N-1, k, MOD) + Y + 2*Z + cmb(N-1, k-2, MOD)
    print(tmp%MOD)

Submission status: Accepted

Solution code:
import collections

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

c = collections.Counter(a)
dup = c.most_common()[0][0]

id = [i for i, x in enumerate(a) if x == dup]
L = id[0]
R = id[1]

MOD = 10**9 +7
factorial = [1]
inverse = [1]

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

def C(n, r):
    if n < r:
        return 0
    return (factorial[n] * inverse[r] * inverse[n-r]) % MOD

print(N)
for i in range(2, N+2):
    ans = (C(N+1, i) - C(L+(N-R), i-1)) % MOD
    print(ans)

Submission status: Accepted

Solution code:
# 基本的に重複がない
# n+1Ck − (n+1)-(r-l+1)Ck−1

MOD = 10**9+7
U = 10**5 + 1

def power_mod(a,n):
  if n == 0:
    return 1
  x = (power_mod(a,n//2)**2)%MOD
  return x if n%2 == 0 else (a*x)%MOD

def make_fact(fact,fact_inv):
  for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
  fact_inv[U] = power_mod(fact[U],MOD-2)
  for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n,k):
  if k < 0 or k > n:
    return 0
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x

fact = [1]*(U+1)
fact_inv = [1]*(U+1)
make_fact(fact,fact_inv)

# 重複の起きる場所の間隔だけが問題
n = int(input())
A = [int(x) for x in input().split()]

memo = dict()
d = 0
for i,x in enumerate(A):
  if x in memo:
    d = i - memo[x]
    break
  memo[x] = i

rest = n-d

for k in range(1,n+2):
  ans = comb(n+1,k) - comb(rest,k-1)
  ans %= MOD
  print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,*a=map(int,open(0).read().split())
    mod=10**9+7
    b=Counter(a).most_common()[0][0]
    l=a.index(b)
    r=a.index(b,l+1)
    n+=1
    nd=l+n-r-1
    
    inv=[0]*(n+1)
    inv[1]=1
    for i in range(2,n+1):
        inv[i]=(-(mod//i)*inv[mod%i])%mod
    tmp=n
    tmp2=1
    print(n-1)
    for i in range(2,n+1):
        tmp=(tmp*(n-i+1)*inv[i])%mod
        tmp2=(tmp2*(nd-i+2)*inv[i-1])%mod
        print((tmp-tmp2)%mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    class BigCombination(object):
        __slots__=["mod", "factorial", "inverse"]

        def __init__(self, mod: int=10**9+7, max_n: int=10**6):
            fac, inv=[1], []
            fac_append, inv_append=fac.append, inv.append

            for i in range(1, max_n+1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod-2, mod))

            for i in range(max_n, 0, -1):
                inv_append(inv[-1] * i % mod)

            self.mod, self.factorial, self.inverse=mod, fac, inv[::-1]

        def get_combination(self, n, r):
            if n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod
    N = I()
    A = LI()
    d = dict()
    BC = BigCombination()
    comb = BC.get_combination
    for i, a in enumerate(A):
        if a in d:
            dabu=(i, d[a])
            break
        else:
            d[a] = i
    out = min(dabu) + N - max(dabu)
    for k in range(1, N + 2):
        ans = comb(N + 1, k) - comb(out, k - 1)
        print(ans%mod)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def factorials(M):#M!までのリストｘと其の逆元のリストyを返すmod INF
    INF=int(1e9+7)
    fac=[0]*(M+1)
    finv=[0]*(M+1)
    inv=[0]*(M+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,M+1):
        fac[i]=(fac[i-1]*i)%INF
        inv[i]=INF-(inv[INF%i]*(INF//i))%INF
        finv[i]=finv[i-1]*inv[i]%INF
    return fac,finv
def nCr(n,r):
    INF=int(1e9+7)
    if n<r or r<0 or n<0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%INF)%INF

N=int(input())
fac,finv=factorials(N+1)
A=list(map(int,input().split()))
INF=int(1e9+7)
d=[0]*(N+1)
for i in A:
    d[i]+=1
key=-1
for i in range(1,N+1):
    if d[i]==2:
        key=i
a,b,c=0,0,0
t=0
for i in range(N+1):
    if key==A[i]:
        t+=1
    elif t==0:
        a+=1
    elif t==1:
        b+=1
    elif t==2:
        c+=1
for i in range(1,N+2):
    if i==1:
        print(N)
        continue

    print((nCr(N+1,i)-nCr(a+c,i-1))%INF)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def mod_invs(max, mod):
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def get_ncrs(n):
    invs = mod_invs(N + 1, MOD)
    ret = [1]
    ncr = 1
    for i in range(1, n + 1):
        ncr = ((ncr * (n - i + 1) % MOD) * invs[i]) % MOD
        ret.append(ncr)
    return ret


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

# dup より端から i 個選ぶ組み合わせ
side_ncrs = get_ncrs(L + N - r)
while len(side_ncrs) < N + 2:
    side_ncrs.append(0)

# 全部選んで選びすぎを引く
# dup を 1 つ選び、その他を dup より端から選ぶ組み合わせが重複する
ans_ncrs = get_ncrs(N + 1)
while len(ans_ncrs) < N + 2:
    ans_ncrs.append(0)
ans = [(ans_ncrs[k] - side_ncrs[k - 1]) % MOD for k in range(1, N + 2)]

print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
class BigCombination(object):
    __slots__ = ["mod", "factorial", "inverse"]

    def __init__(self, mod: int = 10**9+7, max_n: int = 10**6):
        fac, inv = [1], []
        fac_append, inv_append = fac.append, inv.append

        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

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

    def get_permutation(self, n, r):
        return self.factorial[n] * self.inverse[n-r] % self.mod

N = int(input())
A = [int(x) for x in input().split()]
se = []
c = sum(A) - N * (N + 1) / 2
for i in range(len(A)):
    if A[i] == c:
        se.append(i)
l = se[0]
r = se[1]
import math
mod = 10**9+7
print(N)
Big = BigCombination()

for i in range(2,N+2):
    k = Big.get_combination(N+1, i)
    
    t = Big.get_combination(l+N-r,i-1)
    res  = k -t
    print(res%mod)

Submission status: Accepted

Solution code:
mod = 10**9+7
N = int(input())
A = [int(x) for x in input().split()]
se = []
c = sum(A) - N * (N + 1) / 2
for i in range(len(A)):
    if A[i] == c:
        se.append(i)
l = se[0]
r = se[1]
import math

print(N)

factorial = [1]
inverse = [1]
for i in range(1, N + 2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append((pow(factorial[-1], mod - 2, 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 i in range(2,N+2):
    k = nCr(N+1, i)
    
    t = nCr(l+N-r,i-1)
    res  = k -t
    print(res % mod)

Submission status: Accepted

Solution code:
N = int(input())
li =  [ int(it) -1 for it in input().split() ] 

import sys
sys.setrecursionlimit(10000000)

from functools import lru_cache
MOD = 1000000007
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)
@lru_cache(maxsize=None)
def modinv(a):
    (inv, q, gcd_val) = egcd(a, MOD)
    return inv % MOD

fac_li = [0]*( 1000009 )
if True:
  s = 1
  for i in range(1,1000001):
    s = (s*i)%MOD
    fac_li[i] = s
def factorial(k):
  if (k<=1):
    return 1
  return fac_li[k]
@lru_cache(maxsize=None)
def combination(n,m):
  return (factorial(n)*modinv(factorial(m))*modinv(factorial(n-m)))%MOD

#print ( factorial(5),factorial(3) )
#print ( combination(5,3) )

import collections as col
c = col.Counter( li ).items()
a = [ it for it in c if it[1] == 2][0][0]
p1 = li.index(a)
p2 = li[p1+1:].index(a) + 1 + p1
#print ( p1 , p2 )
H = p1 + (N-p2)
#print ( H )

li=[]
for i in range(1,N+2):
  a =  (combination(N+1,i) - (combination(H,i-1)if (i-1)<=H else 0))%MOD
  li.append(a)
print ( "\n".join( map(str,li) ) )

Submission status: Accepted

Solution code:
n=int(input())
*A,=map(int,input().split())

cnt = [0]*n
for i,a in enumerate(A):
    a -= 1
    if cnt[a] == 0:
        cnt[a] = i+1
    else:
        N = i-cnt[a] #同じ数に挟まれている数字の数

p = 10**9+7
fac = [1]*n
inv = [1]*n
finv = [1]*n
for i in range(2,n):
    fac[i] = (fac[i-1]*i) %p
    inv[i] = (-inv[p%i]*(p//i)) %p
    finv[i] = (finv[i-1]*inv[i]) %p
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]%p)%p

for k in range(1,n+1):
    print((comb(n-1,k)+comb(n-1,k-2)+(comb(n-1,k-1)*2-comb(n-1-N,k-1)))%p)
print(1)

Submission status: Accepted

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

mod = 10**9+7

class combinationmod():
  def __init__(self,MAX, mod):
    self.mod =mod
    self.fac=[0]*(MAX+1)
    self.finv=[0]*(MAX+1)
    self.inv=[0]*(MAX+1)
    self.fac[0]=self.fac[1]=1
    self.finv[0]=self.finv[1]=1
    self.inv[1]=1
    for i in range(2,MAX+1):
      self.fac[i] = self.fac[i-1]*i%self.mod
      self.inv[i] = (-self.inv[mod%i]*(mod//i))%self.mod
      self.finv[i] = self.finv[i-1]* self.inv[i] %self.mod

  def nCk(self,n,k):
    if n<k or n<0 or k<0:
      return 0
    return self.fac[n]*(self.finv[k]*self.finv[n-k]%self.mod)%self.mod
  
memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
c = combinationmod(n+1,mod)
for k in range(1,n+2):
  print((c.nCk(n+1,k) - c.nCk(L+R,k-1))%mod)

Submission status: Accepted

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

mod = int(1e9+7)
def invmod(a, mod):
    if a==1:
        return 1
    return -invmod(mod%a, mod) * (mod//a) %mod


memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [0]*(n+3)
_LCR = [0] * (n+3) # _LCR[k] = (L+C+R)C(k)
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) #LR[k] = (L+R)C(k)
LR[0] = 1
#LDR = [0]*(n+2)
#LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
#LDCR = [0] * (n+2) #最後に*2を忘れないこと
#LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * invmod(k,mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
#  LDR[k] = LR[k-1]
#  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]
#  LDCR[k] = LCR[k-1]
#  LDCDR[k] = LDCR[k-1]
  #print(LR, LCR)
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

Submission status: Accepted

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

mod = int(1e9+7)
def powermod(a, n, mod):
    r = 1
    while n>=1:
        if n%2:
            r = (r*a)%mod
        a = (a*a)%mod
        n = n//2
    return r
  
memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [0]*(n+3)
_LCR = [0] * (n+3) # _LCR[k] = (L+C+R)C(k)
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) #LR[k] = (L+R)C(k)
LR[0] = 1
#LDR = [0]*(n+2)
#LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
#LDCR = [0] * (n+2) #最後に*2を忘れないこと
#LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * powermod(k, mod-2, mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
#  LDR[k] = LR[k-1]
#  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]
#  LDCR[k] = LCR[k-1]
#  LDCDR[k] = LDCR[k-1]
  #print(LR, LCR)
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

Submission status: Accepted

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

mod = int(1e9+7)
def powermod(p,n,mod):
    #if n==0: return 1
    if n==1:
        return p%mod
    if n%2:
        return powermod(p,n//2,mod)**2 * p %mod
    else:
        return powermod(p,n//2,mod)**2 %mod


memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [0]*(n+3)
_LCR = [0] * (n+3) # _LCR[k] = (L+C+R)C(k)
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) #LR[k] = (L+R)C(k)
LR[0] = 1
#LDR = [0]*(n+2)
#LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
#LDCR = [0] * (n+2) #最後に*2を忘れないこと
#LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * powermod(k, mod-2, mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
#  LDR[k] = LR[k-1]
#  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]
#  LDCR[k] = LCR[k-1]
#  LDCDR[k] = LDCR[k-1]
  #print(LR, LCR)
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7



n = int(input())
a = [int(i) for i in input().split()]


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))

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

A = copy.deepcopy(a)
A.sort()
for i in range(n+1):
    if A[i] == A[i+1]:
        double = A[i]
        break

cnt = 0
for i in range(n+1):
    if a[i] == double:
        if cnt == 0:
            l = i+1
            cnt += 1
        else:
            r = i+1
# print(l,r)
for k in range(1,n+2):
    # print(n+1,k,l+n-r,k-1)
    ans = (combinations_count(n+1,k)-combinations_count((l+n-r),(k-1)))%mod
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
mod = 10 **9 + 7


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


X = Counter(A).most_common(1)[0][0]
X_index = []
for i, a in enumerate(A, start=1):
    if a == X:
        X_index.append(i)
L, R = X_index[0], X_index[1]

for k in range(1, N + 2):
    if k == 1:
        print(N)
    else:
        print((nCr(N + 1, k) - nCr(N - R + L, k - 1)) % mod)

Submission status: Accepted

Solution code:
n = int(input()) + 1
a = [int(item) for item in input().split()]
MOD = 10**9 + 7

def mod_pow(x, n):
    ans = 1
    while(n != 0):
        if n & 1:
            ans = ans * x % MOD
        x = x * x % MOD
        n = n >> 1
    return ans

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

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = inv_fac[n-r] * inv_fac[r] % MOD
    return tmp * fac[n] % MOD 

index = [-1] * (n+1)
l, r = 0, 0
for i, c in enumerate(a):
    if index[c] == -1:
        index[c] = i
    else:
        l = index[c]
        r = i

for i in range(1, n+1):
    total = mod_nCr(n, i)
    doubled = mod_nCr(n -(r-l) - 1, i-1)
    ans = total - doubled
    if ans < 0:
        ans += MOD
    print(ans)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    factrial = [1] * (N+2)
    for k in range(1, N+2):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (N+2)
    fact_inv[N+1] = pow(factrial[N+1], MOD - 2, MOD)
    for k in range(N, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    def comb(n, r, MOD):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD

    m = first + (N - second)
    for i in range(1, N+2):
        ans = comb(N+1, i, MOD) - comb(m, i-1, MOD)
        print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
d = {}
L, R = -1, -1
for i in range(n + 1):
    if a[i] in d:
        L = d[a[i]] + 1
        R = i + 1
        break
    else:
        d[a[i]] = i

MOD = 10 ** 9 + 7
M = 100005
fact = [0] * M
fact[0] = 1
for i in range(1, M):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

rfact = [0] * M
rfact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(M - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1)
    rfact[i] %= MOD

def comb(x, y):
    if x < 0 or y < 0 or x < y:
        return 0
    return fact[x] * rfact[y] * rfact[x - y] % MOD


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

Submission status: Accepted

Solution code:
def mod_inv(n: int, mod: int)->int:
    b, u, v = mod, 1, 0
    while b > 0:
        t = n // b

        n -= t * b
        u -= t * v

        n, b = b, n
        u, v = v, u

    return (u+mod) % mod


def _11(N: int, A: list)->list:
    MOD = 10**9 + 7

    d = {}
    l, r = 0, 0
    for i, a in enumerate(A):
        if a in d:
            l, r = d[a], N-i
        else:
            d[a] = i

    c1, c2 = [1]*(N+2), [1]*(N+2)
    for i in range(N+1):
        c1[i+1] = (c1[i] * (N+1-i) * mod_inv(i+1, MOD)) % MOD
        c2[i+1] = (c2[i] * (l+r-i) * mod_inv(i+1, MOD)) % MOD

    return [(c1[k+1]-c2[k]+MOD) % MOD for k in range(N+1)]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _11(N, A)
    print('\n'.join(map(str, ans)))