AGC028 B問題 Removing Blocks

beta.atcoder.jp

editorialで確率がどうのこうの書いてあって ??? となったので。

方針

最終的に求めたい答えは当たり前だけど  a_0 A_0 + a_1 A_1 + \cdots + a_n A_n の形でかける.
そして ,  a_i の値を求めにいく.

  •   a_i = \displaystyle \sum_{j} ( A_j を取り除く時にA_iが連結である場合の数 )  で求めること.
  •  A_j を取り除く時にA_iが連結である場合の数を全体の  N! 通りの中の割合で求めること.

この二つが大きなポイントだと思う. 二つ目の方から考える.

2つ目のポイントの考察

※下記では j \leq i として議論する.
 A_j を取り除く時にA_iが連結である  \Leftrightarrow  A_j , \cdots , A_i 間で A_jが最初に除かれる.
と言い換えることができる.では,その場合の数はN!のうちどのくらいの割合なのか?

 A_j \cdots A_i 間で,初めて取り除かれるものを A_kとし , これによって事象を定義する.
すなわち , 全事象  \Omega = \displaystyle \bigcup_{k=j}^i   \left\{ 事象k ; A_j \cdots A_i 間でA_kが初めて除かれる \right\}
これらは排反の事象であり , 確率(場合の数の割合)はどの事象も等しく  P(k) = \dfrac{1}{i - j + 1} となっている.

A_jが最初に除かれる場合の数を知りたかったので, 全体の場合の数をかけて

 N! P(j) = \dfrac{N!}{i - j + 1}

あと ,  j \leq i と条件を取っ払えば

 N! P(j) = \dfrac{N!}{|i - j| + 1}

1つ目のポイントの考察

あとはさっきの結果を代入してあげればok

 a_i = \displaystyle \sum_{j}  \dfrac{N!}{|i - j|+ 1}

最後にもう一工夫.
  0 \leq |i-j| \leq N より ,  \displaystyle \sum_{k = 0}^N \dfrac{N!}{k+ 1} を先に計算(累積和)しておくことができる.  O(N)
すると  a_i  O(1)で求まるようになる.

なので,全体は答え  a_0 A_i + a_1 A_1 + \cdots + a_n A_n O(N)で求まる.

ソースコード

N = int(input())
A = list(map(int,input().split(" ")))
mod = 10**9+7

# N!計算
fact = 1
for i in range(2,N+1):
    fact *= i
    fact %= mod

# 場合の数計算
rev = [ (pow((i),mod-2,mod)*fact)%mod for i in range(1,N+1) ]
# 累積和
for i in range(N-1):
    rev[i+1] += rev[i]
    rev[i+1] %= mod

# a_0 A_0 + a_1 A_1 + ... + a_n A_n を計算
ans = 0
for i in range(N):
    ans += A[i] * (rev[i] + rev[N-1-i] - rev[0]) % mod
    ans %= mod

print(ans)

感想

解けてから見ると問題文にわざわざ N!通りとか書いてくれてるのはヒントだったのかなぁと思ったり。