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
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


# --------------------------------------------

dp = None


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


class Combination:
    def __init__(self, n, mod=(10**9 + 7)):

        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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

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


def main():
    N = int(input())
    A = li_input()

    C = Combination(N + 1)

    double_elem = sum(A) - sigma(N)

    l, r = -1, -1

    for i, a in enumerate(A, start=1):
        if a == double_elem:
            if l == -1:
                l = i
            else:
                r = i
                break

    for i in range(1, N + 2):
        print((C(N + 1, i) - C(l - 1 + N + 1 - r, i - 1)) % (10**9 + 7))


main()

Submission status: Accepted

Solution code:
MOD = 10**9+7
facts = [1]
for i in range(1, 10**5+2):
    facts.append((i*facts[i-1])%MOD)
def nCk(n, k):
    if n < k: return 0
    return (facts[n]*pow(facts[k], MOD-2, MOD)%MOD * pow(facts[n-k], MOD-2, MOD))%MOD

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

# Search doubling number and its indexes
indexes = [[] for _ in range(n+1)] # 0 to n:max(a)
for i in range(n+1):
    indexes[a[i]].append(i)
for idx in indexes:
    if len(idx) == 2: idxs = sorted(idx)

for k in range(1, n+1+1):
    p_all = nCk(n+1, k)
    p_double = nCk(n+1-(idxs[1]-idxs[0]+1), k-1)
    print((p_all-p_double)%MOD)

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
import queue
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap
  
  
class Combination:
    def __init__(self, n, mod):

        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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

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


@mt
def slv(N, A):
    MOD = 10**9+7
    c = Counter(A)
    k = c.most_common(1)[0][0]
    i = A.index(k)
    j = i + A[i+1:].index(k)

    cmb = Combination(N+1, MOD)
    for k in range(1, N+2):
        ans = cmb(N+1, k) - cmb(i+N-(j+1), k-1)
        ans %= MOD
        print(ans)


def main():
    N = read_int()
    A = read_int_n()

    (slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
import queue
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


class Combination:
    def __init__(self, n, mod):

        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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

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


@mt
def slv(N, A):
    MOD = 10**9+7
    c = Counter(A)
    k = c.most_common(1)[0][0]
    i = A.index(k)
    j = i + A[i+1:].index(k)

    cmb = Combination(N+1, MOD)
    for k in range(1, N+2):
        ans = cmb(N+1, k) - cmb(i+N-(j+1), k-1)
        ans %= MOD
        print(ans)


def main():
    N = read_int()
    A = read_int_n()

    (slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
P=10**9+7
A=[int(i) for i in input().split()]
B=[-1 for i in range(N)]
s=(-1,-1)
for i in range(N+1):
    if B[A[i]-1]==-1:
        B[A[i]-1]=i
    else:
        s=(B[A[i]-1],i)
        break
M=N-s[1]+s[0]+1
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)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(N+2)]
Finv=[0 for i in range(N+2)]
Fact[0]=1
Finv[0]=1
for i in range(1,N+2):
    Fact[i]=(i*Fact[i-1])%P
    Finv[i]=inv(Fact[i])%P
def C(n,k):
    return (((Fact[n]*Finv[k])%P)*Finv[n-k])%P
ans=[0 for i in range(N+1)]
for i in range(1,N+2):
    if i<=M:
        ans[i-1]=(C(N+1,i)-C(M-1,i-1))%P
    else:
        ans[i-1]=C(N+1,i)%P
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl_int(): return list(map(int, input().split()))
def inpl_str(): return list(map(int, input().split()))

def Comb(n):
    gyakugen = [1]*(n+1)
    fac = [1]*(n+1)

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

    gyakugen[n] = pow(fac[n],mod-2,mod)

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

    com = [1]*(n+1)

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

    return com

N = int(input())
aa = inpl_int()

i = 1
dd = defaultdict(int)
for i,a in enumerate(aa):
	if dd[a] == 0:
		dd[a] = i+1
	else:
		X1 = dd[a]-1
		X2 = i

L,R = X1,N-X2
ALL = 1

ALL = Comb(N+1)
daburi = Comb(L+R)

for i in range(1,N+2):
	if L+R+1 >= i:
		print((ALL[i]-daburi[i-1])%mod)
	else:
		print(ALL[i]%mod)

Submission status: Accepted

Solution code:
# Pythonの組み込み関数powを使ったバージョン
MOD = 10**9+7

fact, invfact = [0]*(10**5+2), [0]*(10**5+2)
fact[0], invfact[0] = 1, 1

for i in range(1, 10**5+2):
  fact[i] = (fact[i-1]*i)%MOD
  invfact[i] = pow(fact[i], MOD-2, MOD)

def mod_comb(n, r):
  if n<r or n==0 or r==0: return 0
  return (((fact[n]*invfact[r])%MOD)*invfact[n-r])%MOD

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
for i, ele in enumerate(a):
  if d[ele] == 0:
    d[ele]= i+1
  else:
    l = d[ele]
    r = i+1

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

Submission status: Accepted

Solution code:
MOD = 10**9+7

def mod_pow(x, n):
  if x==0: return 1
  res = 1
  while n > 0:
    if n&1:
      res = (res*x)%MOD
    x = (x*x)%MOD
    n >>= 1
  return res

fact, invfact = [0]*(10**5+2), [0]*(10**5+2)
fact[0], invfact[0] = 1, 1
for i in range(1, 10**5+2):
  fact[i] = (fact[i-1]*i)%MOD
  invfact[i] = mod_pow(fact[i], MOD-2)%MOD

def comb(n, r):
  if n<r or n==0 or r==0: return 0
  return (((fact[n]*invfact[r])%MOD)*invfact[n-r])%MOD

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
for i, ele in enumerate(a):
  if d[ele] == 0:
    d[ele]= i+1
  else:
    l = d[ele]
    r = i+1

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

Submission status: Accepted

Solution code:
N = int(input())
e = list(map(int,input().split()))
mod = 1000000007
kai = [0]*(N+3)
from collections import Counter
c = Counter(e).most_common(1)[0][0]
g = e.index(c)
e.remove(c)
f = e.index(c) +1
e = []
for i in range(N+3):
  if i ==0:
    kai[i] = 1
  else:
    kai[i] = (kai[i-1]*(i))%mod
def comb(n,k,p):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=kai[n] 
  b=kai[k] 
  c=kai[n-k] 
  b = pow(b,mod-2,mod)
  c = pow(c,mod-2,mod)
  return (a*b*c)%mod
h = [1]*((N+6)//2)
for j in range((N+4)//2):
  h[j+1] = comb(N+1,j+1,mod)
for j in range(N+1):
  if N-j>N/2:
    print((h[j+1]-comb(g+N-f,j,mod)+mod)%mod)
  else:
    print((h[N-j]-comb(g+N-f,j,mod)+mod)%mod)

Submission status: Accepted

Solution code:
# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


n = int(input())
A = list(map(int, input().split()))
C = [-1] * (n+1)
lr = 0
for i, a in enumerate(A):
    if C[a] == -1:
        C[a] = i
    else:
        lr = C[a] + n - i
        break


def combination(n, mod):
    lst = [1]
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst


mod = 10**9+7
NC = combination(n+1, mod)
LRC = combination(lr, mod)
for i in range(1, n+2):
    print((NC[i] - (LRC[i-1] if i-1 <= lr else 0)) % mod)

Submission status: Accepted

Solution code:
def comb(n,k):
	if n<k or n==0: return 0
	elif k==0: return 1
	else: return f[n]*p[k]*p[n-k]%(10**9+7)
from collections import Counter
n = int(input())
print(n)
a = [int(i) for i in input().split()]
twice = Counter(a).most_common(1)[0][0]
x,y = (i for i,j in enumerate(a) if j == twice)
num,y,f,p = 1,n-y,[1],[1]
for i in range(1,n+2):
	f.append(f[-1]*i%(10**9+7))
	p.append(pow(f[-1],10**9+5,10**9+7))
for i in range(2,x+y+2): print((comb(n+1,i)-comb(x+y,i-1))%(10**9+7))
for i in range(x+y+2,n+2): print(comb(n+1,i))

Submission status: Accepted

Solution code:
"""
実験のためにkobaya0514様のコードをいじくらせていただいております
"""

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)
l = se[0]
r = se[1]

mod = 10 ** 9 + 7

# 階乗計算
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)))


# 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)
for i in range(2, N + 2):
    print(int(nCr(N + 1, i) - nCr(l + N - r, i - 1)) % mod)

Submission status: Accepted

Solution code:
from collections import Counter

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

ctr = Counter(src)
most = ctr.most_common(1)[0][0]
i1 = src.index(most)
i2 = src[i1+1:].index(most) + i1+1
d = i2 - i1

MOD = 10**9+7

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,N+3):
    f = mul(fac[n-1], n)
    fac.append(f)
    fac_inv.append(inv(f))

def ncr(n,r):
    return mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])

anss = []
for r in range(1,N+2):
    anss.append(ncr(N+1,r))
n = N-d
for r in range(n+1):
    anss[r] -= ncr(n,r)
    anss[r] %= MOD

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

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
c = Counter(A).most_common(1)[0][0]
B = []
mod = 10**9+7

for i in range(N+1):
    if A[i]==c:
        B.append(i)

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

def C(n,r):
    if n<r or n==0 or r==0:
        return 0
    else:
        return F[n]*I[r]*I[n-r]%mod

r0 = B[0]+N-B[1]

for i in range(1,N+2):
    Ans = (C(N+1,i) - C(r0,i-1))%mod
    print(Ans if i>1 else Ans-1)

Submission status: Accepted

Solution code:
from statistics import mode

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

# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

# 階乗・逆元の値を保存
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1]*i % MOD)
    inverse.append((pow(factorial[i], MOD-2, 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)
for i in range(2, N+2):
    print(int(nCr(N+1, i) - nCr(outside, i-1)) % 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)
l=se[0]
r=se[1]

mod=10**9+7
 
#階乗計算
factorial=[1]
inverse=[1]
for i in range(1,N+2):
    factorial.append(factorial[-1]*i %mod)
    inverse.append((pow(factorial[i], mod-2, 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)
for i in range(2,N+2):
    print(int(nCr(N+1,i)-nCr(l+N-r,i-1))%mod)

Submission status: Accepted

Solution code:
def d_11(N, A):  # N:整数の種類, A:数列
    M = 10**9 + 7  # 求めた解の剰余をこれで取る

    # 重複した数のインデックスを求める
    from collections import Counter
    c = Counter(A).most_common(n=1)[0][0]  # 重複した整数の値を取得
    index = [i for i, x in enumerate(A) if x == c]  # 重複した整数のインデックス
    l = index[0] + 1
    r = index[1] + 1

    # フェルマーの小定理を用いてコンビネーションを効率よく計算
    factrial = [1] * (N + 2)  # 0~N+1までの階乗のテーブルを作る
    for k in range(1, N + 2):
        factrial[k] = (factrial[k - 1] * k) % M

    fact_inv = [1] * (N + 2)
    fact_inv[N + 1] = pow(factrial[N + 1], M - 2, M)
    for k in range(N, -1, -1):
        fact_inv[k] = (fact_inv[k + 1] * (k + 1)) % M

    def nCr(n, r, M):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n - r]) % M

    ans = ''
    for k in range(1, N + 2):
        ans += '{}\n'.format((nCr(N + 1, k, M) -
                              nCr((l - 1) + (N + 1 - r), k - 1, M)) % M)
    return ans[:-1]

N = int(input())
A = [int(i) for i in input().split()]
print(d_11(N, A))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
import math
n=input()
a=map(int, raw_input().split())
b=Counter(a)
freq_val=b.most_common(1)[0][0]


index_num=[n for n, v in enumerate(a) if v==freq_val]
d=index_num[1]-index_num[0]


div = int(1e9 + 7)
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, n + 2):
    fact_tmp *= i
    fact_tmp %= div
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, div - 2, div))


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


for k in range(1,n+2):
	print (combination(n+1,k)-combination(n-d,k-1))% div

Submission status: Accepted

Solution code:
def comb(k,r):
  """kCpを求める"""
  if k<0 or r<0 or r>k: return 0
  elif k==0 or r==0: return 1
  else:
    return (X[k]*Y[r]*Y[k-r])
  
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
n = int(input())
a = list(map(int,input().split()))
p=10**9+7
ans=0
X=[1]  #階乗テーブル
for i in range(1,n+2):
  X+=[ (X[-1]*i) %p ]
Y=[1]*(n+2)  #階乗の逆元テーブル
Y[n+1]=power_func(X[n+1],p-2,p)
for i in range(n,-1,-1):
  Y[i]=Y[i+1]*(i+1) %p

#ダブりをみつける
check = [0]*n
for i in range(n+1):
  if check[a[i]-1]==1: dub = a[i]
  else: check[a[i]-1] = 1

indexes = [i for i, x in enumerate(a) if x == dub]
ind1, ind2  = indexes[0], indexes[1]

for i in range(1,n+2):
  ans = comb(n+1, i)
  if ind1 + n -ind2 +1 >= i:
    ans -= comb(ind1 + n -ind2, i-1)
  print(ans%p)

Submission status: Accepted

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

dup = sum(a) - n * (n + 1) // 2
d1 = a.index(dup)
d2 = a.index(dup, d1 + 1)

N = n + 1
Ndup = d1 + n - d2

MOD = 10 ** 9 + 7

# inv[k]: kの逆元
inv = [0 for i in range(N + 1)]
inv[1] = 1
for i in range(2, N + 1):
    inv[i] = (-(MOD // i) * inv[MOD % i]) % MOD

C = N
Cdup = 1
print(N - 1)
for k in range(2, N + 1):
    C = (C * (N - k + 1) * inv[k]) % MOD
    Cdup = (Cdup * (Ndup - k + 2) * inv[k - 1]) % MOD
    print((C - Cdup) % MOD)

Submission status: Accepted

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

dup = sum(a) - n * (n + 1) // 2
d1 = a.index(dup)
d2 = a.index(dup, d1 + 1)

N = n + 1
Ndup = d1 + n - d2

MOD = 10 ** 9 + 7

def power(x, n):
    ans = 1
    while n:
        if n % 2 == 1:
            ans = (ans * x) % MOD
        x = (x * x) % MOD
        n //= 2
    return ans

# fack[k]: kの階乗
fact = [0 for i in range(N + 1)]
fact[0] = 1
for i in range(1, N + 1):
    fact[i] = (fact[i - 1] * i) % MOD

# inv[k]: kの階乗の逆元
inv = [0 for i in range(N + 1)]
inv[N] = power(fact[N], MOD - 2) % MOD
for i in range(N - 1, -1, -1):
    inv[i] = (inv[i + 1] * (i + 1)) % MOD

def comb(n, r):
    if n < r:
        return 0
    else:
        return (fact[n] * inv[n - r] * inv[r]) % MOD

for k in range(1, N + 1):
    C = comb(N, k)
    Cdup = comb(Ndup, k - 1)
    print((C - Cdup) % MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, combinations
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right

INF = 10 ** 10


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, (n, k)
        a = self.fact[n]
        b = (self.inv[k] * self.inv[n - k]) % self.mod
        return a * b % self.mod


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

    dual = Counter(a_list).most_common(1)[0][0]
    pre, post = [i for i, a in enumerate(a_list) if a == dual]
    x = pre + (n - post)

    comb = Combination(10 ** 5 + 1, MOD)
    for i in range(1, n + 2):
        a, b = comb.nCr(n + 1, i), 0
        if i == 1:
            b = 1
        elif 0 < x and i - 1 <= x:
            b = comb.nCr(x, i - 1)
        print((a - b) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def D_11(x):
    n = x[0]  # 整数の数
    a = x[1:]  # 数列
    M = 10**9 + 7  # 求めた解の剰余をこれで取る

    s = set()
    result = [x for x in a if x in s or s.add(x)]
    # for x in a:
    # if x in s:
    #     result.append(x)
    # s.add(x) と同じ書き方
    index = [i for i, x in enumerate(a) if x == result[0]]
    l = index[0] + 1
    r = index[1] + 1

    # フェルマーの小定理を用いてコンビネーションを効率よく計算
    factrial = [1] * (n + 2)
    for k in range(1, n + 2):
        factrial[k] = (factrial[k - 1] * k) % M

    fact_inv = [1] * (n + 2)
    fact_inv[n + 1] = pow(factrial[n + 1], M - 2, M)
    for k in range(n, -1, -1):
        fact_inv[k] = (fact_inv[k + 1] * (k + 1)) % M
    # Mについて等式[(n-1)!]^(-1)=(n!)^(-1)*nの剰余を取ると
    # [(n-1)!]^(M-2)%M = [(n!)^(M-2)*n]%M になるからという感じ？ 

    def nCr(n, r, M):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n - r]) % M

    for k in range(1, n + 2):
        print((nCr(n + 1, k, M) - nCr((l - 1) + (n + 1 - r), k - 1, M)) % M)

n = int(input())
l = [int(i) for i in input().split()]
x = [n] + l
D_11(x)

Submission status: Accepted

Solution code:
def D_11(x):
    n = x[0]  # 整数の数
    a = x[1:]  # 数列
    M = 10**9 + 7  # 求めた解の剰余をこれで取る

    s = set()
    result = [x for x in a if x in s or s.add(x)]
    # for x in a:
    # if x in s:
    #     result.append(x)
    # s.add(x) と同じ書き方
    index = [i for i, x in enumerate(a) if x == result[0]]
    l = index[0] + 1
    r = index[1] + 1

    # フェルマーの小定理を用いてコンビネーションを効率よく計算
    factrial = [1] * (n + 2)
    for k in range(1, n + 2):
        factrial[k] = (factrial[k - 1] * k) % M
    fact_inv = [1] * (n + 2)
    fact_inv[n + 1] = pow(factrial[n + 1], M - 2, M)
    for k in range(n, -1, -1):
        fact_inv[k] = (fact_inv[k + 1] * (k + 1)) % M

    def nCr(n, r, M):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n - r]) % M

    for k in range(1, n + 2):
        print((nCr(n + 1, k, M) - nCr((l - 1) + (n + 1 - r), k - 1, M)) % M)

n = int(input())
l = [int(i) for i in input().split()]
x = [n] + l
D_11(x)

Submission status: Accepted

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

s = set()
result = [x for x in a if x in s or s.add(x)]
indices = [i for i, x in enumerate(a) if x == result[0]]

l = indices[0]+1
r = indices[1] +1

fact = [1]
for x in range(1, n+2):
	fact.append( (x * fact[x-1]) % C )
 
factinv = [1] * (n+2)
factinv[n+1] = pow(fact[n+1], C-2, C)
 
for x in range(n, -1, -1):
	factinv[x] = ( factinv[x+1] * (x+1) ) % C
 
def nCr(n,r):
    if n < 0 or r < 0 or n < r:
        return 0
    else:
        return ( fact[n] * factinv[r] * factinv[n-r] ) % C

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

Submission status: Accepted

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

from collections import Counter
import re

def pow(a, x):
        y = 1
        p = a % mask
        n = x
        while (n > 0):
                if ((n % 2) == 0):
                        p = (p * p) % mask
                        n /= 2
                else:   
                        y = (y * p) % mask
                        n -= 1
        return y

n = int(raw_input())
a = map(int, re.split("\s", raw_input()))
left = 0
right = 0

mask = 10**9 + 7
invm = 10**9 + 5

com = [1]*(n+2)
inv = [1]*(n+2)

tmp = 1 
for i in range(1, n+2):
        tmp = (tmp * i) % mask
        com[i] = tmp
        inv[i] = pow(tmp, invm) % mask

counter = Counter(a)
dup = counter.most_common(1)[0][0]
left = a.index(dup)
right = a[left+1:].index(dup) + left + 1

for i in range(1, n + 2):
        ans = (com[n + 1] * (inv[i] * inv[n + 1 - i]))

        if ((left + n - right - i + 1) >= 0):
                ans -= (com[left + n - right] * inv[i - 1] * inv[left + n - right - i + 1])
        print ans % mask

Submission status: Accepted

Solution code:
def power(x, n):
    y = 1
    while n > 0:
        if n % 2 == 0:
            x = (x * x) % (10 ** 9 + 7)
            n = n // 2
        else:
            y = (y * x) % (10 ** 9 + 7)
            n = n - 1
    return y


MOD = 10 ** 9 + 7

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

fact = [1] * (n + 2)
inv = [1] * (n + 3)

for i in range(1, n + 2):
    fact[i] = (i * fact[i - 1]) % MOD
    inv[i] = power(fact[i], MOD - 2) % MOD


def nCm(n, m):
    global fact
    global inv
    return fact[n] * inv[m] % MOD * inv[n - m] % MOD


saw = [-1] * n
left = 0
right = 0
for i in range(n):
    if saw[a[i] - 1] == -1:
        saw[a[i] - 1] = i
    else:
        left, right = saw[a[i] - 1], n - i
        break

for i in range(1, n + 2):
    if i == 1:
        print(n)
    elif left + right >= i - 1:
        print((nCm(n + 1, i) - nCm(left + right, i - 1)) % MOD)
    else:
        print(nCm(n + 1, i))

Submission status: Accepted

Solution code:
INF = 10**9+7 

n = int(input())
a = list(map(int, input().split()))
s = set()
result = [x for x in a if x in s or s.add(x)]
indexes = [i for i, x in enumerate(a) if x == result[0]]
l0 = indexes[0]+1
l1 = indexes[1] +1

def bin_pow(a,n):
    ans = 1
    mag = a
    while(n>0):
        if n%2==0:
            mag = (mag*mag)%INF
            n /= 2
        else:        
            ans = ans* mag%INF
            n -= 1
    return ans

factorial = [0]*(n+2)
inverse_factorial = [0] * (n+2)

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

inverse_factorial[n+1] = bin_pow(factorial[n+1], INF-2)
for i in range(n,-1,-1):
    inverse_factorial[i] = (inverse_factorial[i+1]*(i+1))%INF

def combi(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    return (factorial[n] * inverse_factorial[r] )%INF * (inverse_factorial[n-r]% INF)

for i in range(1,n+2):
    print((combi(n+1,i)-combi(n-(l1-l0), i-1) )%INF)

Submission status: Accepted

Solution code:
n = int(input())
a = tuple(map(int, input().split()))
occur = [0 for i in range(n + 1)]
MOD = 1000000007
for i in range(n + 1):
    if occur[a[i]] > 0: val = n - 1 - i + occur[a[i]]
    else: occur[a[i]] = i + 1
inv = [0 if i > 2 else 1 for i in range(n + 2)]
pinv = [0 if i > 2 else 1 for i in range(n + 2)]
perm = [0 if i > 2 else 1 for i in range(n + 2)]
for i in range(2, n + 2):
    inv[i] = -int(MOD / i) * inv[MOD % i] + MOD
    pinv[i] = pinv[i - 1] * inv[i] % MOD
    perm[i] = perm[i - 1] * i % MOD
def C(n, m):
    return (perm[m] * pinv[n] % MOD) * pinv[m - n] % MOD if n <= m else 0
for i in range(1, n + 2):
    temp = C(i, n + 1) - C(i - 1, val)
    if temp < 0: temp += MOD
    print(temp)