問題概要
問題ページ
-
-
D - 11
問題ページへ移動する
問題文
\(1,...,n\) の \(n\) 個の整数からなる長さ \(n+1\) の数列 \(a_1,a_2,...,a_{n+1}\) が与えられます。
この数列には \(1,...,n\) のどの整数もかならず \(1\) 回以上出現することが分かっています。
\(k=1,...,n+1\) のそれぞれについて、与えられた数列の長さ \(k\) の（連続とは限らない）部分列の個数を求め、
\(10^9+7\) で割ったあまりを出力して下さい。
注意
- \(2\) つの部分列が数列として同じであれば、元の数列での位置が異なっていたとしても、\(1\) 通りと数えます。
- 数列 \(a\) の長さ \(k\) の部分列とは、\(a\) の要素のうち \(k\) 個を選んで、
それらを順番を変えずに取り出して並べた数列のことを指します。
例えば、数列 \(1,2,3,4,5\) の長さ \(3\) の部分列には、 \(1,3,5\) や \(1,2,3\) などがあります。
一方で、\(3,1,2\) や \(1,10,100\) はこの数列の部分列ではありません。
制約
- \(1 \leq n \leq 10^5\)
- \(1 \leq a_i \leq n\)
- \(1,...,n\) のどの整数も必ず数列に出現する。
- \(n,a_i\) は整数である。
問題の考察
ACコード
import sys
import collections
def combination_mod_list(n, m):
d = collections.defaultdict(int)
denominator = 1
molecule = 1
for i in range(n + 1):
r = min(n - i, i)
if (n, r) not in d:
if r == 0:
d[n, i] = 1
else:
denominator = (denominator * (n - i + 1)) % m
molecule = (molecule * i) % m
d[n, r] = denominator * pow(molecule, m - 2, m) % m
else:
break
return d
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
n = int(input().rstrip('\n'))
a = list(map(int, input().rstrip('\n').split()))
d = collections.defaultdict(int)
f = l = 0
for i in range(len(a)):
if a[i] not in d:
d[a[i]] = i
else:
f = d[a[i]]
l = n - i
break
cb_1 = combination_mod_list(n + 1, mod)
cb_2 = combination_mod_list(f + l, mod)
for i in range(len(a)):
t = cb_1[n + 1, min(i + 1, (n + 1) - (i + 1))]
if i <= f + l:
t -= cb_2[f + l, min(i, f + l - i)]
print(t % mod)
if __name__ == '__main__':
solve()