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:
n=int(input())
A=list(map(int,input().split()))
idx=dict()
mod=10**9+7
for i in range(1+n):
    if A[i] in idx:
        x=idx[A[i]]
        y=i
        break
    idx[A[i]]=i
kaijo=[1]
for i in range(1,n+2):
    kaijo.append((kaijo[-1]*i)%mod)
gyaku=[pow(kaijo[n+1],mod-2,mod)]
from collections import deque
gyaku=deque(gyaku)
for i in range(n+1,0,-1):
    gyaku.appendleft((gyaku[0]*i)%mod)
gawa=n-1-(y-x-1)
zentai=n-1
gawa_conb=[1]
for i in range(1,1+gawa):
    if i<1+gawa//2:
        gawa_conb.append((kaijo[gawa]*gyaku[i]*gyaku[gawa-i])%mod)
    else:
        gawa_conb.append(gawa_conb[gawa-i])
gawa_conb+=[0]*(zentai-gawa)
zentai_conb=[1]
for i in range(1,1+zentai):
    if i<1+zentai//2:
        zentai_conb.append((kaijo[zentai]*gyaku[i]*gyaku[zentai-i])%mod)
    else:
        zentai_conb.append((zentai_conb[zentai-i]))
if n>1:
    print((zentai_conb[1]+zentai_conb[0]*2-gawa_conb[0])%mod)
    for i in range(2,n):
        print((zentai_conb[i-2]+zentai_conb[i]+zentai_conb[i-1]*2-gawa_conb[i-1])%mod)
    print((zentai_conb[n-2]+zentai_conb[n-1]*2-gawa_conb[n-1])%mod)
    print((zentai_conb[n-1])%mod)
else:
    print(1)
    print(1)

Submission status: Accepted

Solution code:
mod = int(1e9) + 7


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, y//2)**2 % mod
    else:
        return power(x, y//2)**2 * x % mod


fact = [1] * int(1e5+2)
for i in range(1, int(1e5+2)):
    fact[i] = (i * fact[i-1]) % mod
inv = [1] * int(1e5+2)
inv[int(1e5+1)] = power(fact[int(1e5+1)], mod-2) % mod
for i in range(int(1e5), 0, -1):
    inv[i] = (inv[i+1] * (i+1)) % mod


def combination(n, r):
    return fact[n] * inv[r] * inv[n-r] % mod


def main():
    N = int(input())
    A = list(map(int, input().split()))
    idx = [-1] * (N+1)
    x = 0
    for i in range(N+1):
        if idx[A[i]] == -1:
            idx[A[i]] = i
        else:
            x = i - idx[A[i]]
    for i in range(1, N+2):
        ans = combination(N+1, i)
        if i <= (N+1-x):
            ans = (ans - combination(N+1-(x+1), i-1)) % mod
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n = I()
a = LI()
b = [None for i in range(n)]
k = n//2
if n%2:
    for i in range(n):
        if i%2:
            b[k+(i+1)//2] = a[i]
        else:
            b[k-i//2] = a[i]
else:
    for i in range(n):
        if i%2:
            b[k-(i+1)//2] = a[i]
        else:
            b[k+i//2] = a[i]
print(*b)
"""

#D
n = I()
a = LI()
fact = [1 for i in range(n+2)]
for i in range(1,n+2):
    fact[i]*= fact[i-1]*i
    fact[i] %= mod
inv_fact = [1 for i in range(n+2)]
inv_fact[n+1] = pow(fact[n+1],mod-2,mod)
for i in range(1,n+1)[::-1]:
    inv_fact[i] = inv_fact[i+1]*(i+1)
    inv_fact[i] %= mod
count = [None for i in range(n+1)]
for i in range(n+1):
    if count[a[i]] != None:
        l = count[a[i]]
        r = n-i
        break
    count[a[i]] = i
for i in range(1,n+2):
    ans = fact[n+1]*inv_fact[i]*inv_fact[n+1-i]%mod
    if l+r >= i-1:
        ans -= fact[l+r]*inv_fact[i-1]*inv_fact[l+r-i+1]%mod
        ans %= mod
    print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

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 = int(input())
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

li=list(map(int,input().split()))
cl=[0]*N
for i in range(N+1):
    cl[li[i]-1]+=1
hu=0
for i in range(N):
    if cl[i]==2:
        hu=i+1
h1=-1
h2=-1
for i in range(N+1):
    if h1==-1 and li[i]==hu:
        h1=i
    if h1>=0 and li[i]==hu:
        h2=N-i

print(N)
for i in range(N):
    print((cmb(N+1,i+2,mod)-cmb(h1+h2,i+1,mod))%mod)

Submission status: Accepted

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

class ModInv:
    def __init__(self, size, MOD):
        self.inv = [0] * (size + 1)
        self.inv[1] = 1
        for i in range(2, size + 1):
            self.inv[i] = (-(MOD // i) * self.inv[MOD%i]) % MOD

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

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        break

first = a.index(b[i])
for i in range(first + 1, n + 1):
    if a[i] == a[first]:
        second = i

w = n + first - second

inv = ModInv(n + 1, MOD)
c = [1] * (n + 2)
d = [1] * (n + 2)

for i in range(n + 1):
    d[i + 1] = (d[i] * inv.inv[i + 1]) % MOD
for i in range(n + 1):
    c[i + 1] = (c[i] * (i + 1)) % MOD

print(n)
for k in range(2, n + 2):
    ans = (((c[n+1] * d[n+1-k]) % MOD) * d[k]) % MOD
    if w >= k - 1:
        ans -= (((c[w] * d[w-k+1]) % MOD) * d[k-1]) % MOD
    print( ans % MOD )

Submission status: Accepted

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



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**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


sorted_a=sorted(a)
for i in range(n):
  if sorted_a[i]==sorted_a[i+1]:
    num = sorted_a[i]
    break

flag = True
for i in range(n+1):
  if a[i]==num:
    if flag:
      first = i
      flag = False
    else:
      second = i

#combination=[0]*(n+2)
#combination[0]=1
#for i in range(1,n+2):
#  combination[i] =combination[i-1]*(n+2-i)//i
#combination2=[0]*(n+2)
#combination2[0]=0
#combination2[1]=1
#for i in range(2,n+2):
#  combination2[i] =combination2[i-1]*(first+n-second+1-(i-1))//(i-1)

#for i in range(1,n+2):
  #ans = comb(n-1,i) + 2*comb(n-1,i-1)-comb(first+n-second,i-1) +comb(n-1,i-2)
  #ans = comb(n+1,i) - comb(first+n-second,i-1)
  #ans = (combination[i]%1000000007-combination2[i]%1000000007)%1000000007
  #print(ans)  
  
for i in range(1,n+2):
  ans = cmb(n+1,i,mod) - cmb(first+n-second,i-1,mod)
  print(ans%mod)

Submission status: Accepted

Solution code:
Q = 10**9 + 7
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv
modfunctional = [1]*(10**5+2)
modinv = getInv(10**5+2)
modinvfunctional = [1]*(10**5+2)
for i in range(10**5+1):
    modinvfunctional[i+1] = (modinvfunctional[i]*modinv[i+1])%Q
for i in range(10**5+1):
    modfunctional[i+1] = (modfunctional[i]*(i+1))%Q

n = int( input())
A = list( map( int, input().split()))
V = [0 for _ in range(n+1)]
for i in range(n+1):
    if V[A[i]] == 1:
        b = A[i]
        break
    V[A[i]] = 1
b_1 = -1
for i in range(n+1):
    if A[i] == b:
        if b_1 == -1:
            b_1 = i
        else:
            b_2 = i
            break
d = b_1 + n - b_2
for k in range(1, n+2):
    if k-1 > d:
        print(((modfunctional[n+1]*modinvfunctional[k])*modinvfunctional[n+1-k])%Q)
    else:
        print( (modfunctional[n+1]*modinvfunctional[k]%Q*modinvfunctional[n+1-k]%Q - modfunctional[d]*modinvfunctional[k-1]%Q*modinvfunctional[d-k+1]%Q)%Q)

Submission status: Accepted

Solution code:
Q = 10**9 + 7
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv
modfunctional = [1]*(10**5+2)
modinv = getInv(10**5+2)
modinvfunctional = [1]*(10**5+2)
for i in range(10**5+1):
    modinvfunctional[i+1] = (modinvfunctional[i]*modinv[i+1])%Q
for i in range(10**5+1):
    modfunctional[i+1] = (modfunctional[i]*(i+1))%Q

n = int( input())
A = list( map( int, input().split()))
V = [0 for _ in range(n+1)]
for i in range(n+1):
    if V[A[i]] == 1:
        b = A[i]
        break
    V[A[i]] = 1
b_1 = -1
for i in range(n+1):
    if A[i] == b:
        if b_1 == -1:
            b_1 = i
        else:
            b_2 = i
            break
d = b_1 + n - b_2
for k in range(1, n+2):
    if k-1 > d:
        print(((modfunctional[n+1]*modinvfunctional[k])*modinvfunctional[n+1-k])%Q)
    else:
        print( (modfunctional[n+1]*modinvfunctional[k]%Q*modinvfunctional[n+1-k]%Q - modfunctional[d]*modinvfunctional[k-1]%Q*modinvfunctional[d-k+1]%Q)%Q)

Submission status: Accepted

Solution code:
from collections import defaultdict

MOD = 1000000007

n = int(input())
alst = list(map(int, input().split()))
dic = defaultdict(list)
for i in range(n + 1):
    dic[alst[i]].append(i)

for v in dic.values():
    if len(v) == 2:
        left, right = v
        break

rem = n + 1 - (right - left + 1)


factMem = {}
def fact(x):
    if x <= 0:return 1
    if x in factMem:return factMem[x]
    factMem[x] = x * fact(x - 1) % MOD
    return factMem[x]

for x in range(n + 1):
    fact(x)

inverseMem = {}
def inverse(x):
    if x in inverseMem:return inverseMem[x]
    inverseMem[x] = pow(x, MOD - 2, MOD)
    return inverseMem[x]

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
M = 10**9+7
res = [-1] * (n+1)
for i in range(n+1):
    if res[a[i]] == -1:
        res[a[i]] = i
    else:
        d = a[i]
        l, r = res[d], n-i


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  # 出力の制限
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

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


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

Submission status: Accepted

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

# 重複している要素Xを探す
X_search_set = set()
for a in A:
    if a in X_search_set:
        X = a
        break
    else:
        X_search_set.add(a)

# 重複している要素のindexを取得
x_left, x_right = [i for i, a in enumerate(A) if a == X]

# 重複している要素の左側・右側にそれぞれ何個あるか
Left, Right = x_left, N - x_right

# 階乗 & 逆元計算
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


# 計算・出力
for k in range(1, len(A) + 1):
    ans = nCr(len(A), k)

    # 重複部分を引く
    if k - 1 <= Left + Right:
        ans -= nCr(Left + Right, k - 1)

    print(ans % mod)

Submission status: Accepted

Solution code:
m = 10**9+7
n = int(input())
inv = [0]*(n+3)
inv[1] = 1
for i in range(2,n+3):
  inv[i] = (m//i)*(m-inv[m%i])%m
# print(inv)

a = list(map(int,input().split()))
w = sum(a) - n*(n+1)//2

q = 0
t = -1
for i in range(n+1):
  if a[i] == w:
    q += t*i
    t = 1
q += 1

x = (n+1)%m
y = 1
for k in range(1,n+2):
  print((x-y)%m)
  x = x*(n+1-k)*inv[k+1]%m
  y = y*(n+2-q-k)*inv[k]%m

Submission status: Accepted

Solution code:
n = int(input())
a=list(map(int,input().split()))
dic = {}
dic2 = {}
for i in range(n + 1):
    dic[a[i]] = 0
    dic2[a[i]] = []
f = 0
s = 0
for i in range(n + 1):
    dic[a[i]] += 1
    dic2[a[i]].append(i)
    if dic[a[i]] == 2:
        f = dic2[a[i]][0]
        s = i
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 + 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 )

for k in range(1,n+2):
    if k==1:
        print(n)
    elif k>f+n-s+1:
        print(cmb(n+1,k,mod))
    else:
        if cmb(n+1,k,mod)-cmb(f+n-s,k-1,mod)>=0:
            print(cmb(n+1,k,mod)-cmb(f+n-s,k-1,mod))
        else:
            print(cmb(n+1,k,mod)-cmb(f+n-s,k-1,mod)+mod)

Submission status: Accepted

Solution code:
n = int(input())
a = input().split()
a = [int(m) for m in a]
dic = {}
dic2 = {}
for i in range(n + 1):
    dic[a[i]] = 0
    dic2[a[i]] = []
f = 0
s = 0
for i in range(n + 1):
    dic[a[i]] += 1
    dic2[a[i]].append(i)
    if dic[a[i]] == 2:
        f = dic2[a[i]][0]
        s = i
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 + 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 )
 
 
for k in range(1,n + 2):
    if k == 1:
        print(n)
    else:
        if f + n - s +1>= k:
            if (cmb(n + 1, k, mod) - cmb(f + n - s, k-1, mod)) >= 0:
                print(cmb(n + 1, k, mod) - cmb(f + n - s, k-1, mod))
            else:
                print(cmb(n + 1, k, mod) - cmb(f + n - s, k-1, mod) + mod)
        elif f+n-s+1<k:
            print(cmb(n + 1, k, mod))

Submission status: Accepted

Solution code:

n = int(input())
a = input().split()
a = [int(m) for m in a]
dic = {}
dic2 = {}
for i in range(n + 1):
    dic[a[i]] = 0
    dic2[a[i]] = []
f = 0
s = 0
for i in range(n + 1):
    dic[a[i]] += 1
    dic2[a[i]].append(i)
    if dic[a[i]] == 2:
        f = dic2[a[i]][0]
        s = i
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 + 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 )
 
 
for k in range(1,n + 2):
    if k == 1:
        print(n)
    else:
        if f + n - s +1>= k:
            if (cmb(n + 1, k, mod) - cmb(f + n - s, k-1, mod)) >= 0:
                print(cmb(n + 1, k, mod) - cmb(f + n - s, k-1, mod))
            else:
                print(cmb(n + 1, k, mod) - cmb(f + n - s, k-1, mod) + mod)
        elif f+n-s+1<k:
            print(cmb(n + 1, k, mod))

Submission status: Accepted

Solution code:
n = int(input())
a = input().split()
a = [int(m) for m in a]
dic = {}
dic2 = {}
for i in range(n + 1):
    dic[a[i]] = 0
    dic2[a[i]] = []
f = 0
s = 0
for i in range(n + 1):
    dic[a[i]] += 1
    dic2[a[i]].append(i)
    if dic[a[i]] == 2:
        f = dic2[a[i]][0]
        s = i
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 + 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 )
 
 
for k in range(1,n + 2):
    if k == 1:
        print(n)
    else:
        if f + n - s +1>= k:
            if (cmb(n + 1, k, mod) - cmb(f + n - s, k-1, mod)) >= 0:
                print(cmb(n + 1, k, mod) - cmb(f + n - s, k-1, mod))
            else:
                print(cmb(n + 1, k, mod) - cmb(f + n - s, k-1, mod) + mod)
        else:
            print(cmb(n + 1, k, mod))

Submission status: Accepted

Solution code:
n = int(input())
a = input().split()
a = [int(m) for m in a]
dic = {}
dic2 = {}
for i in range(n + 1):
    dic[a[i]] = 0
    dic2[a[i]] = []
f = 0
s = 0
for i in range(n + 1):
    dic[a[i]] += 1
    dic2[a[i]].append(i)
    if dic[a[i]] == 2:
        f = dic2[a[i]][0]
        s = i
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 + 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 )
 
 
for i in range(n + 1):
    if i == 0:
        print(n)
    else:
        if f + n - s >= i:
            if (cmb(n + 1, i + 1, mod) - cmb(f + n - s, i, mod)) >= 0:
                print(cmb(n + 1, i + 1, mod) - cmb(f + n - s, i, mod))
            else:
                print(cmb(n + 1, i + 1, mod) - cmb(f + n - s, i, mod) + mod)
        else:
            print(cmb(n + 1, i + 1, mod))

Submission status: Accepted

Solution code:
#import itertools
import math
n = int(input())
a = input().split()
a = [int(m) for m in a]
dic = {}
dic2 = {}
for i in range(n + 1):
    dic[a[i]] = 0
    dic2[a[i]] = []
k = 0
j = 0
for i in range(n + 1):
    dic[a[i]] += 1
    dic2[a[i]].append(i)
    if dic[a[i]] == 2:
        j = dic2[a[i]][0]
        k = i

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 + 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 )


for i in range(n + 1):
    if i == 0:
        print(n)
    else:
        if j + n - k >= i:
            if (cmb(n + 1, i + 1, mod) - cmb(j + n - k, i, mod)) >= 0:
                print(cmb(n + 1, i + 1, mod) - cmb(j + n - k, i, mod))
            else:
                print(cmb(n + 1, i + 1, mod) - cmb(j + n - k, i, mod) + mod)
        else:
            print(cmb(n + 1, i + 1, mod))

Submission status: Accepted

Solution code:
mod=10**9+7
N=int(input())
Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=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,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

inverseFactorial=[1]*(N+1)
inverseFactorial[N]=power(Factorial[N],mod-2)
for i in range(0,N)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod

list=[-1]*N
n=0
for i in input().split():
  if list[int(i)-1]<0:
    list[int(i)-1]=n
    n+=1
  else:
    a=list[int(i)-1]
    b=n-a-1
    c=N-n
for m in range(1,N+2):
    print((comb(a+b+c,m)+2*comb(a+b+c,m-1)-comb(a+c,m-1)+comb(a+b+c,m-2))%mod)

Submission status: Accepted

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

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)

N = 10**9+7
R = 10**5+10
modfact = [0]*(R+1)
def modfact_memo(n,N):
    r = 1
    modfact[0] = 1
    for i in range(1,n+1):
        r = r % N * i % N
        modfact[i] = r
modfact_memo(R,N)

# ax ≡ 1 (mod m)
modinv=[0]*(R+1)
def modinv_memo(a,m):
    for i in range(a+1):
        j = modfact[i]
        (inv, q, gcd_val) = egcd(j, m)
        modinv[i] = inv % m
modinv_memo(R,N)

def modconb(n,r,N):
    p = modfact[n]
    q1 = modinv[r]
    q2 = modinv[n-r]
    return p*q1%N*q2%N


n = int(input())
a = list(map(int,input().split()))
b=[0]*n
for i in range(n+1):
    b[a[i]-1] += 1
w = b.index(2)+1
index = []
for i in range(n+1):
    if a[i] == w:
        index.append(i)
l = index[0]
r = n - index[1]

for i in range(n+1):
    ans = modconb(n+1,i+1,N)
    if l+r >= i:
        ans -= modconb(l+r,i,N)
        ans %= N
    print(ans)

Submission status: Accepted

Solution code:
def Pow(i, n):
    if n == 0:
        return 1
    else:
        ans = Pow(i * i % mod, n//2)
        if n % 2 == 1:
            ans *= i
            ans %= mod
        return ans

N = int(input())
A = [int(i) for i in input().split()]
mod = 7 + 10 ** 9
num = [-1 for i in range(N)]
for i, a in enumerate(A):
    if num[a-1] == -1:
        num[a-1] = i
    else:
        Double = [num[a-1], i]

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

doublearray = N + 1 - (Double[1] - Double[0])
for i in range(1, N+2):
    whole = Nfact[N+1] * NfactRev[N+1-i] * NfactRev[i] % mod
    if i <= doublearray:
        double = Nfact[doublearray-1] * NfactRev[doublearray-i] * NfactRev[i-1] % mod
    else:
        double = 0
    print((whole - double) % mod)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        
# 二項係数
def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod


from collections import Counter

MOD = 10**9+7

n = ni()
a = list(li())

# 被っている数の後にある数の個数を把握
cnt = Counter(a)
db = 0
for k,v in cnt.items():
    if v == 2:
        db = k
        
front = a.index(db)
back = a[::-1].index(db)

# 二項係数の準備
inv = inv_mod(n+1,MOD)
fac = fact(n+1, MOD)
facInv = fact_inv(n+1,inv,MOD)

# 出力
for k in range(1, n+2):
    ans = nCr(n+1,k,MOD,fac,facInv) - nCr(front+back,k-1,MOD,fac,facInv)
    if ans < 0:
        ans += MOD
    
    print(ans)

Submission status: Accepted

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

index2 = 0
for i in range(n+1):
    if a[i] in s:
        index2 = i
    s.add(a[i])

index1 = 0
for i in range(n+1):
    if a[i] == a[index2]:
        index1 = i
        break

#combination---
m = 10**9 + 7
fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n+5):
    fac.append(fac[i-1] * i % m)
    inv.append(m - inv[m%i] * (m//i) % m)
    finv.append(finv[i-1] * inv[i] % m)

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

#-----


for k in range(1, n+2):
    print((nck(n + 1, k) - nck(index1 + n - index2, k-1)) % m)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
src = list(map(int,input().split()))
ctr = Counter(src)
doub = ctr.most_common()[0][0]
i1 = src.index(doub)
i2 = src[::-1].index(doub)
doub_len = (i1+i2+1)

MOD = 10**9+7

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

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

ans = []
for i in range(1,N+2):
    ans.append(ncr(N+1,i))
for i in range(doub_len):
    ans[i] -= ncr(doub_len-1, i)
    ans[i] %= MOD
print(*ans,sep='\n')

Submission status: Accepted

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

B=sorted(A)
for i in range(1,n+1):
    if B[i]==B[i-1]:
        x=B[i]

r=A[::-1].index(x)
l=A.index(x)



s=n+1
INV=[None]*(s+1)#1/aのリストを予め作っておく.
for i in range(1,s+1):
    INV[i]=pow(i,mod-2,mod)

Combi=[None]*(s+1)#Combi[i]=nCi を表す
Combi[0]=1
for i in range(1,s+1):
    Combi[i]=Combi[i-1]*(s-i+1)*INV[i] %mod


m=r+l
INV2=[None]*(m+1)#1/aのリストを予め作っておく.
for i in range(1,m+1):
    INV2[i]=pow(i,mod-2,mod)

Combi2=[None]*(m+1)#Combi[i]=nCi を表す
Combi2[0]=1
for i in range(1,m+1):
    Combi2[i]=Combi2[i-1]*(m-i+1)*INV2[i] %mod











print(n)
for i in range(2,n+2):
    ANS=Combi[i]
    if m>=i-1:
        ANS-=Combi2[i-1]
    print(ANS%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


class Combination:
    def __init__(self, n, mod):
        assert 0 < n
        self.mod = mod
        self.fact = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for i in range(1, len(self.fact)):
            self.fact[i] = (i * self.fact[i - 1]) % self.mod
            self.inv[i] = pow(self.fact[i], self.mod - 2, self.mod)

    def nCr(self, n, k):
        assert 0 <= n < len(self.fact) and 0 <= k
        assert n >= k
        a = self.fact[n]
        b = (self.inv[k] * self.inv[n - k]) % self.mod
        return a * b % self.mod


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

    comb = Combination(10**5 + 10, MOD)

    pos = [-1] * 100010
    for i, a in enumerate(A):
        if pos[a] != -1:
            pos1, pos2 = min(pos[a], i), max(pos[a], i)
            break
        pos[a] = i

    dist = pos2 - pos1
    for i in range(1, N + 2):
        ans = comb.nCr(N + 1, i)
        rest = N + 1 - dist - 1

        if rest >= i - 1:
            ans -= comb.nCr(rest, i - 1)

        print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

p = 10**9 + 7

found = {}
for i, a in enumerate(A):
    if a in found:
        dup = a
        dup_1 = found[a]
        dup_2 = i
    found[a] = i

from functools import lru_cache

@lru_cache(maxsize=None)
def gfp_inv(x, p):
    return pow(x, p - 2, p)

from itertools import chain, accumulate
memo_fact = list(chain([1], accumulate(range(1, 10**5 + 2), lambda a, x: a * x % p)))

def comb(n, m):
    if m < 0 or n < m: return 0
    if n == m: return 1
    return memo_fact[n] * gfp_inv(memo_fact[n - m], p) * gfp_inv(memo_fact[m], p) % p

intv = dup_2 - dup_1 - 1
for k in range(1, n + 2):
    ans = comb(n + 1, k)
    ans -= comb(n + 1 - intv - 2, k - 1)
    print(ans % p)

Submission status: Accepted

Solution code:
def factorial_memo(n, p):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F

def inverse(F, p):
  Finv = [x for x in F]
  Finv[-1] = pow(Finv[-1], p - 2, p)
  for i in range(len(F) - 2, 0, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv

def comb(a, b):
  if a < b:
    return 0
  return F[a] * Finv[a - b] * Finv[b] % p

n = int(input())
A = [int(x) for x in input().split()]
p = 10 ** 9 + 7
D = [-1] * n
double = [-1, -1]
for i, a in enumerate(A):
  if D[a - 1] == -1:
    D[a - 1] = i
  else:
    double = [D[a - 1], i]
    break
F = factorial_memo(n + 1, p)
Finv = inverse(F, p)
n_a = double[0]
n_b = n - double[1]
print(n)
C = [0] * n
for i in range(2, n + 2):
  cnt = (comb(n + 1, i) - comb(n_a + n_b, i - 1)) % p
  print(cnt)