https://smijake3.hatenablog.com/entry/2019/03/06/002846

組み合わせを計算する問題は、計算の視点がうまく合わせられないとなかなか計算できなくて、頭を抱える...。
結局、公式の解法を見て通した。

atcoder.jp

問題概要

${N}$ 個のブロックが一列に並んでいて、 ${i}$ 番目のブロックの重さは ${A_i}$ である。

このブロックを1つずつ取り除くが、このブロックを取り除く際のコストはその時点で繋がっているブロックの重さの総和になる。

ブロックの取り除き方は ${N!}$ 通り存在するが、この ${N!}$ 通りの各順番の操作コスト和の総和をmod ${10^9 + 7}$ で求めよ。

制約

${1 \le N \le 10^5}$
${1 \le A_i \le 10^9}$

解法

各ブロックの重さ ${A_i}$ がそれぞれ何回足されるかを求めることで解を計算する。

初めに、 ${N!}$ 通りあるブロックの取り除き方の中で、 ${j}$ 番目のブロックを取り除く際に ${i}$ 番目のブロックの重さ ${A_i}$ がコストとして足される、取り除き方の通り数を計算する。
ここでは、 ${L = | i - j | + 1}$ とする。

ここで、 ${i}$ 番目と ${j}$ 番目の間の ${L}$ 個のブロックが連結状態のまま、それ以外の ${N-L}$ 個のブロックから ${K}$ 個( ${0 \le K \le N - L}$ )のブロックが取り除かれ、その後に ${j}$ 番目のブロックが取り除かれる場合の通り数を考えてみる。

この通り数は ${}_{N-L}P_{K} \times 1 \times (N - K - 1)!$ で計算でき、
各 ${K}$ に対する通り数の和は、

$\sum_{K=0}^{N-L} {}_{N-L}P_{K} \times 1 \times (N - K - 1)!$
$= (N-L)!(L-1)! \sum_{K=0}^{N-L} {}_{N-K-1}C_{L-1} = \frac{N!}{L}$

と計算できる。( ${\sum_{L=K}^{N} {}_{L-1} C_{K-1} = {}_NC_K}$ を利用する)

(公式解説の確率 ${\frac{1}{|i - j| + 1}}$ は、 ${N}$ 個のブロックをランダムに取り除くと考えた時に、 ${i}$ 番目と ${j}$ 番目の間のブロックの中で初めて取り除くブロックが ${j}$ 番目である確率、と読み直したらしっくりきた)

次に、 ${i}$ 番目のブロックのコスト ${A_i}$ が足される回数 $\sum_{j=1}^{N} \frac{N!}{|i - j| + 1}$ を計算するが、これは事前に累積和を求めておいた上で計算すればよい。

具体的には、 ${S_x = \frac{1}{1} + \frac{1}{2} + ... + \frac{1}{x}}$ とおくと、

$\sum_{j=1}^{N} \frac{N!}{|i - j| + 1} = S_i + S_{N-i+1} - 1$

で計算でき、これは累積和 ${S_x}$ により ${O(1)}$ で計算できる。

これで、解を ${O(N)}$ で計算できる。

実装

提出コード(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)