ARC077 D 11

Intro

• ARC077 D問題 「11」(600点) をpythonで解きました!

Point

• 逆元を使った組み合わせの計算

問題

1~nの数字からなる長さn+1の数列が与えられる。
(1~nの数字の中で、一つだけ２回出てくる数字があって、それいがいは1回しか出てこない)
k=1...n+1について、長さkの 連続とは限らない 部分列の個数を求めよ。
(答えは、10**9+7でMODをとる)

atcoder.jp

考えたこと

• 組み合わせ数のMODをとって答えにする-> 逆元の組み合わせ を 使いそう
• n個の数字で、数列には全ての数字が一個以上含まれてて、数列の長さは n+1。つまり、 重複する数字のみが二回出てきて 、その他の数字は一回しか出てこない
• 重複を気にせずに前組み合わせを求めてから、重複したものを除けば良さそう。

実装

1. まず、重複する数字について、一つ目が出てくる位置と二つ目が出てくる位置をそれぞれ求める。
2. 重複する数字をdとすると、数列は一つ目のdよりも前の部分(L1)と、二つのdの間の部分(L2)と、二つ目のdよりも後ろの部分(L3)、の３つに分けることができる。
   ( 数列は、[L1] d [L2] d [L3]の形になる )
3. 除くパターンは、 [L1からいくつか]+d+[L3からいくつか] のパターンになので、それを全体からのぞく
   (言い換えると、dとL2以外からk-1個選ぶ(kこのうち一つは、dなので、k-1個)

　submittion

# -*- coding: utf-8 -*-


import sys


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        if n < r:
            return 0
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
N = n+1
A = list(map(int, input().split()))
MOD = 10**9+7
# 重複する数字を見つける
already = set()
for i, l in enumerate(A):
    if l in already:
        dup_ind = i
        dup_num = l
        break
    else:
        already.add(l)
# 重複する数字について、その間にある数字の個数
mid_dup = dup_ind-A.index(dup_num)+1

F = FactMod(n+1, MOD)

# 全体から、重複分を除く
for k in range(1, n+2):
    all_pattern = F.comb(N, k)
    rem_pattern = F.comb(N-mid_dup, k-1)
    print((all_pattern-rem_pattern+MOD) % MOD)

Outro

• 組み合わせとMODって出ると、この逆元のやつ使うことが多いと思うので、ライブラリ作っとくと楽。
• 最近一日一文を目標に、500~600埋めをしててます。
• 解けない問題が多くて、辛いですが頑張りたいです。