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:
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  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
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())#10 ** 5
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

count = [0] * (n)
for i in range(n + 1):
  count[A[i] - 1] += 1
  #print(count)
mm = count.index(max(count)) + 1
#print(mm)

m1 = A.index(mm)
m2 = A[m1 + 1:].index(mm) + m1 + 1
#print(m1, m2)

ans = [0] * (n + 1)
for i in range(n + 1):
  ans[i] = cmb(n + 1, i + 1, p) - cmb(n - m2 + m1, i, p)
  
for i in range(n + 1):  
  print(ans[i] % p)

Submission status: Accepted

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

Submission status: Accepted

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

# 1を一つだけ選ぶやつは重複する可能性
d = [False] * (n + 1)

left = right = 0
for i in range(n):
    if d[a[i]]:
        right = i
        left = a.index(a[i])
        break
    d[a[i]] = True


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


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


def c(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return fac[n] * inv(fac[n - k] * fac[k] % mod) % mod


left_len = left
right_len = n - right - 1
print(n - 1)
for i in range(2, n + 1):
    ans = c(n, i) - c(left_len + right_len, i - 1)
    print(ans % mod)

Submission status: Accepted

Solution code:

from collections import defaultdict
n = int(input()) + 1
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

# 1を一つだけ選ぶやつは重複する可能性
d = defaultdict(int)

left = right = 0
for i in range(n):
    if d[a[i]] > 0:
        right = i
        left = a.index(a[i])
        break
    d[a[i]] += 1


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


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


def c(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return fac[n] * inv(fac[n - k] * fac[k] % mod) % mod


left_len = left
right_len = n - right - 1
print(n - 1)
for i in range(2, n + 1):
    ans = c(n, i) - (c(left_len + 1 + right_len, i) -
                     c(left_len + right_len, i))
    print(ans % mod)

Submission status: Accepted

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

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

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

r = n-r

#print(l, r)

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

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

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

Submission status: Accepted

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


mod = 10 ** 9 + 7
up = [1 for i in range(N+1)]
for i in range(2, N+1):
    up[i] = up[i-1]*i % mod
down = [1 for i in range(N+1)]
down[N] = pow(up[N], mod-2, mod)
for i in range(N-1, 0, -1):
    down[i] = (i+1)*down[i+1] % mod


def ncr(n, r):
    if not n >= r >= 0:
        return 0
    else:
        return up[n]*down[n-r]*down[r] % mod


duplicated_number, _cnt = Counter(a).most_common()[0]
index_que = []

for i in range(N+1):
    if a[i] == duplicated_number:
        index_que.append(i)
        
A, B = min(index_que), max(index_que)

for k in range(1, N+2):
    if k == 1:
        print(N)
    else:
        ans = ncr(N-1, k-2)+ncr(N-1, k)+2 * ncr(N-1, k-1)-ncr(N-B+A, k-1)
        print(ans % mod)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

dic = DD(int)
for i in range(1,N+2):
  a = A[i-1]
  if not dic[a]:
    dic[a] = i
  else:
    l,r = dic[a],i
    
for i in range(1,N+2):
  ans = nCr(N+1,i)
  ans -= nCr(N+l-r,i-1)
  print(ans%MOD)

Submission status: Accepted

Solution code:
from collections import Counter

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

cnt=Counter(a)

mod=10**9+7

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

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

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

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

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

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

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    pi = [-1]*(n+1)
    x1 = 0
    x2 = 0
    for i,ai in enumerate(a):
        if pi[ai] == -1:
            pi[ai] = i
        else:
            x1 = pi[ai]
            x2 = n-i
            break
    xt = x1+x2

    #nCrをmodで割った余りを求める。Nに最大値を入れて使用。
    N = n+1
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    def cmb(n,r,mod=(10**9+7)):
        if r<0 or r>n :
            return 0
        r = min(r,n-r)
        return g1[n]*g2[r]*g2[n-r]%mod
    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)-cmb(xt,i-1))%mod)


    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

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

def inv_mod(n):
  return pow(n, MOD-2, MOD)

FACTS = [1 for _ in range(MAX_NUM+1)]
for n in range(1, MAX_NUM+1):
  FACTS[n] = (n*FACTS[n-1]) % MOD

INV_FACTS = [1 for _ in range(MAX_NUM+1)]
INV_FACTS[MAX_NUM] = inv_mod(FACTS[MAX_NUM])
for n in range(MAX_NUM-1, -1, -1):
  INV_FACTS[n] = (INV_FACTS[n+1]*(n+1)) % MOD
  
for i in range(MAX_NUM+1):
  assert (FACTS[i]*INV_FACTS[i])%MOD == 1

def ncr(n, r):
  if r > n:
    return 0
  if r < 0:
    return 0
  # C(n, r) = n!/(n-r)!r!
  ans = FACTS[n]*INV_FACTS[n-r]*INV_FACTS[r]
  return ans % MOD

from collections import defaultdict
v2i = defaultdict(list)
for i, v in enumerate(A):
  v2i[v].append(i)

fst, snd = -1, -1
for v in v2i:
  if len(v2i[v]) == 2:
    fst, snd = v2i[v]

K = snd - fst - 1
for ell in range(1, N+2):
  ans = ncr(N+1, ell) - ncr(N-1-K, ell-1)
  print(ans%MOD)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

mod = 10**9 + 7
def cmb(n, r, p=mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

input = sys.stdin.readline
N = int(input())
A = list(map(int, sys.stdin.readline().split()))

fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 2):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

counter = Counter(A)
tmp = sorted(counter.items(), key = lambda x: x[1])
dup_n = tmp[-1][0]
# print(dup_n)

indices = [i for i, x in enumerate(A) if x == dup_n]
# print(indices)
left = indices[0]
right = indices[1]

print(cmb(N, 1))
for i in range(2, N+2):
# for i in range(1, N+2):
    tmp = cmb(N+1, i)
    tmp %= mod
    # 重複した数を含むパターン
    # print("debug", cmb(N+1, i), cmb(left, i-1), cmb(N - right, i-1))
    # print("debug", cmb(N+1, i), cmb(left + N - right, i-1))
    # if 1 < i: 
    #     tmp -= cmb(left, i-1) + cmb(N - right, i-1) 
    if 1 < i: 
        tmp -= cmb(left + N - right, i-1) 
    tmp %= mod
    print(tmp)
# print(cmb(N+1, N+1))

Submission status: Accepted

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

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

mod = 10 ** 9 + 7

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

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

Submission status: Accepted

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

mod = 10 ** 9 + 7
N = 100000

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

d = {}

# n1個 X n2個 X n3個
n1 = 0
n2 = 0
n3 = 0

for i, ai in enumerate(a):
    if ai not in d:
        d[ai] = i
    else:
        n1 = d[ai]
        n2 = i - d[ai] - 1
        n3 = n - i
        break

for i in range(1, n+2):
    ans = 0
    # Xを選ばない
    ans += cmb(n-1, i)
    # Xを2回選ぶ
    ans += cmb(n-1, i-2)
    # Xを1回選ぶ かつ Xの間からは選ばない
    ans += cmb(n-1-n2, i-1)
    # Xを1回選ぶ かつ Xの間から一つ以上選ぶ
    if i >= 2 and i <= n:
        ans += 2 * (cmb(n2+n1+n3, i-1) - cmb(n1+n3, i-1))

    print(ans % mod)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
A = [0] + LI()
mod = 10**9+7

count = [0]*(N+1)
for i in range(1,N+2):
    if count[A[i]] != 0:
        a,b = count[A[i]],i  # 重複する文字のあるindex
    else:
        count[A[i]] = i


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


def nCr(n,r):
    if n < r:
        return 0
    return (kaijou[n]*pow(kaijou[r],mod-2,mod)*pow(kaijou[n-r],mod-2,mod)) % mod


for k in range(1,N+2):
    print((nCr(N+1,k)-nCr(N+a-b,k-1)) % mod)

Submission status: Accepted

Solution code:
MOD = 10**9+7

class Combination:
    def __init__(self, n_max=10**6, mod=10**9+7):
        # self._n_max = n_max
        self._fac, self._finv, self._inv = [0]*n_max, [0]*n_max, [0]*n_max
        self._fac[0], self._fac[1] = 1, 1
        self._finv[0], self._finv[1] = 1, 1
        self._inv[1] = 1
        for i in range(2, n_max):
            self._fac[i] = self._fac[i - 1] * i % MOD
            self._inv[i] = MOD - self._inv[MOD%i] * (MOD // i) % MOD
            self._finv[i] = self._finv[i - 1] * self._inv[i] % MOD
    def com(self, n, r):
        if n < r: return 0
        if n < 0 or r < 0: return 0
        return self._fac[n] * (self._finv[r] * self._finv[n - r] % MOD) % MOD



def main():
    comb = Combination(10**5+10, MOD)
    n = int(input())
    al = list(map(int, input().split()))
    same_num = 0
    aset = set()
    for a in al:
        if a in aset: 
            same_num = a
            break
        else:
            aset.add(a)
    
    l,r = -1,-1
    for i, a in enumerate(al):
        if a == same_num:
            if l == -1: l = i
            else: r = i

    l = l
    r = (n+1)-r-1

    # l_coms = [0]*(l+1)
    # r_coms = [0]*(r+1)

    # for i in range(l+1):
    #     l_coms[i] = comb.com(l,i)
    # for i in range(r+1):
    #     r_coms[i] = comb.com(r,i)

    for k in range(1,n+2):
        all_cnt = comb.com(n+1,k)
        ng_cnt = comb.com(l+r,k-1)
        ans = all_cnt-ng_cnt
        ans %= MOD
        print(ans)

    # l_cnts = [0]*(l+1)
    # r_cnts = [0]*(r+1)
    # for 


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
A = [0] + LI()
mod = 10**9+7

count = [0]*(N+1)
for i in range(1,N+2):
    if count[A[i]] != 0:
        a = count[A[i]]
        b = i
    else:
        count[A[i]] = i


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


def nCr(n,r):
    if n < r:
        return 0
    return (kaijou[n]*pow(kaijou[r],mod-2,mod)*pow(kaijou[n-r],mod-2,mod)) % mod


for k in range(1,N+2):
    print((nCr(N+1,k)-nCr(N+a-b,k-1)) % mod)

Submission status: Accepted

Solution code:
class Factorials:
    # nに十分大きい数を入力
    def __init__(self, n, mod):
        self.mod = mod

        # self.fac[i] ≡ i! (factorial:階乗)
        self.fac = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            self.fac.append(num)

        # self.rec[i] ≡ 1 / i! (reciprocal:逆数)
        num = pow(num, mod-2, mod)
        self.rec = [1 for i in range(n+1)]
        self.rec[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            self.rec[i] = num

    # comb(n, r) ≡ nCr
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod
    
    # perm(n, r) ≡ nPr
    def perm(self, n, r):
        return self.fac[n] * self.rec[n-r] % self.mod

    # fact(n) ≡ n!
    def fact(self, n):
        return self.fac[n]

mod = 10**9 + 7

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

check = [-1] * n
for i in range(n+1):
    a[i] -= 1
    if check[a[i]] == -1:
        check[a[i]] = i
    else:
        m = n + check[a[i]] - i
        break

fct = Factorials(n+1, mod)

for i in range(1, n+2):
    if m >= i - 1:
        print((fct.comb(n+1, i) - fct.comb(m, i-1)) % mod)
    else:
        print(fct.comb(n+1, i))

Submission status: Accepted

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
m = 10**9+7
N = int(input())
A = list(map(int,input().split()))
B = (N+1)*[0]

for n in range(N+1):
  if B[A[n]]==0:
    B[A[n]]=n+1
  else:
    S = B[A[n]]+N-n-1
    break

p = 1
q = 1

for n in range(1,N+2):
  p = ((p*(N+2-n))*pow(n,m-2,m))%m
  q = (1 if n==1 and S>=n-1 else(0 if S<n-1 else ((q*(S-n+2))*pow(n-1,m-2,m)))%m)
  print((p-q)%m)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
place=[-1]*n
for i in range(n+1):
	if place[a[i]-1]==-1:
		place[a[i]-1]=i
	else:
		R=(place[a[i]-1],i)
		break
def c(a,b):
	if a==b==0:
		return 1
	if a<b or a<=0 or b<0:
		return 0
	r=fac[a-b]*fac[b]%mod
	return fac[a]*pow(r,mod-2,mod)%mod
fac=[1]
for i in range(n+1):
	fac.append(fac[-1]*(i+1)%mod)
for i in range(1,n+2):
	ans=(c(n+1,i)-c(R[0]+n-R[1],i-1))%mod
	print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    maxn=N
    fact=[1]*(maxn+1)#NはnCrの最大のn
    invs=[1]*(maxn+1);invs[0]=0
    ifact=[1]*(maxn+1)
    for i in range(2,maxn+1):
        fact[i]=(fact[i-1]*i)%mod
        invs[i]=invs[mod%i]*(-(mod//i))%mod
        ifact[i]=(ifact[i-1]*invs[i])%mod
    def perm(n,r): return fact[n]*ifact[n-r]%mod
    def comb(n,r): 
        if r>n or n<0 or r<0:return 0
        return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod
    def multicomb(self,n,*rs):#n!/(r1!*r2!*r3!*...)
        ans=fact[n]
        for r in rs: ans=(ans*self.ifact[r])%self.mod
        return ans
    
    d=dict()
    for i,a in enumerate(A):
        if a not in d:
            d[a]=i
        else:
            j=d[a]
            break
    
    p1=j;p2=i
    for k in range(1,N+2):
        ans=comb(N-1,k-2)
        ans+=2*comb(N-1,k-1)
        ans-=comb(N-p2+p1,k-1)
        ans+=comb(N-1,k)
        ans%=mod
        print(ans)







if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 重複を引いて求める

MOD = 10 ** 9 + 7
table_len = 10 ** 5 + 10

fac = [1, 1]
for i in range(2, table_len):
    fac.append(fac[-1] * i % MOD)

finv = [0] * table_len
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(table_len-1, 0, -1):
    finv[i-1] = finv[i] * i % MOD

N = int(input())
As = map(int, input().split())

last = [-1] * (N+1)
for i, A in enumerate(As):
    if last[A] == -1:
        last[A] = i
    else:
        l = last[A]
        r = N - i
        break

for k in range(1, N+2):
    ans = fac[N+1] * finv[k] % MOD * finv[N+1 - k] % MOD
    if l + r >= k - 1:
        ans -= fac[l+r] * finv[k-1] % MOD * finv[l+r-k+1] % MOD
        ans %= MOD
    print(ans)

Submission status: Accepted

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

def comb(n,k,p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p
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


for key, val in cnt.items():
    if val == 2:
        doubled_num = key
        break

left = None
for i, a in enumerate(A):
    if a == doubled_num:
        if left == None:
            left = i
        else:
            right = i

rest = n - right
base_numerator = n+1
base_denominator = 1
base = (base_numerator * mod_inv(base_denominator, mod)) % mod
duplicate_numerator = left + rest + 1
duplicate_denominator = 0
duplicate = 1
for i in range(n+1):
    #print("base", base_numerator, base_denominator)
    #print("dup", duplicate_numerator, duplicate_denominator)
    #print(base, duplicate)
    print((base - duplicate) % mod)

    base_numerator -= 1
    base_denominator += 1
    base *= base_numerator * mod_inv(base_denominator, mod)
    base %= mod
    duplicate_numerator -= 1
    duplicate_denominator += 1
    duplicate *= duplicate_numerator * mod_inv(duplicate_denominator, mod)
    duplicate %= mod

Submission status: Accepted

Solution code:
def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] % mod * ifac[n-k] % mod if n >= k >= 0 else 0


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac


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

MOD = 10**9 + 7
fac, ifac = make_tables(MOD,N+1)

ans = 0
INF = 10**9
x,y = 0,0
l = [INF]*(N+1)
for i in range(N+1):
  if l[A[i]-1] != INF:
    x = l[A[i]-1]
    y = i+1
    break
  l[A[i]-1] = i+1

for i in range(1,N+2):
  print((cmb(N+1,i,MOD,fac,ifac) - cmb(N+x-y,i-1,MOD,fac,ifac))%MOD)