AGC028 B問題 - kamojirobrothersのブログ

AtCoder Grand Contest 028のB問題を解いた。
時間内には解けなかったし、解説もよくわからなかった。
問題はこれ
B - Removing Blocks。
解説はこれ
https://img.atcoder.jp/agc028/editorial.pdf。
参考にしたのはこれ
AGC028 B問題 Removing Blocks - banbooooのブログ。

解説

解説でよく使われる確率を理解できたことが殆どなかった。
今回もそれ。
いろいろ調べてたら上の参考サイトを見つけた。
解説などに置ける、同様に確からしい確率は確率を表しているわけでなく、
背反な事象でそれぞれの個数が等しいもののことを言っているということがわかった。
数学っぽく言うと、数え上げ測度の等しい disjoint な可測集合たちのことを言っていることがわかった。
とはいえ、確率の気持ちで理解するのは大事っぽい。
同様に確からしいっぽい気持ちで考える問題もよく見る。

解説をします。
i番目のブロックを取り除いたとき、j番目のブロックの値が加算されるとする。
i番目からj番目までのブロックがどれも除かれておらず、その中で、i番目のブロックが初めに取り除かれる場合の数を求めれば良い。
$\sharp(\sqcup_{i \leq k \leq j}\{iからj番目までのブロックのうちk番目のブロックが初めに取り出される取り出し方全体\}) = N!$
が成り立つ。
互いに排反なので、
$\sum_{i\leq k \leq j}\sharp(\{iからj番目までのブロックのうちk番目のブロックが初めに取り出される取り出し方全体\}) = N!$
となる。
また、（同様に確からしいの部分だが、）各 $i \leq k \leq j$ に対して、
$\sharp(\{iからj番目までのブロックのうちk番目のブロックが初めに取り出される取り出し方全体\})$
は等しい。
従って、どの $i \leq k \leq j$ に対しても、
$\sharp(\{iからj番目までのブロックのうちk番目のブロックが初めに取り出される取り出し方全体\}) = \frac{N!}{|i-j|+1}$
となる。
特に、今は $k=i$ の場合である。
あとは、色んなサイト書いてあるように、累積和とかmodにおける逆元とか頑張ればできる。
プログラムは次のやつ。

def getInv(N):
    inv = [0] * (N + 1)
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q % i]) % Q
    return inv

from itertools import accumulate
N = int( input())
A = list( map( int, input().split()))
Q = 10**9 + 7
fact = [1]*(N+1)
invs = getInv(N)
accI = [0]*(N+1)
for i in range(N):
    fact[i+1] = fact[i]*(i+1)%Q
    accI[i+1] = (accI[i]+invs[i+1])%Q
factN = fact[-1]
ans = 0
for i in range(N):
    C = factN*(accI[i+1] + accI[N-i]-1)*(A[i]%Q)%Q
    ans += C
    ans %= Q
print(ans)