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:
import sys
input = sys.stdin.buffer.readline
N = int(input())
a = list(map(int, input().split()))
num = [[] for _ in range(N + 1)]
dnum = 0
mod = 10 ** 9 + 7
for i in range(N + 1):
  num[a[i]].append(i)
  if len(num[a[i]]) == 2:
    dnum = a[i]
class Factorial:
  def __init__(self, n, mod):
    self.f=[1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i=[pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(N + 1, mod)
for i in range(1, N + 2):
  t = f.combi(N + 1, i)
  u = 0
  if num[dnum][0] + (N + 1 - num[dnum][1]) >= i:
    u = f.combi(num[dnum][0] + (N + 1 - num[dnum][1]), i)
    if num[dnum][0] + (N + 1 - num[dnum][1] - 1) >= i:
      u -= f.combi(num[dnum][0] + (N + 1 - num[dnum][1] - 1), i)
  print((t - u) % mod)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = list(map(int,input().split()))
    #N = 1
    #A = [1,1]
    
    mod = 10**9 + 7
    ex = [1]
    for i in range(1,10**5+1):
        ex.append((ex[-1]*i)%mod)
        
    def comb(n,k):
        if 0 <= n and 0 <= k <= n:
            return (ex[n] * pow(ex[k],mod-2,mod) * pow(ex[n-k],mod-2,mod))%mod
        else:
            return 0
    
    D = {}
    for i in range(N+1):
        if not A[i] in D:
            D[A[i]] = i
        else:
            double = A[i]
            d1 = D[A[i]]
            d2 = i
    A = d1
    B = d2-d1-1
    C = N-d2
    #print(A,B,C)
    for i in range(1,N+2):
        ans = 0
        ans += comb(A+B+C,i)
        ans += 2*comb(A+B+C,i-1)
        ans -= comb(A+C,i-1)
        ans += comb(A+B+C,i-2)
        #print(comb(A+B+C,i), comb(A+B+C-1,i-1), comb(A+C,i-1), comb(A+B+C,i-2))
        print(ans%mod)
        
        
    
    
main()

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    a = LI()
    d = defaultdict(lambda:0)
    for i in a:
        d[i] += 1
    d = list(d.values())
    d.sort()
    ans = 0
    for i in range(len(d)-k):
        ans += d[i]
    print(ans)
    return

#B
def B():
    n,z,w = LI()
    a = LI()
    if n == 1:
        print(abs(a[0]-w))
        return
    ans = max(abs(a[-1]-w),abs(a[-2]-a[-1]))
    print(ans)
    return

#C
def C():
    n = I()
    s1 = S()
    s2 = S()
    dp = [[[0]*3 for j in range(3)] for i in range(n+1)]
    if s1[0] == s2[0]:
        dp[1] = [[1 if i == j else 0 for j in range(3)] for i in range(3)]
    else:
        dp[1] = [[0 if i == j else 1 for j in range(3)] for i in range(3)]
    for i in range(1,n):
        ni = i+1
        if s1[i] == s2[i]:
            for j in range(3):
                for k in range(3):
                    if k == j:continue
                    for l in range(3):
                        if l == j:continue
                        dp[ni][j][j] += dp[i][k][l]
        else:
            if i and s1[i] == s1[i-1]:
                for j in range(3):
                    for k in range(3):
                        dp[ni][j][k] = dp[i][j][k]
            else:
                for j in range(3):
                    for k in range(3):
                        if k == j:continue
                        for l in range(3):
                            if l == j:continue
                            for m in range(3):
                                if m == k:continue
                                dp[ni][j][k] += dp[i][l][m]
    ans = 0
    for i in range(3):
        for j in range(3):
            ans += dp[n][i][j]
    print(ans%mod)
    return

#D
def D():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod
    n = I()
    a = LI()
    d = defaultdict(lambda : 0)
    for i in range(n+1):
        if d[a[i]]:
            l = d[a[i]]-1
            r = n-i
            break
        d[a[i]] = i+1
    fact = [1]
    m = 100001
    for i in range(m):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(m+1)
    inv[m] = pow(fact[m],mod-2,mod)
    for i in range(m)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    for i in range(1,n+2):
        ans = comb(n+1,i)
        if l+r >= i-1:
            ans -= comb(l+r,i-1)
            ans %= mod
        print(ans)
    return

#E
def E():

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())

A = list(map(int, input().split()))
c = Counter(A)
s = c.most_common()[0][0]
idx_s = [i for i,x in enumerate(A) if x == s]
l = idx_s[0]
r = idx_s[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

for i in range(1,N+2):
    print((nCr(N+1, i) - nCr(l+N+1-(r+1), i-1)) % MOD)

Submission status: Accepted

Solution code:

mod = 10**9+7
n = int(input())
a = list(map(int, input().split()))
check = [-1]*(n+1)
def make_fact(n):
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact

def make_fact_inv(n):
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact = make_fact(n+1)
fact_inv = make_fact_inv(n+1)
def comb(n, k):
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod

for i, ai in enumerate(a):
    if check[ai]<0:
        check[ai] = i
    else:
        b = check[ai]
        c = i
        break
m = c-b-1
for k in range(1, n+2):
    if n-m-1>=k-1:
        print((comb(n+1, k)-comb(n-m-1, k-1))%mod)
    else:
        print(comb(n+1, k))

Submission status: Accepted

Solution code:
from collections import Counter

def factorials(n,m):
    # 0~n!のリスト
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i%m)

    # 0~n!の逆元のリスト
    g = [1]
    for i in range(n):
        g.append(pow(f[i+1],m-2,m))

    return f,g


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

m = 10**9+7

f,g = factorials(n,m)

counter = Counter(a)

for x in a:
    if counter[x] == 2:
        b = x
        break

l,r = [i for i, x in enumerate(a) if x == b]

if r-l == 1:
    renzoku = True
else:
    renzoku = False

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

if renzoku:
    print(n)
    for k in range(2,n):
        x = f[n-1]*g[n-k-1]*g[k]
        y = f[n-1]*g[n-k]*g[k-1]
        z = f[n-1]*g[n-k+1]*g[k-2]
        print((x+y+z)%m)
    print(n)
    print(1)
else:
    print(n)
    for k in range(2,n):
        x = f[n-1]*g[n-k-1]*g[k]
        y = f[n-1]*g[n-k]*g[k-1] * 2
        z = f[n-1]*g[n-k+1]*g[k-2]
        if n-r + l >=k-1:
            y -= f[n-r+l]*g[n-r+l-k+1]*g[k-1]
        print((x+y+z)%m)
    print(n+1)
    print(1)

Submission status: Accepted

Solution code:
fact=[1]
MOD=10**9+7
temp=1
for i in range(1,10**6):
    temp*=i
    temp%=MOD
    fact+=[temp]

def bi(a,b):
    if b>a:
        return 0
    up=fact[a]
    down=fact[a-b]*fact[b]
    down=pow(down,MOD-2,MOD)
    return (up*down)%MOD
    
def find(A):
    n=len(A)-1
    dic={}
    for i in range(len(A)):
        if A[i] in dic:
            dic[A[i]]+=[i]
        else:
            dic[A[i]]=[i]
    bad=[]
    for x in dic:
        if len(dic[x])==2:
            bad=dic[x][:]
            break
    p1=bad[0]
    p2=n-bad[1]
    ans=[]
    ans+=[n]
    for k in range(2,n+1):
        ans+=[(bi(n+1,k)-bi(p1+p2,k-1))%MOD]
    ans+=[1]
    return ans

input()
A=list(map(int,input().strip().split(' ')))
for x in find(A):
    print(x)

Submission status: Accepted

Solution code:
from itertools import accumulate
from operator import mul

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

MOD = 10**9 + 7


# n + 1 個の整数からk個選ぶ組合せから重複する部分列の個数を差し引いて解を求める
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


f = [ModInt(1)] + list(
    accumulate(
        map(ModInt, range(1, n + 2)),
        mul
    )
)


def c(n, k):
    return (
        0 if n < k else
        f[n] / (f[n - k] * f[k])
    )


w = sum(a) - n * (n + 1) // 2
m = a.index(w) + a[::-1].index(w)
ans = '\n'.join(
    str(c(n + 1, k) - c(m, k - 1))
    for k in range(1, n + 2)
)

# 出力
print(ans)

Submission status: Accepted

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


import sys


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        if n < r:
            return 0
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
N = n+1
A = list(map(int, input().split()))
MOD = 10**9+7
# 重複する数字を見つける
already = set()
for i, l in enumerate(A):
    if l in already:
        dup_ind = i
        dup_num = l
        break
    else:
        already.add(l)
# 重複する数字について、その間にある数字の個数
mid_dup = dup_ind-A.index(dup_num)+1

F = FactMod(n+1, MOD)

# 全体から、重複分を除く
for k in range(1, n+2):
    all_pattern = F.comb(N, k)
    rem_pattern = F.comb(N-mid_dup, k-1)
    print((all_pattern-rem_pattern+MOD) % MOD)

Submission status: Accepted

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


import sys


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
N = n+1
A = list(map(int, input().split()))
MOD = 10**9+7
already = set()
for i, l in enumerate(A):
    if l in already:
        dup_ind = i
        dup_num = l
        break
    else:
        already.add(l)
before_first_dup_num = A.index(dup_num)
after_dup_num = N-dup_ind-1

F = FactMod(n+1, MOD)
for k in range(1, n+2):
    all_pattern = F.comb(N, k)
    rem_pattern = F.comb(before_first_dup_num+after_dup_num,
                         k-1) if before_first_dup_num+after_dup_num >= k-1 else 0
    print((all_pattern-rem_pattern+MOD) % MOD)

Submission status: Accepted

Solution code:
class BinomialCoefficient:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}                # n!
        self.inverse = {i: None for i in range(1, N+1)}      # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def binom(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dup_num = sum(A) - N*(N+1)//2
dup_num_idx = sorted([i+1 for i, a in enumerate(A) if a == dup_num])
l, r = dup_num_idx[0], dup_num_idx[1]

bc = BinomialCoefficient(N+1, MOD)
for k in range(1, N+2):
    print((bc.binom(N+1, k) - bc.binom(N+1 - (r - l + 1), k - 1)) % MOD)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def ex_euclid(a,b,c,d):
    if (b == 1) : return d
    x = a // b
    y = a % b
    return ex_euclid(b,y,d,(c[0]-x*d[0],c[1]-x*d[1]))
    

def mod_inv(a,p):
    x = ex_euclid(p,a,(1,0),(0,1))
    return x[1] % p

n = int(input())
visited = [-1 for i in range(n+1)]

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

for i in range(n+1):
    if(visited[a[i]] == -1):visited[a[i]] = i
    else : 
        x = visited[a[i]]
        y = i
        break

m = x + (n-y)

#n+1Ck - mC(k-1)

nc = n+1
mc = 1

print(nc-mc)

for i in range(2,n+2):
    nc = (nc * (n+2-i)) % MOD
    nc = (nc * mod_inv(i,MOD)) % MOD
    if (i-1 <= m):
        mc = (mc * (m+2-i)) % MOD
        mc = (mc * mod_inv(i-1,MOD)) % MOD
        print((nc - mc) % MOD)
    else:
        print(nc)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
a=[int(i)-1 for i in input().split()]
count=[0]*N
for i in range(N+1):
  count[a[i]]+=1
  if count[a[i]]==2:
    D=a[i]
    break
flag=False
k=0
mod=10**9+7
for i in range(N+1):
  if a[i]==D and not flag:
    flag=True
  elif a[i]==D and flag:
    break
  elif flag:
    k+=1
    
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

dp=[[0]*3 for i in range(N+2)]
dp[0][0]=1

for i in range(N+1):
  dp[i+1][0]=comb(N-1,i+1)
  dp[i+1][1]=-comb(N-k-1,i)+2*dp[i][0]
  if i>=1:
    dp[i+1][2]=dp[i-1][0]
  print(sum(dp[i+1])%mod)

Submission status: Accepted

Solution code:
from collections import Counter
mod=10**9+7
N=10**5+11
fac,finv,inv = [0]*N,[0]*N,[0]*N
 
def cmb_init():
        fac[0]=fac[1]=finv[0]=finv[1]=inv[1]=1
        for i in range(2,N):
                fac[i] = fac[i-1]*i%mod
                inv[i] = mod-inv[mod%i] * (mod//i) % mod
                finv[i] = finv[i-1] * inv[i] % mod
 
 
def cmb_mod(n,k):
        if n<k : return 0
        return fac[n]*(finv[k]*finv[n-k]%mod)%mod
 
n=int(input())
a=list(map(int,input().split()))
ac = Counter(a).most_common()[0][0]
sames=[i for i,x in enumerate(a) if x==ac]
same_len = sames[0]+(n-sames[1])
cmb_init()
print(n)
 
for i in range(1,n):
        nums = cmb_mod(n+1,i+1) - cmb_mod(same_len,i)
        if nums < 0: nums+=mod
        print(nums)
print(1)

Submission status: Accepted

Solution code:
N = int(input())
L = [-1] * N
a = [int(i)-1 for i in input().split()]
for i in range(N+1):
    if L[a[i]] == -1:
        L[a[i]] = i
    else:
        x1, x2 = (min(L[a[i]], i), max(L[a[i]], i))
A = x1
B = x2-x1-1
C = N-x2

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007


#階乗の逆元を求める
fac_lim = N
fac = [None]*(fac_lim+1)
fac[0] = 1
for i in range(fac_lim):
    fac[i+1] = fac[i] * (i+1)
    fac[i+1] = fac[i + 1] % 1000000007

fac_inv = [None]*(fac_lim+1)
fac_inv[fac_lim] = power(fac[fac_lim], 1000000005)
for i in range(fac_lim, 0, -1):
    fac_inv[i-1] = (fac_inv[i] * i)  % 1000000007

def conv(a, b):
    if a >= b:
        return (fac[a] * fac_inv[a-b] * fac_inv[b]) % 1000000007
    else:
        return 0

N1_conv = [0]*(N+2)
AC_conv = [0]*(N+2)
for i in range(N+2):
    N1_conv[i] = conv(N-1, i)
for i in range(N+2):
    AC_conv[i] = conv(A+C, i)
for K in range(1, N+2):
    ans = 0
    ans += N1_conv[K]
    if K>0:
        ans += AC_conv[K-1]
        ans += 2 * N1_conv[K-1]
        ans -= 2 * AC_conv[K-1]
    if K>1:
        ans += N1_conv[K-2]
    ans %= 1000000007
    print(ans)

Submission status: Accepted

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

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

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

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

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


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


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

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
mod = 10**9 +7
n = int(input())

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

inv = [1 for _ in range(n+1)]
for i in range(2,n):
    inv[i] = (-(mod//i) * inv[mod%i]) %mod    

facinv = [1 for _ in range(n+1)]
for i in range(n):
    facinv[i+1] = inv[i+1]*facinv[i]%mod

def comb(a, b):
    if a < b or b < 0:
        return 0
    return fac[a]*facinv[b]*facinv[a-b]
    
a = inpl()
x = sum(a) - n*(n+1)//2
Y = [i for i, v in enumerate(a) if v == x]
y = n-Y[1]+Y[0]

for k in range(1,n+2):
    ans = (comb(n-1, k) + 2*comb(n-1, k-1) + comb(n-1, k-2) - comb(y, k-1))%mod
    print(ans)

Submission status: Accepted

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

fact = {i: None for i in range(n+2)}                 # n!
inverse = {i: None for i in range(1, n+2)}       # inverse of n in the field Z/(MOD)Z
fact_inverse = {i: None for i in range(n+2)}  # inverse of n! in the field Z/(MOD)Z

fact[0] = fact[1] = 1
fact_inverse[0] = fact_inverse[1] = 1
inverse[1] = 1
for i in range(2, n+2):
    fact[i] = i * fact[i-1] % MOD
    inverse[i] = - inverse[MOD % i] * (MOD // i) % MOD
    fact_inverse[i] = inverse[i] * fact_inverse[i-1] % MOD

def combination(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return fact[n] * (fact_inverse[r] * fact_inverse[n-r] % MOD) % MOD

dup_num = sum(A) - n*(n+1)//2
dup_idx = []
for i, a in enumerate(A):
    if a == dup_num:
        dup_idx.append(i)
        
left, right = dup_idx[0], dup_idx[1]
        
for k in range(1, n+2):
    print((combination(n+1, k) - combination(n + 1 - (right - left + 1), k - 1)) % MOD)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

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

n = ni()
a = list(li())
# 2こあるものは何か
cnt = Counter(a)
two = cnt.most_common(1)[0][0]

left = a.index(two)
right = a[::-1].index(two)

# 二項係数準備
MOD = 10**9+7

inv = inv_mod(n+2,MOD)
fac = fact(n+2,MOD)
fac_inv = fact_inv(n+2,inv,MOD)

for i in range(1,n+2):
    if 1 < i < n+1:
        ans = nCr(n+1,i,MOD,fac,fac_inv)

        if left+right >= i-1:
            ans -= nCr(left+right,i-1,MOD,fac,fac_inv)
            
        if ans < 0:
            ans += MOD
            
        print(ans)
        
    elif i == 1:
        print(n)
    else:
        print(1)

Submission status: Accepted

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

ctr = Counter(A)
doub = ctr.most_common()[0][0]
i1 = A.index(doub)
i2 = N - A[::-1].index(doub)
l = N - (i2-i1)

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 n in range(1,N+2):
    ans.append(ncr(N+1,n))
for i in range(l+1):
    ans[i] -= ncr(l,i)
    ans[i] %= MOD

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

MOD = 10**9 + 7
 
N = read()
A = reads()

fact = [1] * N
for i in range(1, N):
  fact[i] = (fact[i-1] * i) % MOD 
invfact = [0] * N; invfact[-1] = pow(fact[-1], MOD-2, MOD)
for i in range(N-2, -1, -1):
  invfact[i] = invfact[i+1] * (i+1) % MOD
def comb(n, k):
  return fact[n] * invfact[n-k] * invfact[k] % MOD  

cnt = Counter(A)
q = next(i for i in range(1,N+1) if cnt[i] == 2)
i1 = A.index(q); i2 = A.index(q, i1+1)
m = N - (i2 - i1)
# print(m)

print(N)
for k in range(2, N+1):
  ans = comb(N-1, k-1) * 2 + comb(N-1, k-2)
  if m >= k-1:
    ans -= comb(m, k-1)
  if k <= N-1:
    ans += comb(N-1, k)
  print(ans % MOD)
print(1)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
deni=[1]*(N+1)#(k)!を格納
quot=[1]*(N+1)#(k)!の逆数を格納
for i in range(1,N+1):
    deni[i]=(deni[i-1]*(i+1))%mod
for i in range(1,N+1):
    t=pow(i+1,mod-2,mod)
    quot[i]=(quot[i-1]*t)%mod
deni=[1]+deni
quot=[1]+quot
box=[[0,0]]*(N+1)
for i in range(N+1):
    if box[A[i]-1][0]==1:
        k_1=box[A[i]-1][1]
        k_2=N-i
        break
    box[A[i]-1]=[1,i]
K=k_1+k_2
ans =[]
for k in range(1,N+2):
    if k==1:
        ans.append(N)
    elif K>=k-1:
        s=deni[N+1]
        s=(s*quot[k])%mod
        s=(s*quot[N+1-k])%mod
        t=deni[K]
        t=(t*quot[k-1])%mod
        t=(t*quot[K-k+1])%mod
        #print(s,t)
        ans.append((s-t)%mod)
    else:
        s=deni[N+1]
        s=(s*quot[k])%mod
        s=(s*quot[N-k+1])%mod
        #print(s)
        ans.append(s)
#print(ans)
print('\n'.join(map(str,ans)))

Submission status: Accepted

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

f_list = [1] * 100001
f_r_list = [1] * 100001

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

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

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

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

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

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


doubled = sum(a) - n * (n + 1) / 2
x = a.index(doubled)
y = a_r.index(doubled)
num = x + y

print(n)

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

Submission status: Accepted

Solution code:
from collections import Counter
mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
l = 0
for i in range(1,n+1):
	if C[i] > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
				if len(p) > 1:
					break
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)%mod
	t %= mod
	t *= pow(k+1,mod-2,mod)
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)%mod
		d %= mod
		d *= pow(k,mod-2,mod)
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
#重複始点終点調査
se=[]
c=sum(A)-N*(N+1)/2
for i in range(len(A)):
  if A[i]==c:
    se.append(i)

mod=10**9+7
 
#階乗計算
factorial=[1]
for i in range(1,N+2):
    factorial.append(factorial[i-1]*i %mod)
#逆元計算
inverse=[0]*(N+2)
inverse[N+2-1] = pow(factorial[N+2-1], mod-2,mod)
for i in range(N+2-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod
#combination計算
def nCr(n,r):
  if n<r or n==0 or r==0:
    return 0
  return factorial[n] * inverse[r] * inverse[n-r] % mod

print(N)
if N==1:
  print(N)
else:
  for i in range(1,N+1):
    print(int(nCr(N+1,i+1)-nCr(se[0]+N-se[1],i))%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

n = int(input())
A = inpl()
mod = 10**9 + 7

fct = [1]
inv = [1]

for i in range(1, n+2):
    fct.append((fct[-1]*i)%mod)
    inv.append((pow(fct[i], mod-2, mod)))

def comb(n, k):
    if k < 0 or k > n:
        return 0
    return (fct[n] * inv[n - k] * inv[k]) % mod    

C = ["" for i in range(n+1)]

for l, a in enumerate(A):
    if type(C[a]) == int:
        i, j = C[a], l
        break
    else:
        C[a] = l

print(n)

for k in range(2, n+2):
    total = comb(n+1, k)
    b = comb(n+i-j, k-1)
    res = (total-b)%(mod)
    print(res)