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:
from collections import Counter

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

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

def comb(n,k):
    return factorial[n]*pow(factorial[n-k]*factorial[k], -1, mod)

mc = Counter(a).most_common()[0][0]

indices=[]
for i in range(n+1):
  if a[i]==mc:indices.append(i)
    
m = [indices[0]+1,n+1-indices[1]]
m = sorted(m)
    
for i in range(1,n+2):
  if i == 1:
    print(n)
    continue
  if i == n+1:
    print(1)
    continue
  if i <= m[0]+m[1]-1:
    print((comb(n+1,i) - comb(m[0]+m[1]-2,i-1)) % mod)
  else:
    print(comb(n+1,i) % mod)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(10**5 + 5)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    pre_idx = 0
    idx = 0
    appeared = [-1] * (N + 1)
    for i, a in enumerate(A):
        if appeared[a] == -1:
            appeared[a] = i
        else:
            pre_idx, idx = appeared[a], i
            break

    """
    dpする前に計算量を見積もる癖はつけた方が良さそう。
    TLEした後に引き返せる時間が残っていない。。。

    問題が「同じ表現を含まない」のネガティブなので、全体から
    表現が被るケースを除くべきでした。
    同じ表現になるのは、２回出てくる数をaとして、aが２回出てくるまでの範囲を見た時に
    aを一回選びかつ2つのaの間の数を全く選ばない時。
    """

    for k in range(1, N + 2):
        if k == 1:
            print(N)
            continue
        rem = (N + 1) - (idx - pre_idx + 1)
        if rem < k - 1:
            print(comb(N + 1, k))
        else:
            print((comb(N + 1, k) - comb(rem, k - 1)) % mod)





if __name__ == "__main__":
    main()

Submission status: Accepted

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

n = int(input())
mod = pow(10, 9)+7
ct = [1]*(n+1)
for i in range(1, n+1):
  ct[i] = ct[i-1]*i%mod

def comb(n, k):
  res = ct[n]*pow(ct[n-k], mod-2, mod)%mod*pow(ct[k], mod-2, mod)%mod
  return res

def main():
  a = [int(x) for x in input().split()]

  already = [-1]*n
  for i in range(n+1):
    if already[a[i]-1] != -1:
      f, s = already[a[i]-1], n-i
      break
    already[a[i]-1] = i
    
  ans = [0]*(n+1)
  c = 1
  for i in range(n+1):
    c = c*(n+1-i)%mod*pow(i+1, mod-2, mod)%mod
    ans[i] += c%mod

  for i in range(n):
    if s+f >= i:
      ans[i] += mod-(comb(f+s, i))%mod
    ans[i] %= mod
  for a in ans:
    print(a)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
### 素数の逆元とCombination

M = 10**9+7 # 出力の制限
N = n+10 # 必要なテーブルサイズ

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

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

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

from collections import Counter
c = Counter(a)
t = []
for i,num in enumerate(a):
    if c[num]==2:
        t.append(i)
i0, i1 = t
n0 = i0
n1 = i1-i0-1
n2 = n - i1
ans = [None]*(n+1)
for k in range(1, n+2):
    if k==1:
        val = n
    else:
        val = cmb(n-1, k, M) + cmb(n-1, k-2, M) + (cmb(n-1, k-1, M) - cmb(n0+n2, k-1, M))*2 + cmb(n0+n2, k-1, M)
        val%= M
    ans[k-1] = val
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
MOD=10**9+7
from collections import Counter

def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;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

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

N=int(input())
fac,finv,inv=facinv(N+1)
A=list(map(int,input().split()))
m=Counter(A).most_common()[0][0]
L,R=sorted([i for i in range(N+1) if A[i]==m])
R=N-R
for k in range(1,N+2):
    print((COM(N+1,k)-COM(L+R,k-1)+MOD)%MOD)

Submission status: Accepted

Solution code:
n = int(input())
arr  = list(map(int , input().split()))
cnt =[-1]*(n+1)
mod = 10**9+7
fact=[1]
now =1
for i in range(1, n+2):
	now =(now%mod)*(i%mod)
	now = now%mod
	fact.append(now)
inverse = []
for i in range(n+2):
	inverse.append(pow(fact[i] , mod-2, mod))
l  , r, =0 , 0
for i in range(0, n+1):
	if cnt[arr[i]]!=-1:
		l = cnt[arr[i]]
		r= i
		break
	cnt[arr[i]]=i

for i in range(1, n+2):
	ans = (fact[n+1]*inverse[i]*inverse[n+1-i])%mod
	rem = n-r+l
	# subtract all the combination which are duplicates the subsequence will either from the
	# left elements of first duplicate or right elements of last duplicates
	# we need to subtract those
	if rem>=i-1:
		ans = ans-(fact[rem]*inverse[i-1]*inverse[rem-(i-1)])%mod+mod
		ans = ans%mod
	print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr  = list(map(int , input().split()))
cnt =[-1]*(n+1)
mod = 10**9+7
fact=[1]
now =1
for i in range(1, n+2):
	now =(now%mod)*(i%mod)
	now = now%mod
	fact.append(now)
inverse = []
for i in range(n+2):
	inverse.append(pow(fact[i] , mod-2, mod))
l  , r, =0 , 0
for i in range(0, n+1):
	if cnt[arr[i]]!=-1:
		l = cnt[arr[i]]
		r= i
		break
	cnt[arr[i]]=i

for i in range(1, n+2):
	ans = (fact[n+1]*inverse[i]*inverse[n+1-i])%mod
	rem = n-r+l
	if rem>=i-1:
		ans = ans-(fact[rem]*inverse[i-1]*inverse[rem-(i-1)])%mod+mod
		ans = ans%mod
	print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
s = set()
for i in range(N+1):
    a = As[i]
    if a in s:
        r = N-i
        l = As.index(a)
        break
    s.add(a)
mod = 10**9+7
rest = l+r

pos = {}
neg = {}
pos[0] = 1
neg[0] = 1
c = 1
for i in range(1, 10**5+5):
    c *= i
    c %= mod
    pos[i] = c
    neg[i] = pow(c, mod-2, mod)

for i in range(1, N+2):
    All = pos[N+1]*neg[i]*neg[N+1-i]%mod
    if rest-i+1>=0:
        kaburi = pos[rest]*neg[i-1]*neg[rest-i+1]%mod
    else:
        kaburi = 0
    print((All-kaburi)%mod)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
from collections import Counter
ctr = Counter(A)
dup = ctr.most_common()[0][0]
i = A.index(dup)
j = A[::-1].index(dup)
l = i+j

MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+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 comb(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 k in range(1,N+2):
    ans.append(comb(N+1,k))
for k in range(l+1):
    ans[k] -= comb(l,k)
    ans[k] %= MOD
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[-1]*(n+1)
MOD=10**9+7
factorials=[1]
current=1
for i in range(1,n+2):
  current=(current*i)%MOD
  factorials.append(current)
inverses=[]
for i in range(n+2):
  inverses.append(pow(factorials[i],MOD-2,MOD))
for i in range(n+1):
  if b[a[i]]!=-1:
    l=b[a[i]]
    r=i
    break
  b[a[i]]=i
for i in range(1,n+2):
  ans=(factorials[n+1]*inverses[i]*inverses[n+1-i])%MOD
  
  rem=n-r+l
  if  rem>=i-1:
    ans=(ans-factorials[rem]*inverses[i-1]*inverses[rem-(i-1)])%MOD
  print(ans)

Submission status: Accepted

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


duplicate_x = None
checked = set()
for a in A:
    if a in checked:
        duplicate_x = a
    checked.add(a)


x_l_index = A.index(duplicate_x)
x_r_index = N + 1 - A[::-1].index(duplicate_x) - 1


# 逆元の前計算
factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, N + 2):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


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


for k in range(1, N + 1 + 1):
    print((nCr(N + 1, k) - nCr(max(0, x_l_index) + max(N + 1 - x_r_index - 1, 0), k - 1)) % MOD)

Submission status: Accepted

Solution code:
import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i % p
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    for i in range(n):
        ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
        ans1[i+1]=ans0[i]*2
        ans2[i+2]=ans0[i]
    sn=pk[0]+n-pk[1]
    for i in range(sn+1):
        ans1[i+1]-=fact[sn]*ifact[sn-i]*ifact[i] % p
    for i in range(1,n+2):
        print((ans0[i]+ans1[i]+ans2[i]) % p)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
D = {i: [0] for i in range(1, n+1)}
for i in range(n+1):
  D[a[i]][0] += 1
  D[a[i]].append(i)
pl, pr = 0, 0
for i in D:
  if D[i][0] == 2:
    pl = D[i][1]
    pr = D[i][2]
    break
L = pl
M = pr - pl - 1
N = n - pr
mod = int(1e9) + 7 # <-- input modulo
maxf = n+11          # <-- input factional limitation

def make_fact(n, k):
    tmp = n
    perm = [i for i in range(k)]
    L = [0 for _ in range(k)]
    for i in range(k):
        L[i] = tmp % (i + 1)
        tmp //= i + 1
    LL = [0 for _ in range(k)]
    for i in range(k):
        LL[i] = perm[L[-i-1]]
        for j in range(L[-i-1]+1, k):
            perm[j-1] = perm[j]
    return LL

def doubling(n, m, modulo=mod):
    y = 1
    base = n
    tmp = m
    while tmp != 0:
        if tmp % 2 == 1:
            y *= base
            if modulo > 0:
                y %= modulo
        base *= base
        if modulo > 0:
            base %= modulo
        tmp //= 2
    return y

def inved(a, modulo=mod):
    x, y, u, v, k, l = 1, 0, 0, 1, a, modulo
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return x % modulo

fact = [1 for _ in range(maxf+1)]
invf = [1 for _ in range(maxf+1)]

for i in range(maxf):
    fact[i+1] = (fact[i] * (i+1)) % mod
invf[-1] = inved(fact[-1])
for i in range(maxf, 0, -1):
    invf[i-1] = (invf[i] * i) % mod

for i in range(1, n+2):
  S = fact[n+1]*invf[i]*invf[n-i+1]%mod
  if i <= n-M:
    S -= fact[n-1-M]*invf[i-1]*invf[n-M-i]%mod
    S %= mod
  print(S)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
D = {i: [0] for i in range(1, n+1)}
for i in range(n+1):
  D[a[i]][0] += 1
  D[a[i]].append(i)
pl, pr = 0, 0
for i in D:
  if D[i][0] == 2:
    pl = D[i][1]
    pr = D[i][2]
    break
L = pl
M = pr - pl - 1
N = n - pr
mod = int(1e9) + 7 # <-- input modulo
maxf = n+11          # <-- input factional limitation

def make_fact(n, k):
    tmp = n
    perm = [i for i in range(k)]
    L = [0 for _ in range(k)]
    for i in range(k):
        L[i] = tmp % (i + 1)
        tmp //= i + 1
    LL = [0 for _ in range(k)]
    for i in range(k):
        LL[i] = perm[L[-i-1]]
        for j in range(L[-i-1]+1, k):
            perm[j-1] = perm[j]
    return LL

def doubling(n, m, modulo=mod):
    y = 1
    base = n
    tmp = m
    while tmp != 0:
        if tmp % 2 == 1:
            y *= base
            if modulo > 0:
                y %= modulo
        base *= base
        if modulo > 0:
            base %= modulo
        tmp //= 2
    return y

def inved(a, modulo=mod):
    x, y, u, v, k, l = 1, 0, 0, 1, a, modulo
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return x % modulo

fact = [1 for _ in range(maxf+1)]
invf = [1 for _ in range(maxf+1)]

for i in range(maxf):
    fact[i+1] = (fact[i] * (i+1)) % mod
invf[-1] = inved(fact[-1])
for i in range(maxf, 0, -1):
    invf[i-1] = (invf[i] * i) % mod

for i in range(1, n+2):
  S = fact[n]*invf[i-1]*invf[n-i+1]%mod
  if i <= n-1:
    S += fact[n-1]*invf[i]*invf[n-1-i]%mod
    S %= mod
  if i <= n-M:
    S -= fact[n-1-M]*invf[i-1]*invf[n-M-i]%mod
    S %= mod
  if i <= n:
    S += fact[n-1]*invf[i-1]*invf[n-i]%mod
    S %= mod
  print(S)

Submission status: Accepted

Solution code:
"""
被りなし
cmb(n-2,k)
被りあり2子使うなら
  x,x,x, A, y,y,y,y, A, z,z,z
cmb(n-2,k-2)
被りあり、１つだけ使うなら。。。
  cmb(n-2,k-1) * 2 # y使うかもしれないけーす
  cmb(count(x) + count(z), k-1) # y使わないケース（２倍カウントしてる）
"""
N = int(input())
A = list(map(int, input().split()))
dup = sum(A) - N*(N+1)//2
idx = []
for i in range(len(A)):
  if A[i] == dup:
    idx.append(i)
    
countXZ = N - idx[1] + idx[0]
### nCr mod
# https://qiita.com/derodero24/items/91b6468e66923a87f39f
mod = 10**9+7 #出力の制限
NMAX = 10**5+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

# solve
print(N) # k=1
for k in range(2,N+1):
  wk = cmb(N-1,k)
  wk += cmb(N-1,k-2)
  wk += cmb(N-1,k-1) * 2
  wk -= cmb(countXZ, k-1)
  #print(cmb(N-1,k), cmb(N-1,k-2), cmb(N-1,k-1) * 2, cmb(countXZ, k-1))
  print(wk % mod)
print(1) # k=N+1

Submission status: Accepted

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

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

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

t = sum(a)-n*(n+1)//2
m = a.index(t) + a[::-1].index(t)
for k in range(1, n+2):
    print((comb(n+1, k)-comb(m, k-1))%mod)

Submission status: Accepted

Solution code:
L=10**5+3
MOD=10**9+7
fac=[1]*(L+1)
for i in range(1,L+1):
  fac[i]=fac[i-1]*i%MOD
inv_fac=[1]*(L+1)
inv_fac[L]=pow(fac[L],MOD-2,MOD)
for i in range(L-1,0,-1):
  inv_fac[i]=inv_fac[i+1]*(i+1)%MOD

def cmb(n,r):
  if n<0 or r<0 or r>n:
    return 0
  return fac[n]*inv_fac[r]%MOD*inv_fac[n-r]%MOD

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

used=[0]*N
for i in range(N+1):
  a=A[i]
  if used[a-1]==0:
    used[a-1]=[1,i]
  else:
    x=a
    y=used[a-1][1]
    z=i
    break

print(N)
for i in range(2,N+2):
  ans=cmb(N+1,i)-cmb(N-z+y,i-1)
  print(ans%MOD)

Submission status: Accepted

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

"""
どこかに同じ数値が出てくる。
AAAxBBBxCCC
xが同一文字とする
・xがどちらか1つ登場
・Bを使用しない
ものについてはどちらのxを使用しても同じ数列になるので除く
"""
modp = mod
max_n = 2*10 ** 5               # 必要分だけ用意する
fact = [1, 1] + [0]*max_n     # fact[n] = (n! mod modp)
factinv = [1, 1] + [0]*max_n  # factinv[n] = ((n!)^(-1) mod modp)
inv = [0, 1] + [0]*max_n      # factinv 計算用

def cmb(n, r, p):
    assert n < p, 'n is less than modp'
    assert n < max_n, 'n in less than max_n'
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

for i in range(2, max_n + 1):
    fact[i] = (fact[i-1] * i) % modp
    inv[i] = (-inv[modp % i] * (modp // i)) % modp
    factinv[i] = (factinv[i-1] * inv[i]) % modp

counter = [0] * n
for i in range(n+1):
    counter[a[i]-1]+=1
    if counter[a[i]-1] == 2:
        second = i
        first = a.index(a[i])
        break

# xの重複を考慮せず全てカウント
ans = [cmb(n+1, i, mod) for i in range(1, n+2)]

n_left = first
n_right = n-second
n_lr = n_left + n_right

# i個の重複する組合せはn_lrからi-1個選び、xをどちらか1つ選ぶ。
doubled = [1]+[cmb(n_lr, i, mod) for i in range(1, n_lr+1)]

for i in range(n_lr+1):
    ans[i] = (ans[i] - doubled[i])%mod

for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
N=10**5+3
mod=10**9+7
fac=[1]*(N+1)
for i in range(1,N+1):
    fac[i]=fac[i-1]*i%mod
inv_fac=[1]*(N+1)
inv_fac[N]=pow(fac[N],mod-2,mod)
for i in range(N-1,0,-1):
    inv_fac[i]=inv_fac[i+1]*(i+1)%mod
def nCr(n,r):
    if n<0 or r<0 or r>n:
        return 0
    return fac[n]*inv_fac[r]%mod*inv_fac[n-r]%mod
n=int(input())
A=list(map(int,input().split()))
used=[0]*n
for i in range(n+1):
    a=A[i]
    if used[a-1]==0:
        used[a-1]=[1,i]
    else:
        x=a
        y=used[a-1][1]
        z=i
        break
print(n)
for i in range(2,n+2):
    ans=nCr(n+1,i)-nCr(n-z+y,i-1)
    print(ans%mod)

Submission status: Accepted

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

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

# まず重複する数字を探す
start = -1
end = -1
checker = {}
for i in range(len(A)):
  if A[i] not in checker:
    checker[A[i]] = i
  else:
    end = i
    start = checker[A[i]]
    break
    
# 1 2 3 4 3 5 6
# について、全組み合わせから、1 2 [3 4 3] 5 6のように同じ数で囲まれた部分を一個と見做した
# 区間での組み合わせを引く
L = (N + 1) - (end - start)  # 短くした区間の長さ
    
DIV = 10 ** 9 + 7
n = (10 ** 6) * 2 # PyPyじゃないと通らない。 * 5が限界くらい
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

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

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

for k in range(1, N + 2):
  if k == 1:
    print(N)
  elif L - 1 >= k - 1:
    print((nCr(N + 1, k, DIV) - nCr(L - 1, k - 1, DIV)) % DIV)
  else:
    print(nCr(N + 1, k, DIV))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
from collections import defaultdict
d = {}
for i,a in enumerate(A):
    if a not in d:
        d[a] = i
    else:
        l = d[a]
        r = i
        break
mod = 10**9+7
n = 100010
frac = [1]*(n+1)
finv = [1]*(n+1)
for i in range(n):
    frac[i+1] = (i+1)*frac[i]%mod
finv[-1] = pow(frac[-1],mod-2,mod)
for i in range(1,n+1):
    finv[n-i] = finv[n-i+1]*(n-i+1)%mod
def nCr(n,r):
    if n<0 or r<0 or n<r: return 0
    r = min(r,n-r)
    return frac[n]*finv[n-r]*finv[r]%mod
ans = 0
for i in range(1,N+2):
    ans = nCr(N+1,i)-nCr(N+l-r,i-1)
    ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
def memfact(a,m):
    temp = 1
    yield temp
    for i in range(1,a+1):
        temp = temp * i % m
        yield temp
def comb(n,r,m):
    if r == 0: return 1
    return (memf[n]*pow(memf[r],m-2,m)*pow(memf[n-r],m-2,m)) % m


n,*a = map(int, open(0).read().split())
m = 1000000007
checker = set()
for i in range(n+1):
    if a[i] in checker:
        left = a.index(a[i])
        right = n - i
        break
    else:
        checker.add(a[i])
memf = []
mfappend = memf.append
for x in memfact(n+1,m):
    mfappend(x)
lr = left + right
for i in range(1,n+2):
    ans = comb(n+1,i,m)
    if i <= lr + 1:
        ans = (ans-comb(lr,i-1,m)) % m
    print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

lim = 10 ** 5 + 2
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, lim + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    # 累計
    factinv.append((factinv[-1] * inv[-1]) % mod)

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

N = getN()
A = getList()

lista = [0] * (max(A) + 1)
double = 0
dou_ind_2 = 0
for i in range(N + 1):
    if lista[A[i]] > 0:
        double = A[i]
        dou_ind_2 = i
        break
    lista[A[i]] += 1

dou_ind_1 = 0
for i in range(N + 1):
    if A[i] == double:
        dou_ind_1 = i
        break

outer = dou_ind_1 + (N - dou_ind_2)

for i in range(1, N + 2):
    if i == 1:
        print(N)
        continue
    print((cmb(N + 1, i) - cmb(outer, i - 1)) % mod)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
idx = [-1]*(n+1)
# 2回現れた文字のidxをl,rに持つ
for i, a in enumerate(A, 1):
    if idx[a] == -1:
        idx[a] = i
    else:
        r = i
        l = idx[a]


MAX_N = 10**6+5
MOD = 10**9 + 7
fac = [0]*(MAX_N)
fac[0] = 1
for i in range(1, MAX_N):
    fac[i] = i*fac[i-1] % MOD
fac_inv = [0]*MAX_N
fac_inv[-1] = pow(fac[-1], MOD-2, MOD)
for i in range(MAX_N-2, -1, -1):
    fac_inv[i] = fac_inv[i+1]*(i+1) % MOD


def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fac[n]*fac_inv[k]*fac_inv[n-k] % MOD


# print(comb(0, 0))
# print(l, r)
# print(fac[:5])
# print(fac_inv[:5])
for k in range(1, n+2):
    #    print(comb(n+1, k), comb(l-1+n-r, k-1))
    ans = (comb(n+1, k)-comb(l-1+n+1-r, k-1)) % MOD
    print(ans)

Submission status: Accepted

Solution code:
def comb(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)


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

appeared = set()
dup_right = 0
dup = 0
for i, x in enumerate(a):
    if x in appeared:
        dup_right = n - i
        dup = x
        break
    appeared.add(x)
dup_left = 0
for i, x in enumerate(a):
    if x == dup:
        dup_left = i
        break

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

Submission status: Accepted

Solution code:
def comb(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)


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

appeared = set()
dup_right = 0
dup = 0
for i, x in enumerate(a):
    if x in appeared:
        dup_right = n - i
        dup = x
        break
    appeared.add(x)
dup_left = 0
for i, x in enumerate(a):
    if x == dup:
        dup_left = i
        break

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))

    appeared = set()
    dup = 0

    for x in a:
        if x in appeared:
            dup = x
            break
        else:
            appeared.add(x)

    first = a.index(dup)
    second = a[first + 1:].index(dup) + first + 1

    print(n)

    p = first
    q = (n + 1) - second - 1

    c1 = n + 1
    c2 = 1

    for i in range(2, n + 2):
        c1 *= (n + 1 - (i - 1))
        c1 %= MOD
        c1 *= pow(i, MOD - 2, MOD)
        c1 %= MOD
        c2 *= (p + q - (i - 2))
        c2 %= MOD
        c2 *= pow(i - 1, MOD - 2, MOD)
        c2 %= MOD
        print((c1 - c2) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
memo={}

for i in range(n+1):
    if l[i]in memo:
        g=l[i]
        x,y=memo[g],i
        break
    memo[l[i]]=i
mod=10**9+7

fact=[1]*(n+1+1)
inv=[1]*(n+1+1)
for i in range(2,n+1+1):
    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(1,n+2):print((comb(n+1,i)-comb(x+n-y,i-1))%mod)

Submission status: Accepted

Solution code:
n = int(input())
last = [-1]*n
mod = 10**9 + 7
l = 10**6
fac = [1]*l
facr = [1]*l

for i in range(l-1):
    fac[i+1] = fac[i]*(i+1)%mod
facr[l-1] = pow(fac[l-1],mod - 2,mod)
for i in range(1,l)[::-1]:
    facr[i-1] = facr[i]*i%mod

def combi(N,K):
    if N < K:
        return 0
    return fac[N]*facr[N-K]%mod*facr[K]%mod



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

for i,a in enumerate(A):
    if last[a-1] == -1: last[a-1] = i
    else:
        dup = [last[a-1],i]
        m = last[a-1] + n - i
        break

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

ans = [0]*(n+1)
for i in range(n+1):
    ans[i] = (combi(n+1,i+1) - combi(m,i))%mod
print("\n".join(str(i) for i in ans))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict


def initialize_cmb(m, mod=10 ** 9 + 7):
    fac = [1]
    finv = [1]
    inv = [0] * (m + 1)
    if m >= 1:
        fac.append(1)
        finv.append(1)
        inv[1] = 1
        pre_fac = 1
        pre_finv = 1
        for i in range(2, m + 1):
            pre_fac = pre_fac * i % mod
            fac.append(pre_fac)
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            pre_finv = pre_finv * inv[i] % mod
            finv.append(pre_finv)
    return fac, finv


def cmb(n, k, fac, finv, mod=10 ** 9 + 7):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))

    arr = [-1] * n

    i1 = i2 = 0

    for i in range(n + 1):
        if arr[a[i] - 1] == -1:
            arr[a[i] - 1] = i
        else:
            i1 = arr[a[i] - 1]
            i2 = i
            break

    fac, finv = initialize_cmb(n + 1, mod)

    for k in range(1, n + 2):
        ans = cmb(n + 1, k, fac, finv, mod)
        if k - 1 <= n - i2 + i1:
            ans -= cmb(n - i2 + i1, k - 1, fac, finv, mod)
        print(ans % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
n = int(input())
alst = list(map(int, input().split()))
num_pos = [-1 for _ in range(n)]

MOD = 10 ** 9 + 7
N = n + 10

fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD

for i, num in enumerate(alst):
    if num_pos[num - 1] == -1:
        num_pos[num - 1] = i
    else:
        bef = num_pos[num - 1]
        aft = n - i
for i in range(1, n + 2):
    ans = nCk(n + 1, i) - nCk(bef + aft, i - 1)
    ans %= MOD
    print(ans)