Edit

【pythonでABC066を解説】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()

プログラミング

-Edit
-