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, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
N = int(input())
A = [int(c) for c in input().split()]
log = [0]*(N+1)
for i in range(N+1):
  if log[A[i]]!=0:
    j = i
  log[A[i]] = 1
c = A[j]
i = A.index(c)
m = i+N-j
for k in range(1,N+2):
  if m>=k-1:
    x = cmb(N+1,k,mod)-cmb(m,k-1,mod)
    print(x%mod)
  else:
    x = cmb(N+1,k,mod)
    print(x%mod)

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
        self.inv[n] = pow(self.factorial[n],mod-2,mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i+1]*(i+1)%mod

    def comb(self,m,k):
        if m-k<0 or k<0: return 0
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod

MOD = 1000000007

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

F = Factorial(N+1,MOD)

tmp = [None for _ in range(N)]

for i in range(N+1):
    if tmp[A[i]-1] is None:
        tmp[A[i]-1] = i
    else:
        a = tmp[A[i]-1]
        b = i
        break

A = []

for i in range(1,N+2):
    A.append((F.comb(N-1,i)+F.comb(N-1,i-2)+F.comb(N-1,i-1)*2-F.comb(N+a-b,i-1))%MOD)

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

Submission status: Accepted

Solution code:
class Factorial:
    def __init__(self, n, mod=10**9+7):
        self.fac = [0] * (n+1)
        self.ifac = [0] * (n+1)
        self.fac[0] = 1
        self.ifac[0] = 1
        self.mod = mod
        modmod = self.mod - 2
        for i in range(n):
            self.fac[i+1] = self.fac[i] * (i+1) % self.mod
            self.ifac[i+1] = self.ifac[i] * pow(i+1, modmod, self.mod) % self.mod

    def comb(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        tmp =  self.ifac[n-r] * self.ifac[r] % self.mod
        return tmp * self.fac[n] % self.mod

    def perm(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        return (self.fac[n] * self.ifac[n-r]) % self.mod

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

d = {}
for i in range(0,n+1):
    if a[i] not in d:
        d[a[i]] = i
    else:
        l,r = d[a[i]], n-i
        break

fact = Factorial(n+1)

for i in range(1,n+2):
    ans = fact.comb(n+1,i)
    s = fact.comb(l+r,i-1)
    ans -= s
    while ans < 0:
        ans += mod
    print(ans)

Submission status: Accepted

Solution code:
#modの掛け算

def modmal(a,b,mod): #a*bをmodを法にして求める

    return a * b % mod


#modの割り算

def moddiv(a,b,mod): #a/bをmodを法にして求める

    return (a * pow(b,mod-2,mod)) % mod


#逆元

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)



#modのn!と、n!の逆元を格納したリストを返す(拾いもの)
#factorialsには[1, 1!%mod , 2!%mod , 6!%mod… , n!%mod] が入っている
#invsには↑の逆元が入っている

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod


n = int(input())

dic = {}

a = list(map(int,input().split()))
twonum = None

for i in range(n+1):

    if a[i] not in dic:
        dic[a[i]] = [i]
    else:
        dic[a[i]].append(i)
        twonum = a[i]

mod = 10**9+7
fac,inv = modfac(n+10,mod)

for k in range(n+1):
    
    k += 1
    
    ans = modnCr(n+1,k,mod,fac,inv)

    l = dic[twonum][0]
    r = (n+1) - dic[twonum][1] - 1

    if l+r >= k-1:
        ans -= modnCr(l+r,k-1,mod,fac,inv)

    print (ans % mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import collections
import copy

def main():
    N = int(input())
    a = list(map(int,input().split()))
    c = collections.Counter(a)
    t = c.most_common()[0][0]
    pos = []
    for i in range(N+1):
        if a[i] == t:
            pos.append(i)
            
    l,r = pos
    MOD = 10**9+7
    fac = [0 for _ in range(N+2)]
    fac[0],fac[1] = 1,1
    inv = copy.deepcopy(fac)
    invfac = copy.deepcopy(fac)
    
    for i in range(2,N+2):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = MOD-(MOD//i)*inv[MOD%i]%MOD
        invfac[i] = (invfac[i-1]*inv[i])%MOD
        
    def coef(x,y):
        if x < y:
            return 0
        else:
            num = (((fac[x]*invfac[y])%MOD)*invfac[x-y]%MOD)
            return num
    
    for i in range(N+1):
        i += 1
        al = coef(N+1,i)
        dup = coef(N-r+l,i-1)
        print((al-dup)%MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - 11

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

# a//b (MOD p)
def div_mod(a, b, p):
    return (a * pow(b, p-2, p)) % p

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

def comb_mod(n, r, mod):
    if n < r:
        return 0
    return div_mod(div_mod(factorial_memo[n], factorial_memo[n-r], mod), factorial_memo[r], mod)


indices = [-1] * (n+1)
for i in range(n+1):
    if indices[a[i]] == -1:
        indices[a[i]] = i
    else:
        f_idx = indices[a[i]]
        s_idx = i
        break

for k in range(1, n+2):
    all_pattern = comb_mod(n+1, k, MOD)
    dup_pattern = comb_mod(f_idx + (n - s_idx), k-1, MOD)
    print((all_pattern - dup_pattern) % MOD)

Submission status: Accepted

Solution code:
MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self//value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

class Combination:
    def __init__(self,max_n):
        self.max_n=0
        self.fact=[Fp(1)]
        self.ifact=[Fp(1)]
        self.make_fact_list(max_n)
    def C(self,n,k):return self.fact[n]*self.ifact[k]*self.ifact[n-k] if 0<=k<=n else 0
    def H(self,n,k):return self.C(n+k-1,k) if n or k else 1
    def P(self,n,k):return self.fact[n]*self.ifact[n-k] if 0<=k<=n else 0
    def make_fact_list(self,max_n):
        if max_n<=self.max_n: return
        self.fact+=[Fp(0)]*(max_n-self.max_n)
        self.ifact+=[Fp(0)]*(max_n-self.max_n)
        for i in range(self.max_n+1,max_n+1):
            self.fact[i]=self.fact[i-1]*i
            self.ifact[i]=self.ifact[i-1]//i
        self.max_n=max_n

N = int(input())
A = list(map(int, input().split()))
B = [-1] * (N + 1)
for i, a in enumerate(A):
    if B[a] >= 0:
        break
    B[a] = i

L = B[a]
R = N - i
M = i - B[a] - 2
print(N)
comb = Combination(N+1)
for k in range(2, N+2):
    print(comb.C(N+1, k) - comb.C(L + R, k-1))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
a = LIST()

check = [0]*(n+1)

kaburi = 0
idx1 = 0
idx2 = 0

mod = 10**9 + 7
N = 10**6  # 必要そうな階乗の限界を入れる
factorial = [1]
for i in range(1, N):
    factorial.append(factorial[i-1] * i % mod)
def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod
def C(n, r):
    return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod
x_inv = [0] * (N)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(N-2, -1, -1):
    x_inv[i] = x_inv[i+1] * (i+1) % mod

for i in range(n+1):
	if check[a[i]]:
		kaburi = a[i]
		idx1 = check[a[i]]
		idx2 = i + 1
		break
	check[a[i]] = i + 1

# print(kaburi)
# print(idx1, idx2)
l = idx1-1
r = n-idx2+1
idx1 -= 1
idx2 -= 1

thre = n-(idx2-idx1)+2
# print(l, r)

for k in range(1, n+2):
	if k >= thre:
		print(C(n+1, k)%mod)
	else:
		print((C(n+1, k)-C(r+l, k-1))%mod)

Submission status: Accepted

Solution code:
def build_combination(n, mod):
    def cmb(n, r):
        if r < 0 or n < r:
            return 0
        return (((invs[r] * invs[n - r]) % mod) * fact[n]) % mod

    fact = [1] * (n + 1)
    for x in range(2, n + 1):
        fact[x] = x * fact[x - 1] % mod

    invs = [1] * (n + 1)
    invs[n] = pow(fact[n], mod - 2, mod)
    for x in range(n - 1, 0, -1):
        invs[x] = invs[x + 1] * (x + 1) % mod

    return cmb


def find(a):
    """重複する数値のindexのペアを返す"""
    n = len(a)
    checked = [-1] * (n + 1)
    for i, x in enumerate(a):
        if checked[x] != -1:
            return checked[x], i
        else:
            checked[x] = i
    raise ValueError


def main():
    mod = 10 ** 9 + 7

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

    cmb = build_combination(n + 1, mod)

    li, ri = find(a)

    for k in range(1, n + 2):
        ret = (cmb(n + 1, k) - cmb(n + 1 - (ri - li + 1), k - 1)) % mod  # mod忘れ
        print(ret)
        # for j in range(k + 1):
        #     ret -= cmb(li, j) * cmb(n - ri, k - j - 1)
        # PxQxRのPRからk-1個とる
        # PRの取り方の総和を求めるより、区間PRに含まれる総個数からk-1個選ぶ方法を考える


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
########   modあり modは素数  ###############
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

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


n=int(input())
A=list(map(int,input().split()))
v=[-1]*n
for i,a in enumerate(A):
    #print(i,a)
    if v[a-1]!=-1:
        s=v[a-1]
        f=i
    if v[a-1]==-1:
        v[a-1]=i

#print(s,f)
mod=10**9+7
for i in range(1,n+1):
    sousuu=cmb(n+1,i,mod)
    tyouhuku=cmb(s+n-f,i-1,mod)
    """if i==1:
        sousuu=n+1
        tyouhuku=1
    else:
        sousuu*=(n+2-i)
        sousuu//=i
        tyouhuku*=(s+n-f+1-i+1)
        tyouhuku//=(i-1)"""
    #print(sousuu,tyouhuku)
    print((sousuu-tyouhuku)%mod)
print(1)

Submission status: Accepted

Solution code:
from collections import Counter

mod = 10**9+7
rng = 100002
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<=0 or k<0 or n<k:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod

n = int(input())
a = list(map(int,input().split()))
same = []
c = Counter(a)
x = c.most_common()[0][0]
for i in range(n+1):
  if a[i] == x:
    same.append(i+1)
y = same[1]-same[0]+1
print(n)
for k in range(2,n+2):
  print((cmb(n+1,k)-cmb(n+1-y,k-1))%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter 
MOD = 1000000007 


def solve(n: int, a: "List[int]"):
    counter = Counter(a).most_common()
    twiceValue = counter[0][0]
    first_index = None
    second_index = None

    for i in range(n+1):
        if a[i] == twiceValue:
            if first_index == None:
                first_index = i
            else:
                second_index = i

    # 1つ目のtwiceValueより左にある数字の数  
    left = first_index

    # 2つ目のtwiceValueより右にある数字の数  
    right = n-second_index
    edge = left+right

    # nCk,edgeCkをO(1)で取れるようにするため
    combination_table = {n+1: [0]*(n+2), edge: [0]*(edge+1)}
    
    combination_table[n+1][0] = 1
    combination_table[n+1][n+1] = 1
    combination_table[edge][0] = 1
    combination_table[edge][edge] = 1
    c_value = 1

    # nCkをうめる
    for i in range(1,n+1):
        c_value *= (n+1 + 1 - i) * pow(i,MOD-2,MOD)
        c_value %= MOD
        combination_table[n+1][i] = c_value

    c_value = 1
    # edgeCkをうめる
    for i in range(1,edge):
        c_value *= (edge + 1 - i) * pow(i,MOD-2,MOD)
        c_value %= MOD
        combination_table[edge][i] = c_value

    for i in range(1,n+2):
        if i-1 <= edge:
            value = combination_table[n+1][i] - combination_table[edge][i-1]
        else:
            value = combination_table[n+1][i]
        print(value%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:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
n=int(input())
A=list(map(int,input().split()))
a=sum(A)-n*(n+1)//2
B=[]
for i in range(n+1):
  if A[i]==a:
    B.append(i)
for k in range(1,n+2):
  print((cmb(n-1,k,mod)+2*cmb(n-1,k-1,mod)-cmb(n-B[1]+B[0],k-1,mod)+cmb(n-1,k-2,mod))%mod)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

mod = 10**9 + 7


class Comb(object):
    def __init__(self, N, mod=10**9 + 7):
        self.mod = mod
        self.fac, self.inv = [1] * (N + 1), [1] * (N + 1)
        for i in range(2, N + 1):
            self.fac[i] = self.fac[i - 1] * i % mod
            self.inv[i] = self.inv[i - 1] * pow(i, mod - 2, mod) % mod

    def calc(self, n, k):
        if n >= k:
            return self.fac[n] * self.inv[k] * self.inv[n - k]
        else:
            return 0


c = [0] * (n + 1)
indexes = [[] for _ in range(n+1)]
for i in range(n + 1):
    c[a[i]] += 1
    indexes[a[i]].append(i)
    if c[a[i]] == 2:
        indexes = indexes[a[i]]
        break

m = indexes[0] + (n - indexes[1])
comb = Comb(n + 1)
for k in range(1, n + 2):
    x = comb.calc(n + 1, k)
    y = comb.calc(m, k - 1)
    ans = (x - y) % mod
    print(ans)

Submission status: Accepted

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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

N = INT()
A = LIST()

# 重複している値を見つけて、indexを取る
dup = 0
for k, v in Counter(A).items():
    if v == 2:
        dup = k
        break
st = []
for i, a in enumerate(A):
    if a == dup:
        st.append(i)
# 重複した値より外側にある要素数
M = N - (st[1] - st[0])

mt = ModTools(N+1, MOD)
for i in range(N+1):
    # 全組み合わせから、重複した値の影響を受ける分を引く
    ans = mt.nCr(N+1, i+1) - mt.nCr(M, i)
    print(ans % MOD)

Submission status: Accepted

Solution code:
import collections

mod = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % mod

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod
already = [0] * (n+1)
k = 0
for key,v in enumerate(a):
  if already[v]:
    k = already[v] + n - key - 1
    break
  else:
    already[v] = key+1
for i in range(n+1):
  if i == n:
    print(1)
    exit()
  ans = comb(n,i) + comb(n,i+1)
  if i <= k:
    ans -= comb(k,i)
  ans %= mod
  print(ans)

Submission status: Accepted

Solution code:
# 解説を見た

class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [-1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod
        # 逆元はこの求め方が速いらしい

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod


def main():
    MOD = 10 ** 9 + 7

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

    pos = [-1] * (N + 1)
    indices = None
    for i, a in enumerate(A):
        if pos[a] == -1:
            pos[a] = i
        else:
            indices = pos[a], i
            break

    width = indices[1] - indices[0] + 1
    # 重複要素を両端に持つような区間の長さ

    calc = Calc(max_value=N + 1, mod=MOD)

    for k in range(1, N + 1 + 1):
        res = (calc.combination(N + 1, k) - calc.combination(N + 1 - width, k - 1)) % MOD
        print(res)


if __name__ == '__main__':
    main()

# PxQxR
# PxRが重複

# 重複要素xの含まれる個数で場合分けをする

# xを含まない
# xを2個とも含む
# 一意

# xを1個含む場合でも、
# Qの要素を含む場合は、どっちのxを取ったか分かる

# Qの要素を含まないとき、どっちのxを取ったか分からない
# cmb(N+1,K)-cmb(PRの総和,K-1)

Submission status: Accepted

Solution code:
MOD = 1000000007

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

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

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

# 鳩ノ巣原理より重複する数が唯一つ存在する
# a_1,a_2,...,a_m,...,a_l,a_l+1,...,a_n
# 左サイドの個数をx,右サイドサイドの個数をyとしたら
# k番目の出力で重複する組合せは(x+y)から(k-1)選んだもの

def solve():
  N = int(input())
  A = list(map(int, input().split()))
  counter = [-1]*(N+2)
  multi_num = -1
  left_element_num = -1
  right_element_num = -1
  for i, a_i in enumerate(A):
    if counter[a_i] != -1:
      left_element_num = counter[a_i]
      right_element_num = N-i
      break
    else:
      counter[a_i] = i

  # print(left_element_num, right_element_num)
  output = []
  for i in range(1, N+2):
    if i == 1:
      output.append(str(N))
      # print(N)
    elif i == N+1:
      output.append(str(1))
      # print(1)
    else:
      ret = cmb(N+1, i)%MOD
      ret = (ret-cmb(left_element_num+right_element_num, i-1)%MOD)%MOD
      output.append(str(ret))
  
  print('\n'.join(output))
  
solve()

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def make_table(n=10**5+1, p=10**9+7):
    fac = [None] * (n + 1)
    fac[0] = 1
    ifac = fac.copy()
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % p
    ifac[n] = pow(fac[n], p - 2, p)
    for i in range(n-1, 0, -1):
        ifac[i] = ifac[i+1] * (i + 1) % p
    return fac, ifac
fac, ifac = make_table()
def comb_mod(n, r, mod=10**9+7):
    if r < 0 or r > n:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

n, *a = map(int, sys.stdin.read().split())

def main():
    appeared = [False] * (n + 1)
    for i in range(n+1):
        cur = a[i] 
        if appeared[cur]:
            x1, x2 = appeared[cur], i+1
            break
        appeared[cur] = i+1
    
    res = [0] * (n + 2)
    for i in range(1, n+2):
        res[i] += comb_mod(n+1, i)

    x = (x1 - 1) + (n + 1 - x2)
    for i in range(x+1):
        res[i+1] -= comb_mod(x, i)
        res[i+1] %= MOD

    return res[1:]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def make_table(n=10**5+1, p=10**9+7):
    fac = [None] * (n + 1)
    fac[0] = 1
    ifac = fac.copy()
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % p
    ifac[n] = pow(fac[n], p - 2, p)
    for i in range(n-1, 0, -1):
        ifac[i] = ifac[i+1] * (i + 1) % p
    return fac, ifac
fac, ifac = make_table()
def comb_mod(n, r, mod=10**9+7):
    if r < 0 or r > n:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

n, *a = map(int, sys.stdin.read().split())

def main():
    appeared = [False] * (n + 1)
    for i in range(n+1):
        cur = a[i] 
        if appeared[cur]:
            x1, x2 = appeared[cur], i+1
            break
        appeared[cur] = i+1
    
    res = [0] * (n + 2)
    for i in range(1, n+2):
        res[i] += comb_mod(n+1, i)
        res[i] %= MOD
    x = (x1 - 1) + (n + 1 - x2)
    
    for i in range(x+1):
        res[i+1] -= comb_mod(x, i)
        res[i+1] %= MOD

    return res[1:]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
class ModWorld:
    def __init__(self, mod):
        self.mod = mod

    def prepare_factorial(self, N):
        self.f = [1]*(N+1) # f[n] := n!
        p = 1
        for i in range(1,N+1):
            p = (p*i) % self.mod
            self.f[i] = p
            
        self.finv = [None]*(N+1)
        for i, s in enumerate(self.f):
            self.finv[i] = self.modpow(s, -1)

    def modpow(self, x, k):
        x %= self.mod
        k %= self.mod-1 # a^(p-1) = 1
        retval = 1
        while k:
            if k&1: retval = retval*x % self.mod
            k>>=1
            x = x*x % self.mod

        return retval

    def modcomb(self, n, k):
        return self.f[n] * self.finv[n-k] * self.finv[k] % self.mod

mw = ModWorld(mod=10**9+7)
mw.prepare_factorial(N=10**5+10)

n = int(input())
A = list(map(int, input().split()))
P = [None]*(n+1)
for i, a in enumerate(A):
    if P[a] is not None: break
    P[a] = i
m = i-P[a]+1

for k in range(1, n+2):
    ans = mw.modcomb(n+1, k)
    if k-1<=n+1-m : ans -= mw.modcomb(n+1-m, k-1)
    print(ans%mw.mod)

Submission status: Accepted

Solution code:
from collections import Counter

n, *a = map(int, open(0).read().split())
n += 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


def make_table(n, mod=10 ** 9 + 7):
    N = n
    # 元テーブル
    g1 = [0] * (N + 1)
    g1[0] = 1
    g1[1] = 1

    # 逆元テーブル
    g2 = [0] * (N + 1)
    g2[0] = 1
    g2[1] = 1

    # 逆元テーブル計算用テーブル
    inverse = [0] * (N + 1)
    inverse[0] = 0
    inverse[1] = 1

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

    return tuple(g1), tuple(g2), tuple(inverse)


d = Counter(a).most_common(1)[0][0]
lr = [i for i, e in enumerate(a) if e == d]
l = lr[1] - lr[0] + 1
g1, g2, inverse = make_table(n)
MOD = 10 ** 9 + 7

answer = [(cmb(n, i, MOD) - cmb(n - l, i - 1, MOD)) % MOD for i in range(1, n + 1)]
print('\n'.join(map(str, answer)))

Submission status: Accepted

Solution code:
from collections import Counter

n, *a = map(int, open(0).read().split())
n += 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


def make_table(n, mod=10 ** 9 + 7):
    N = n
    # 元テーブル
    g1 = [0] * (N + 1)
    g1[0] = 1
    g1[1] = 1

    # 逆元テーブル
    g2 = [0] * (N + 1)
    g2[0] = 1
    g2[1] = 1

    # 逆元テーブル計算用テーブル
    inverse = [0] * (N + 1)
    inverse[0] = 0
    inverse[1] = 1

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

    return tuple(g1), tuple(g2), tuple(inverse)


d = Counter(a).most_common(1)[0][0]
lr = [i for i, e in enumerate(a) if e == d]
l = lr[1] - lr[0] + 1
g1, g2, inverse = make_table(n)
MOD = 10 ** 9 + 7

answer = [(cmb(n, i) - cmb(n - l, i - 1)) % MOD for i in range(1, n + 1)]
print('\n'.join(map(str, answer)))

Submission status: Accepted

Solution code:
from collections import Counter

n, *a = map(int, open(0).read().split())
n += 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


def make_table(n, mod=10 ** 9 + 7):
    mod = mod
    N = n
    # 元テーブル
    g1 = [0] * (N + 1)
    g1[0] = 1
    g1[1] = 1

    # 逆元テーブル
    g2 = [0] * (N + 1)
    g2[0] = 1
    g2[1] = 1

    # 逆元テーブル計算用テーブル
    inverse = [0] * (N + 1)
    inverse[0] = 0
    inverse[1] = 1

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

    return g1, g2, inverse


d = Counter(a).most_common(1)[0][0]
lr = [i for i, e in enumerate(a) if e == d]
l = lr[1] - lr[0] + 1
g1, g2, inverse = make_table(n)
MOD = 10 ** 9 + 7

answer = [(cmb(n, i) - cmb(n - l, i - 1)) % MOD for i in range(1, n + 1)]
print('\n'.join(map(str, answer)))

Submission status: Accepted

Solution code:
from collections import Counter

n, *a = map(int, open(0).read().split())
n += 1


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


mod = 10 ** 9 + 7
N = n
# 元テーブル
g1 = [0] * (N + 1)
g1[0] = 1
g1[1] = 1

# 逆元テーブル
g2 = [0] * (N + 1)
g2[0] = 1
g2[1] = 1

# 逆元テーブル計算用テーブル
inverse = [0] * (N + 1)
inverse[0] = 0
inverse[1] = 1

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

d = Counter(a).most_common(1)[0][0]
lr = [i for i, e in enumerate(a) if e == d]
l = lr[1] - lr[0] + 1

answer = [(cmb(n, i, mod) - cmb(n - l, i - 1, mod)) % mod for i in range(1, n + 1)]
print('\n'.join(map(str, answer)))