Problem:


Score : 600 points

Problem Statement

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

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

Notes

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

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

Constraints

1 \leq n \leq 10^5

1 \leq a_i \leq n

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

n and a_i are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
1 2 1 3

Sample Output 1

3
5
4
1

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

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

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

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

Sample Input 2

1
1 1

Sample Output 2

1
1

There is one subsequence with length 1: 1.

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

Sample Input 3

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

Sample Output 3

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

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



Sample input:
3
1 2 1 3


Sample output:
3
5
4
1

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    def find_duplicate(L):
        n = len(L)
        table = [None] * n
        for i, num in enumerate(L):
            if table[num] is not None:
                return table[num], i
            else:
                table[num] = i

    def make_factorial_table(size, mod):
        '''
        fact_mod[i] は i! % mod を表す。fact_mod[0] ~ facto_mod[size] まで計算可能なテーブルを返す
        >>> make_factorial_table(20, 10**9+7)
        [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 227020758, 178290591, 674358851, 789741546, 425606191, 660911389, 557316307, 146326063]
        '''
        fact_mod = [1] * (size + 1)
        for i in range(1, size + 1):
            fact_mod[i] = (fact_mod[i - 1] * i) % mod
        return fact_mod

    def combination(n, r, mod, fact_table):
        '''
        フェルマーの小定理 
        a ^ p-1 ≡ 1 (mod p)
        a ^ p-2 ≡ 1/a (mod p) (逆元)
        nCr = (n!) / ((n-r)! * r!) だが、mod p の世界ではこの分母を逆元を用いて計算しておくことが可能
        
        >>> m = 1000000007
        >>> fact_table = make_factorial_table(100, m)
        >>> combination(10, 5, m, fact_table)
        252
        >>> combination(100, 50, m, fact_table)
        538992043
        '''
        if r > n:
            return 0
        numerator = fact_table[n]
        denominator = (fact_table[n-r] * fact_table[r]) % mod
        # pow はすでに繰り返し二乗法で効率的に実装されている
        return (numerator * pow(denominator, mod-2, mod)) % mod

    n = ii()
    L = lmi_0()
    i, j = find_duplicate(L)
    fact = make_factorial_table(n+1, mod)

    for l in range(1, n+2):
        print((combination(n+1, l, mod, fact) - combination(i+n-j, l-1, mod, fact)) % mod)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def exteuc(a, b):
    # ax + by = gcd(a, b)
    if b == 0:
        return 1, 0, a
    y, x, v = exteuc(b, a % b)
    y -= (a//b) * x
    return x, y, v


def modinv(a, mod):
    x, _, _ = exteuc(a, mod)
    return x % mod


def main():
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # calculate duplicate indices
    # Ex. [1, 4, 2, 1, 3] -> 0, 3
    dup_first_index, dup_second_index = -1, -1
    indices = [-1 for _ in range(N)]
    for i, a in enumerate(A):
        if indices[a - 1] != -1:
            dup_first_index, dup_second_index = indices[a - 1], i
            break
        indices[a - 1] = i
    # Ex. [1, 4, 2, 5, 4, 3, 6] -> [1] + [3, 6] -> 3
    s = dup_first_index + N - dup_second_index
    # calculate answer
    ans = [0 for _ in range(N + 1)]
    comb_n1, comb_s = N + 1, 1  # comb(N + 1, 1), comb(s, 0)
    for i in range(N + 1):
        ans[i] = comb_n1  # comb(N + 1, i + 1)
        comb_n1 *= (N + 1) - (i + 1)
        comb_n1 *= modinv(i + 2, MOD)
        comb_n1 %= MOD
        if s >= i:
            ans[i] -= comb_s  # comb(s, i)
            comb_s *= s - i
            comb_s *= modinv(i + 1, MOD)
            comb_s %= MOD
        ans[i] %= MOD
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
num = [-1] * (n + 1)
for i in range(n + 1):
    if num[a[i]] == -1:
        num[a[i]] = i
    else:
        samei, samej = num[a[i]], i
        break
x = n + samei - samej
same = 1
comb = n + 1
print(comb - 1)
for i in range(2, n + 2):
    comb = (comb * (n - i + 2) * pow(i, mod - 2, mod)) % mod
    if i - 1 <= x:
        same = (same * (x - i + 2) * pow(i - 1, mod - 2, mod)) % mod
    else:
        same = 0
    print((comb - same) % mod)

Submission status: Accepted

Solution code:

class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


n = int(input())
*a, = map(int, input().split())
indices = [-1]*n
l, r = 0, 0
for i in range(n+1):
    if indices[a[i]-1] != -1:
        l = indices[a[i]-1]
        r = i
        break
    indices[a[i]-1] = i

MOD = 10**9+7
n += 1
c = Combination(n, MOD)
k = n-(r-l+1)
for i in range(1, n+1):
    ans = c.choose(n, i)
    if i == 1:
        ans -= 1
    elif k >= (i-1):
        ans -= c.choose(k, i-1)
    print((ans+MOD) % MOD)

Submission status: Accepted

Solution code:

class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def choose(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod


n = int(input())
*a, = map(int, input().split())
indices = [-1]*n
l, r = 0, 0
for i in range(n+1):
    if indices[a[i]-1] != -1:
        l = indices[a[i]-1]
        r = i
        break
    indices[a[i]-1] = i

MOD = 10**9+7
c = Combination(n+2, MOD)
for i in range(1, n+2):
    ans = c.choose(n+1, i) - c.choose(l+n-r, i-1)
    ans = (ans+MOD) % MOD
    print(ans)

Submission status: Accepted

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

import collections
c = collections.Counter(al)
cc = c.most_common()[0][0]

da = ([i for i, x in enumerate(al) if x ==cc ][0])
db = ([i for i, x in enumerate(al) if x ==cc ][1])

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

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

print(n)
for i in range(2,n+2):
    print((cmb(n-1,i,p)+ cmb(n-1,i-1,p)*2 -cmb(da+n-db,i-1,p) + cmb(n-1,i-2,p)) % p)

Submission status: Accepted

Solution code:
mod = 1000000007
n= int(input())
a= list(map(int,input().split()))
check = [0]*(n+1)
g1=[1,1]
g2=[1,1]
inverse=[0,1]
for i in range(2,n+1+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)
def cmb2(n,r):
    mod = 1000000007
    if (r<0 or r>n ):return 0
    r = min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%mod
r=-1
jn=-1
for i in range(n+1):
    check[a[i]-1]+=1
    if check[a[i]-1]==2:
        jn,r=a[i],i
        break
l=a.index(jn)
s = min(l,n-r)
t = max(l,n-r)
print(n)
for p in range(2,n+1):
  w2=cmb2(n+1,p)
  y2=cmb2(s+t,p-1)
  print(((w2+mod)-y2) % mod)
print(1)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline


def solve():
    N = int(input())
    d = {i:-1 for i in range(1, N+1)}
    *l, = map(int, input().split())

    MOD = 10**9+7
    n = N+1
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD if a>=b else 0

    for i, j in enumerate(l):
        if d[j] != -1:
            break
        d[j] = i

    v = d[j]+N-i
    for i in range(1, N+2):
        print((comb(N+1, i)-comb(v, i-1))%MOD)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())
d = {i:-1 for i in range(1, N+1)}
*l, = map(int, input().split())

MOD = 10**9+7
n = N+1
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD if a>=b else 0

for i, j in enumerate(l):
    if d[j] != -1:
        break
    d[j] = i

a = d[j]
b = N-i
for i in range(1, N+2):
    print((comb(N+1, i)-comb(a+b, i-1))%MOD)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
a = list(map(int, input().split()))
#互いに素なa,bについて、a*x+b*y=1の一つの解
def mod_combination(n,k,mod):
    if k == 0:
        return 1
    return (n*mod_inv(k,mod) * mod_combination(n-1,k-1,mod) ) % mod
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
mod = 10**9+7
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
combi = [0 for i in range(n+2)]
combi[0] = 1
for i in range(1,n+2):
    combi[i] = (combi[i-1]*(n-i+2)*mod_inv(i,mod)) % mod
kind = set()
left = -1
right = -1
for i in range(n+1):
    if a[i] in kind:
        right = (n - i)
        left = a.index(a[i])
        break
    else:
        kind.add(a[i])
combi_remain = [0 for i in range(left + right+3)]
combi_remain[0] = 1
for i in range(1,left+right+2):
    combi_remain[i] = (combi_remain[i-1]*(left+right-i+1)*mod_inv(i,mod)) % mod
for i in range(1,n+2):
    if i-1 <= left+right:
        print((combi[i] - combi_remain[i-1]) % mod)
    else:
        print(combi[i]%mod)

Submission status: Accepted

Solution code:
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
MOD = 10**9+7
for i in range(2, 10**5+10):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

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

N = int(input())
A = map(int, input().split())
d = {}
n1 = n2 = -1
for i, a in enumerate(A):
  if a in d:
    n1 = N - i
    n2 = d[a]
    break
  d[a] = i

ans = [0] * (N+1)
for k in range(1, N+2):
  ans[k-1] = (comb(N+1, k) - comb(n1+n2, k-1)) % MOD

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    n=int(input())
    a=list(map(int1,input().split()))
    index=[-1]*n
    for i,x in enumerate(a):
        if index[x]==-1:
            index[x]=i
        else:
            d=(index[x],i)
            break
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
        fac[0]=fac[1]=1
        finv[0]=finv[1]=1
        inv[1]=1
        for i in range(2,(n+1)):
            fac[i]=fac[i-1]*i%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(n,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    for i in range(1,n+2):
        ans=COM(n-1,i)
        p=COM(d[0]+n-d[1],i-1)
        q=COM(n-1,i-1)-p
        ans+=p+q*2
        ans+=COM(n-1,i-2)
        print(ans%MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
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,*A = map(int, open(0).read().split())
Cnt = Counter(A)
for i in range(1,N+1):
  if Cnt[i]==2:
    p = i
    break
a = A.index(p)
b = A[::-1].index(p)
for i in range(1,N+2):
  print((cmb(N+1,i,mod)-cmb(a+b,i-1,mod))%mod)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
cnt=[0 for i in range(n+1)]
mod=10**9+7
fact=[1]*(n+2)
inv=[1]*(n+2)
for i in range(2,n+2):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n+1,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod if x>=y>=0 else 0
for i in range(n+1):
    if cnt[l[i]]:
        r=cnt[l[i]]+n-i;break
    cnt[l[i]]+=i
else:r=n-cnt[l[0]]
for i in range(1,n+2):
    print((comb(n+1,i)-comb(r,i-1))%mod)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
l1 = [[l[i],i] for i in range(n+1)]
l1.sort()
for i in range(n):
    if l1[i][0] == l1[i+1][0]:
        a,b = l1[i][1],l1[i+1][1]

m = b-a+1
k = n-m+1

mod = 10**9+7 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,n+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod


for i in range(1,n+2):
    a = nCr(n+1,i,mod) -nCr(k,i-1,mod)
    
    print(a%mod)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)
for i in range(n+1):
    if b[a[i]] == 0:
        b[a[i]] += 1
    else:
        d = a[i]

l = 0
r = 0
c = 0
for i in range(n+1):
    if a[i] != d and c == 0:
        l += 1
    elif a[i] != d and c == 2:
        r += 1
    elif a[i] == d:
        c += 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 = 100011
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(1, n+2):
    print((cmb(n+1, i, mod)-cmb(r+l, i-1, mod))%mod)

Submission status: Accepted

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

MOD=10**9+7
inv_table = [0]+[1]
for i in range(2,n+2):
  inv_table.append(-(MOD//i)*inv_table[MOD%i]%MOD)

dic_a={}
same_pair=None
for i in range(n+1):
  if alist[i] in dic_a:
    same_pair=(dic_a[alist[i]],i)
    break
  else:
    dic_a[alist[i]]=i
pair_diff=n-(same_pair[1]-same_pair[0])
#print(same_pair,pair_diff)

comb1,comb2=1,1
for r in range(1,n+2):
  comb1*=(n-r+2)*inv_table[r]
  comb1%=MOD
  #print(comb1,comb2)
  print((comb1-comb2)%MOD)
  comb2*=(pair_diff-r+1)*inv_table[r]
  comb2%=MOD

Submission status: Accepted

Solution code:
N, *X = map(int, open(0).read().split())

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

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

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

# Find indices of duplicated values
indices = [-1] * (N + 1)
for i in range(N + 1):
    if indices[X[i]] < 0:
        indices[X[i]] = i
    else:
        l = indices[X[i]]
        r = i
        break

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

Submission status: Accepted

Solution code:
MOD = 1000000000+7
n = int(input())
a = list(map(int,input().split()))

count = [0]*n
for i,ai in enumerate(a,1):
    count[ai-1] += 1
    if(count[ai-1] == 2):
        common = a.index(ai) + (n+1-i)
        break

fac = [1]*(n+2)
fac_inv =  [0]*(n+2)

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

for i in range(1,n+2):
    ans = (fac[n+1] * (fac_inv[i] * fac_inv[n+1-i])%MOD)%MOD
    if common >= i-1:
        ans -= (fac[common] * (fac_inv[i-1] * fac_inv[common - (i-1)])%MOD)%MOD
    print(ans%MOD)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split());b={};M=10**9+7;p=n+1;q=r=1
for i,x in enumerate(a):
 if x in b:d=i-b[x];break
 b[x]=i
for k in range(n+1):print((p-q)%M);q=q*(n-d-k)*r%M;r=pow(k+2,M-2,M);p=p*(n-k)*r%M

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split());b={};M=10**9+7
for i,x in enumerate(a):b.setdefault(x,[]).append(i)
p=n+1;q=r=1;d=[abs(j[0]-j[1])for x,j in b.items()if len(j)>1][0]
for k in range(n+1):print((p-q)%M);q=q*(n-d-k)*r%M;r=pow(k+2,M-2,M);p=p*(n-k)*r%M

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
M = 10 ** 9 + 7

n = int(input())
a = list(map(int, input().split()))
assert len(a) == n + 1

b = [None] * (n + 1)
d1, d2 = -1, -1
for i in range(n + 1):
    if b[a[i]] is None:
        b[a[i]] = i
    else:
        d1 = b[a[i]]
        d2 = i
        break
assert d1 >= 0 and d2 >= 0 and a[d1] == a[d2]


a, b, ik = n + 1, 1, 1
for k in range(1, n + 2):
    ans = (a - b) % M
    print(ans)
    b = b * (n + 1 - d2 + d1 - k) * ik % M
    ik = pow(k + 1, M - 2, M)
    a = a * (n + 1 - k) * ik % M

Submission status: Accepted

Solution code:
def mod_rep_pow(a, n, mod=(10 ** 9 + 7)):
    res = 1
    while 0 < n:
        if n & 1:
            res = (res * a) % mod
            n -= 1
        else:
            a = (a ** 2) % mod
            n //= 2
    return (res % mod)


def mod_inverse(a, mod=(10 ** 9 + 7)):
    return mod_rep_pow(a, (mod - 2))


def mod_comb(facts, facts_inverse, n, k, mod=(10 ** 9 + 7)):
    return (facts[n] * facts_inverse[k] * facts_inverse[n - k])


n = int(input().strip())
a = list(map(int, input().split()))
not_unique = sum(a) - sum([i for i in range(1, n + 1)])
b = []
for i in range(n + 1):
    if a[i] == not_unique:
        b.append(i)
x = n - (b[1] - b[0])
mod = 10 ** 9 + 7
facts = [1] * (n + 2)
for i in range(0, n + 1):
    facts[i + 1] = (facts[i] * (i + 1) % mod)

facts_inverse = [1] * (n + 2)
facts_inverse[n + 1] = mod_inverse(facts[n + 1])
for i in range(n + 1, 0, -1):
    facts_inverse[i - 1] = (facts_inverse[i] * (i)) % mod

for i in range(1, n + 2):
    if x < (i - 1):
        print(mod_comb(facts, facts_inverse, (n + 1), i) % mod)
    else:
        print((mod_comb(facts, facts_inverse, (n + 1), i) - (mod_comb(facts, facts_inverse, x, (i - 1)))) % mod)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
MAXN = 100005
factorial = [1]
for i in range(1, MAXN + 1):
    factorial.append(factorial[-1] * i % MOD)

inv_factorial = [-1] * (MAXN + 1)
inv_factorial[-1] = pow(factorial[-1], MOD-2, MOD)
for i in reversed(range(MAXN)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

def fact(n):
    return factorial[n]

def nck(n, k):
    if k > n or k < 0:
        return 0
    else:
        return factorial[n]*inv_factorial[n - k]*inv_factorial[k]%MOD

def main():
    n = int(input())
    a = list(map(int,input().split()))
    dic = {i:[] for i in range(1,n + 1)}
    for i in range(n + 1):
        dic[a[i]].append(i)
        if len(dic[a[i]]) >= 2:
            l,r = dic[a[i]][0],dic[a[i]][1]
            break

    r = n - r
    print(n)
    for i in range(2,n + 2):
        print((nck(n + 1,i) - nck(l + r,i - 1) + MOD)%MOD)
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 + 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()))
 
val = sum(A) - sum(set(A))
i = -1
j = -1
for k in range(n+1):
    if A[k] == val:
        if i == -1:
            i = k
        elif j == -1:
            j = k
            break
for k in range(1,n+2):
    print((cmb(n+1, k, mod) - cmb(n + i - j, k - 1, mod)) % mod)

Submission status: Accepted

Solution code:
import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
id=0
frac=[1]*(10**5+10)
fracinv=[0]*(10**5+10)
p=10**9+7
c=collections.Counter(a)
id=c.most_common()[0][0]
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
for i in range(0,10**5+10):
    fracinv[i]=modinv(frac[i],p)
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
N=n+1
short=N-(max(buf)-min(buf))

#print(short,N)

for i in range(1,n+2,1):
    if short-i<0:
        sub1=0
    else:
        sub1 = (((frac[short] * fracinv[i]) % p) * fracinv[short-i]) % p

    if short-i-1<0:
        sub2=0
    else:
        sub2 = (((frac[short - 1] * fracinv[i]) % p) * fracinv[short - i - 1]) % p
    all=(((frac[N]*fracinv[i])%p)*fracinv[N-i])%p

    #print(all,sub1,sub2)
    print((all-(sub1-sub2)%p)%p)

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 + 1 # N >= n
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()))

val = sum(A) - sum(set(A))
i = -1
j = -1
for k in range(n+1):
    if A[k] == val:
        if i == -1:
            i = k
        elif j == -1:
            j = k
            break
for k in range(1,n+2):
    print((cmb(n+1, k, mod) - cmb(n + i - j, k - 1, mod)) % mod)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 2個ある要素を1つだけ選び，他を2要素より外側から
# 取るときだけ重複する

# nCk
## 0!~n!をmodしつつ求める
def fact_all(n,M=mod):
    f = [1]*(n+1)
    ans = 1
    for i in range(1,n+1):
        ans = (ans*i)%M
        f[i] = ans
    return f

## inv(0!)~inv(n!)をmodしつつ求める
def fact_inv_all(fact_all,M=mod):
    N = len(fact_all)
    finv = [0]*N
    finv[-1] = pow(fact_all[-1],M-2,M)
    for i in range(N-1)[::-1]:
        finv[i] = finv[i+1]*(i+1)%M
    return finv

## nCkをmodしつつ返す
def nCk(n,k,fact_list,inv_list,M=mod):
    return (((fact_list[n]*inv_list[k])%M)*inv_list[n-k])%M

n = I()
a = LI()

place = [-1]*(n+1)
for i in range(n+1):
    if place[a[i]] != -1:
        p1 = place[a[i]]
        p2 = i
        break
    else:
        place[a[i]] = i

fl = fact_all(n+1)
il = fact_inv_all(fl)

for i in range(1,n+2):
    ans = nCk(n+1,i,fl,il)
    if p1+n-p2 >= i-1:
        ans -= nCk(p1+n-p2,i-1,fl,il)
        ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
# solution

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:
mod = 10**9+7
MAX = 10**5+1
fact = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i)%mod
inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[mod%i]*(mod-mod//i)%mod
fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1]*inv[i]%mod
def comb(n, r):
    if n < r:
        return 0
    return fact[n]*fact_inv[n-r]*fact_inv[r] % mod

n = int(input())
L = list(map(int,input().split()))
M = []
for i in range(n+1):
    M.append(L[i])
M.sort()
dou = 1 #重複する数
for i in range(n+1):
    if M[i] == dou:
        dou += 1
    else:
        dou = M[i]
        break
l = 0
r = 0
cnt = 0
for i in range(n+1):
    if L[i] == dou and cnt == 0:
        l = i+1
        cnt += 1
    elif L[i] == dou and cnt == 1:
        r = i+1
        break
for i in range(1,n+1):
    print((comb(n+1,i)-comb(l+n-r,i-1))%mod)
print(1)