AtCoder: AtCoder Grand Contest 028 - B問題: Removing Blocks
組み合わせを計算する問題は、計算の視点がうまく合わせられないとなかなか計算できなくて、頭を抱える...。
結局、公式の解法を見て通した。
問題概要
個のブロックが一列に並んでいて、番目のブロックの重さはである。
このブロックを1つずつ取り除くが、このブロックを取り除く際のコストはその時点で繋がっているブロックの重さの総和になる。
ブロックの取り除き方は通り存在するが、この通りの各順番の操作コスト和の総和をmod で求めよ。
制約
解法
各ブロックの重さがそれぞれ何回足されるかを求めることで解を計算する。
初めに、通りあるブロックの取り除き方の中で、番目のブロックを取り除く際に番目のブロックの重さがコストとして足される、取り除き方の通り数を計算する。
ここでは、とする。
ここで、番目と番目の間の個のブロックが連結状態のまま、それ以外の個のブロックから個()のブロックが取り除かれ、その後に番目のブロックが取り除かれる場合の通り数を考えてみる。
この通り数は で計算でき、
各に対する通り数の和は、
と計算できる。( を利用する)
(公式解説の確率 は、個のブロックをランダムに取り除くと考えた時に、番目と番目の間のブロックの中で初めて取り除くブロックが番目である確率、と読み直したらしっくりきた)
次に、番目のブロックのコストが足される回数 を計算するが、これは事前に累積和を求めておいた上で計算すればよい。
具体的には、 とおくと、
で計算でき、これは累積和により で計算できる。
これで、解を で計算できる。
実装
提出コード(Python3): Submission #4433694 - AtCoder Grand Contest 028
N = int(input()) *A, = map(int, input().split()) MOD = 10**9 + 7 # 事前計算の累積和 S = [0]*(N+1) r = 0 for i in range(1, N+1): S[i] = r = (r + pow(i, MOD-2, MOD)) % MOD # Σ_i A[i] * (S_i + S_{N-i+1} - 1) ans = 0 for i in range(N): ans += A[i] * (S[i+1] + S[N-i] - 1) # 最後に N! を掛ける for i in range(1, N+1): ans = ans * i % MOD print(ans)