Problem:


Score : 600 points

Problem Statement

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

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

Notes

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

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

Constraints

1 \leq n \leq 10^5

1 \leq a_i \leq n

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

n and a_i are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
1 2 1 3

Sample Output 1

3
5
4
1

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

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

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

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

Sample Input 2

1
1 1

Sample Output 2

1
1

There is one subsequence with length 1: 1.

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

Sample Input 3

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

Sample Output 3

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

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



Sample input:
3
1 2 1 3


Sample output:
3
5
4
1

Submission status: Accepted

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

dup=[0]*n
for num in a:
    dup[num-1]+=1
    if dup[num-1]>1:
        break

A=-1
B=-1
for i in range(len(a)):
    if a[i]==num:
        if A==-1:
            A=i
        else:
            B=i
B=n-B

def find_power(n,mod=10**9+7):
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
  
def find_inv_power(n,mod=10**9+7):
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

mod = 10**9+7
NUM = (10**5)+100
p_lis=find_power(NUM,mod)
ip_lis=find_inv_power(NUM,mod)

def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (p_lis[n]*ip_lis[r]*ip_lis[n-r])%(mod)

print(n)
for k in range(2,n+2):
    base=comb(n+1,k) - comb(A+B,k-1)

    print(base%mod)

Submission status: Accepted

Solution code:
from collections import Counter

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

MAX = 10 ** 5 + 10

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


c = Counter(a)
for key, val in c.items():
    if val == 2:
        break

idx = []
for i, e in enumerate(a):
    if e == key:
        idx.append(i)

l = idx[0]
r = n - idx[1]
for k in range(1, n + 2):
    ans = comb(n + 1, k) - comb(l + r, k - 1)
    ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
c=[0]*n
for i in a:c[i-1]+=1
ind=c.index(2)
x=[]
for i in range(n+1):
    if a[i]==ind+1:x.append(i)
m=n+x[0]-x[1]
ans=1
anss=1
for k in range(1,n+2):
    ans=(ans*(n-k+2))%mod
    ans=ans*pow(k,mod-2,mod)%mod
    if k==1:print(n);continue
    anss=(anss*(m-k+2))%mod
    anss=anss*pow(k-1,mod-2,mod)%mod
    if k-1>m:print(ans);continue
    print((ans-anss)%mod)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
c=[0]*n
for i in a:c[i-1]+=1
ind=c.index(2)
x=[]
for i in range(n+1):
    if a[i]==ind+1:x.append(i)
m=n+x[0]-x[1]
f=[1]
for i in range(1,n+2):f.append(f[-1]*i%mod)
def comb(n,r):return f[n]*pow(f[r],mod-2,mod)*pow(f[n-r],mod-2,mod)%mod
for k in range(1,n+2):
    if k==1:print(n);continue
    if k-1>m:print(comb(n+1,k));continue
    ans=comb(n+1,k)-comb(m,k-1)
    print(ans%mod)

Submission status: Accepted

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

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

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

from collections import defaultdict
dic = defaultdict(int)

for idx, a in enumerate(al):
    if dic[a] == 1:
        e = idx
        v = a
    dic[a] += 1

for idx, a in enumerate(al):
    if a == v:
        s = idx
        break


for i in range(1, n+2):
    ans = comb(n+1, i)
    if s + n - e >= i - 1:
        ans -= comb(s+(n-e), i-1)
    ans %= MOD
    print(ans)

Submission status: Accepted

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

d = {}
for i in range(n+1):
    if A[i] not in d:
        d[A[i]] = i
    else:
        l = d[A[i]]
        r = i
        break
#print(l, r)

def cmb1(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 )

for k in range(1, n+2):
    ans = cmb1(n+1, k, mod) - cmb1(l+n-r, k-1, mod)
    print(ans%mod)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

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

cntA = Counter(A)
I = [a for a, c in cntA.items() if c == 2][0]
L, R = [i for i, a in enumerate(A) if a == I]
S = L + (N - R)

for i in range(1, N + 2):
    if i == 1:
        print(N)
        continue

    ans = comb.ncr(N + 1, i) - comb.ncr(S, i - 1)
    print(ans % 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)
d = ctr.most_common(1)[0][0]
x = A.index(d)
y = x+1 + A[x+1:].index(d)
f = x + N-y

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 i in range(1,N+2):
    ans.append((comb(N+1,i) - comb(f,i-1)) % MOD)
print(*ans, sep='\n')

Submission status: Accepted

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


class Combination:
    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    comb = Combination(N + 10)
    X = Counter(A).most_common()[0][0]

    l = A.index(X)
    r = A.index(X, l+1)
    LR = l + (N - r)

    for i in range(1, N + 2):
        ans = comb(N + 1, i)
        ans -= comb(LR, i - 1)
        ans = (ans + mod) % mod

        print(ans)

Submission status: Accepted

Solution code:
import sys
mod = 7 + 10 ** 9

def comb(n, r, fact, revfact, mod):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    Ad = dict()
    double = []
    for i, a in enumerate(A):
        if a in Ad:
            Ad[a].append(i)
            double = Ad[a]
        else: Ad[a] = [i]

    fact = [1] * (N + 2)
    for i in range(1, N + 2): fact[i] = (fact[i - 1] * i) % mod
    revfact = [1] * (N + 2)
    revfact[N + 1] = pow(fact[N + 1], mod - 2, mod)
    for i in reversed(range(1, N + 1)):revfact[i] = ((i + 1) * revfact[i + 1]) % mod
    mayOverCount = double[0] + N - double[1]
    
    for k in range(N + 1):
        total = comb(N + 1, k + 1, fact, revfact, mod)
        if k <= mayOverCount: 
            total += mod - comb(mayOverCount, k, fact, revfact, mod)
            total %= mod
        print(total)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
p = 10**9+7

n = int(input())
a = list( map(int, input().split()))
count = [0]*n

for i in range(n+1):
    count[a[i]-1] += 1
    if count[a[i]-1] == 2:
        right = i
        left = a.index(a[i])
        break

def nCr_mod_p(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
N = 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p), 0! = 1! = 1
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p), 0! = 1! = 1
inv = [0, 1]  # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる

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)

for i in range(1,n+2):
    ans = nCr_mod_p(n+1,i,p) - nCr_mod_p(n-right+left,i-1,p)
    print(ans%p)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
MOD_t_MAX = 10**5+10

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    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():
    n = int(input())
    a = list(map(int, input().split()))
    p = [-1]*(n+1)
    l, r = -1, -1
    for i, v in enumerate(a):
        if p[v] == -1:
            p[v] = i
        else:
            l = p[v]
            r = i
            break
    MOD_COM_init()
    for i in range(1, n+2):
        if i == 1:
            print(n)
        else:
            tmp = MOD_COM(n+1, i)
            tmp -= MOD_COM(l+(n+1-r-1), i-1)
            while tmp < 0:
                tmp += MOD
            print(tmp)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**5+10
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 )

ma=0
dic={}
for i in range(m):
    if not a[i] in dic:
        dic[a[i]]=i
    else:
        ma=i-dic[a[i]]-1

for k in range(1,m+1):
    if k==1:
        print(n)
        continue
    tmp=cmb(m,k)

    tmp-=cmb(m-2-ma,k-1)
    print(tmp%mod)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**5+10
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 )

ma=0
dic={}
for i in range(m):
    if not a[i] in dic:
        dic[a[i]]=i
    else:
        ma=i-dic[a[i]]-1

for k in range(1,m+1):
    if k==1:
        print(n)
        continue
    tmp=cmb(m,k)
    if m-2-ma>=k-1:
        tmp-=cmb(m-2-ma,k-1)
    print(tmp%mod)

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

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ct=[0]*n
X=[]
for i in range(n+1):
  ct[a[i]-1]+=1
for i in range(n):
  if ct[i]==2:
    x=i+1
    break
for i in range(n+1):
  if a[i]==x:
    X.append(i)

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(X[0]+n-X[1],i-1,mod)+mod)%mod)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

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

    return modFacts, invs


N = int(input())
place = [0] * N
A = list(map(int, input().split()))
for i, s in enumerate(A):
    if place[s - 1] == 0:
        place[s - 1] = i + 1
    else:
        a = place[s - 1]
        b = i + 1
        break

modFacts, invs = prepare(N + 1)
cnt = pow(2, N + 1, MOD) - 1
cnt -= pow(2, a - 1, MOD) * pow(2, N + 1 - b, MOD)

la = a - 1
rb = N + 1 - b
t = la + rb
for k in range(1, N + 2):
    cnt = (modFacts[N + 1] * invs[k] * invs[N + 1 - k]) % MOD
    if t >= k - 1:
        cnt -= (modFacts[t] * invs[k - 1] * invs[t - (k - 1)])
    print(cnt % 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
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
n=int(input())
mod=10**9+7
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 )
import copy
a=list(map(int,input().split()))
b=copy.deepcopy(a)
b.sort()
tmp=-1
for i in range(n):
  if b[i]==b[i+1]:
    tmp=b[i]
r=[]
for i in range(n+1):
  if a[i]==tmp:
    r.append(i)
y=abs(r[1]-r[0]-1)
for k in range(1,n+2):
  ans=(comb(n-1,k,mod)+comb(n-1,k-2,mod)+comb(n-1,k-1,mod)*2-comb(n-1-y,k-1,mod))%mod
  print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline

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

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

def combination(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[k] * fact_inv[n-k] % mod

x = Counter(a).most_common(1)[0][0]
front = a.index(x)
back = a[::-1].index(x)

for k in range(1, n+2):
    ans = (combination(n+1, k) - combination(front + back, k-1)) % mod
    print(ans)

Submission status: Accepted

Solution code:
import copy

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 = 2*10**5
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()))

B=copy.copy(A)
B.sort()
x=0
for i in range(0,N):
    if B[i]==B[i+1]:
        x=B[i]
        break

first=-1
second=-1
for i in range(0,N+1):
    if A[i]==x:
        if first==-1:
            first=i
        else:
            second=i

for k in range(1,N+2):
    if N-1>=k:
        if first+N-second>=k-1:
            ans=2*cmb(N-1,k-1,mod)-cmb(first+N-second,k-1,mod)+cmb(N-1,k,mod)+cmb(N-1,k-2,mod)
            print(ans%mod)
        else:
            ans=2*cmb(N-1,k-1,mod)+cmb(N-1,k,mod)+cmb(N-1,k-2,mod)
            print(ans%mod)
    elif N==k:
        if first+N-second>=k-1:
            ans=2*cmb(N-1,k-1,mod)-cmb(first+N-second,k-1,mod)+cmb(N-1,k-2,mod)
            print(ans%mod)
        else:
            ans=2*cmb(N-1,k-1,mod)+cmb(N-1,k-2,mod)
            print(ans%mod)
    else:
        if first+N-second>=k-1:
            ans=-cmb(first+N-second,k-1,mod)+cmb(N-1,k-2,mod)
            print(ans%mod)
        else:
            ans=cmb(N-1,k-2,mod)
            print(ans%mod)

Submission status: Accepted

Solution code:
class COM:
    def __init__(self, n: int, mod: int):
        self.n = n
        self.mod = mod
        self.fact = [0] * (n + 1)
        self.factinv = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        
        self.fact[0] = self.fact[1] = 1
        self.factinv[0] = self.factinv[1] = 1
        self.inv[1] = 1
        for i in range(2, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % mod
            self.inv[i] = (-self.inv[mod % i] * (mod // i)) % mod
            self.factinv[i] = (self.factinv[i - 1] * self.inv[i]) % mod
    
    def get_cmb(self, n: int, k: int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] % self.mod * self.factinv[n - k] % self.mod


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    
    pos = dict()
    l, r = -1, -1
    for i in range(n + 1):
        if a[i] in pos:
            l, r = pos[a[i]], i
            break
        pos[a[i]] = i
    
    com = COM(10 ** 5 + 1, MOD)
    print(n)
    for i in range(2, n + 1):
        ans = com.get_cmb(n + 1, i) - com.get_cmb(l + n - r, i - 1)
        print(ans % MOD)
    print(1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[None]*(n+1)
for i in range(n+1):
    if l[a[i]]==None:
        l[a[i]]=i
    else:
        p=l[a[i]]+n-i
        break
pr=10**9+7
print(n)
MAX_NUM = 10**5 + 2
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
for i in range(2,n+1):
    t=c(n+1,i)
    if p>=i-1:
        t-=c(p,i-1)
    print(t%pr)
print(1)

Submission status: Accepted

Solution code:
#abc066d
mod=10**9+7
fact=[1]*(10**5+2)
for n in range(1,10**5+2):
 fact[n]=n*fact[n-1]%mod

def com(n,k,m):
 return fact[n]*pow(fact[k],m-2,m)*pow(fact[n-k],m-2,m)%m

N=int(raw_input())
A=map(int,raw_input().split())
c=[-1]*N
for i in range(N+1):
 if c[A[i]-1]!=-1:
  break
 c[A[i]-1]=i
j=c[A[i]-1]
i=N-i
for k in range(1,N+2):
 res=com(N+1,k,mod)
 if k-1<=i+j:
  res-=com(i+j,k-1,mod)
 print res%mod

Submission status: Accepted

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline


#N=int(input())

N=int(input())
A=list(map(int,input().split()))
if N==1:
    print(1)
    print(1)
    exit()
mod=10**9+7
fac=[1,1]
for i in range(2,N+2):
    fac.append(fac[i-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]


def comb(a,b):
    if a<b:
        return(0)
    if a==0 or b==0:
        return(1)


    return(fac[a]*ifac[a-b]*ifac[b]%mod)



data=[[] for i in range(N+1)]
for i in range(len(A)):
    data[A[i]].append(i)
a,b=[i for i in data if len(i)>=2][0]

z=a+len(A)-b-1


for n in range(1,N+2):
    #print(N+1,n,z,n-1)
    print((comb(N+1,n)-comb(z,n-1))%mod)

Submission status: Accepted

Solution code:
import collections

mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
cnt=collections.Counter(arr)
for key in cnt.keys():
  if cnt[key]==2:
    K=key
pos1=-1
pos2=-1
for i in range(n+1):
  if arr[i]==K:
    if pos1==-1:
      pos1=i
    else:
      pos2=i
A=pos1
B=pos2-pos1-1
C=n-pos2
facts=[1]
for i in range(1,n+1):
  facts.append((facts[-1]*i)%mod)
revfacts=[1]
for i in range(1,n+1):
  revfacts.append(pow(facts[i],mod-2,mod))
ans=[]
for i in range(1,n+2):
  ways1=0
  if i<=A+B+C:
    ways1=(facts[A+B+C]*revfacts[i]*revfacts[A+B+C-i])%mod
  ways2=0
  if i>=2 and i-2<=A+B+C:
  	ways2=(facts[A+B+C]*revfacts[i-2]*revfacts[A+B+C-(i-2)])%mod
  ways3=0
  if i>=1 and i-1<=A+C:
    ways3=(facts[A+C]*revfacts[i-1]*revfacts[A+C-(i-1)])%mod
  ways4=0
  if i>=1 and i-1<=A+B+C:
    ways4=(2*facts[A+B+C]*revfacts[i-1]*revfacts[A+B+C-(i-1)]-2*ways3)%mod
  ans.append((ways1+ways2+ways3+ways4)%mod)
for val in ans:
  print(val)

Submission status: Accepted

Solution code:
mod = 10**9 + 7;

def inv(x):
  m = mod
  u = 1
  v = 0
  while m:
    t = x // m
    x -= t * m
    x, m = m, x
    u -= t * v
    u, v = v, u
  return u % mod

n = int(input())

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

a = list(map(int, input().split()))
num = [0] * (n + 1)
for x in a:
  num[x] += 1

two = -1
for i, c in enumerate(num):
  if c == 2:
    two = i
    break

l = -1
r = -1;
for i in range(n + 1):
  if l == -1 and a[i] == two:
    l = i
  elif l != -1 and a[i] == two:
    r = n - i

for k in range(1, n + 2):
  if k - 1 <= l + r:
    print((fac[n + 1] * inv(fac[k] * fac[n + 1 - k]) - fac[l + r] * inv(fac[k - 1] * fac[l + r - k + 1])) % mod)
  else:
    print(fac[n + 1] * inv(fac[k] * fac[n + 1 - k]) % mod)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    a=LI()
    def cmb(n, r, mod):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return (fact[n] * factinv[r] * factinv[n-r])%mod

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]
    
    for i in range(2, N + 5):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
        
    loc=[-1]*N
    mu=[-1,-1]
    for i in range(N+1):
        if loc[a[i]-1]==-1:
            loc[a[i]-1]=i
        else:
            mu[0]=loc[a[i]-1]
            mu[1]=i
    N1=mu[0]
    N2=N-mu[1]
    
    for i in range(N+1):
        if i==0:
            print(N)
        else:   
            print((cmb(N+1,i+1,mod)-cmb(N1+N2,i,mod))%mod)
        
            
    
            
            
        


main()

Submission status: Accepted

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

# とりあえず二項係数を答えにぶち込む
fact = [1]
for i in range(1, N + 2):
    fact.append(fact[-1] * i % mod)


ans = [0] * (N + 2)
fN = fact[N + 1]
for i in range(1, N + 2):
    div = fact[i] * fact[N - i + 1] % mod
    value = fN * pow(div, mod - 2, mod) % mod
    ans[i] = value

# 数列Aの中に2つあるやつx
# xの左側、右側にあるやつをカウントする
x = Counter(A).most_common()[0][0]
left = A.index(x)
right = N - A.index(x, left + 1)
M = left + right

for i in range(0, M + 1):
    num = fact[M]
    div = fact[i] * fact[M - i] % mod
    comb = num * pow(div, mod - 2, mod) % mod
    ans[i + 1] = (ans[i + 1] - comb + mod) % mod

print(*ans[1:], sep="\n")

Submission status: Accepted

Solution code:
from collections import Counter


class Combination:
    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    N = int(input())
    A = tuple(map(int, input().split()))
    mod = 10 ** 9 + 7

    X = Counter(A).most_common()[0][0]
    left = A.index(X)
    right = A[::-1].index(X)
    LR = left + right

    comb = Combination(10 ** 5 + 10)

    ans = []
    for i in range(1, N + 2):
        val = comb(N+1, i)-comb(LR, i-1)
        val = (val + mod) % mod
        ans.append(val)

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

Submission status: Accepted

Solution code:
from collections import Counter

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

U = N + 10
fact = [1] * (U + 1)
inv = [1] * (U + 1)

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

inv[U] = pow(fact[i], mod - 2, mod)
for i in range(U, 0, -1):
    inv[i - 1] = inv[i] * i % mod


def comb(N, r):
    if r < 0 or r > N:
        return 0
    res = fact[N] * inv[r] % mod
    res = res * inv[N - r] % mod
    return res


X = Counter(A).most_common()[0][0]
left = A.index(X)
right = A[::-1].index(X)
LR = left + right

for i in range(1, N + 2):
    ans = comb(N+1, i)-comb(LR, i-1)
    ans = (ans + mod) % mod
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

U = 10**5+1
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
    
def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
n = int(input())
A = list(map(int, input().split()))
x = Counter(A).most_common()[0][0]
left = A.index(x)
right = A[::-1].index(x)
for k in range(1, n+2):
  ans = comb(n+1, k) - comb(left+right, k-1)
  ans %= MOD
  print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

U = 10**5+1
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
    
def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
n = int(input())
A = list(map(int, input().split()))
x = Counter(A).most_common()[0][0]
left = A.index(x)
right = A[::-1].index(x)
print(n)
for k in range(2, n+2):
  ans = comb(n+1, k) - comb(left+right, k-1)
  ans %= MOD
  print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

def cmb(n, k):
    if k > n:
        return 0
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 5 + 10 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

N = ir()
A = lr()
double = 0
used = set()
for i, a in enumerate(A):
    if a in used:
        double = a
        index_back = i
        break
    used.add(a)

index_front = A.index(double)
x = N + 1 - (index_back - index_front)
print(N)
for i in range(2, N+1):
    answer = cmb(N+1, i) - cmb(x-1, i-1)
    print(answer % MOD)

print(1)
# 10