AGC028 B - Removing Blocks
問題
n個のブロックが一列に並んでおり、左からi番目のブロックの重さはa[i]である
これらのブロックに対して「まだ取り除かれていないブロックを1つ取り除き、そのブロックと連結なブロックの重さの総和をスコアに加える」という操作をn回行う
操作の列n!通り全てについて、スコアの合計を求め、その総和を求めよ
解法
p(i,j): ブロックiを取り除くときにブロックiとjが連結である確率
とする
ブロックiを取り除くときブロックiとjが連結であるということは、ブロックiとjの間にあるブロックの中で一番最初に取り除かれるブロックがブロックiであるということ
よって
p(i,j) = 1 / (abs(i-j)+1)
となる
あとは累積和をとっておいて
Σ a[i] * (Σs(i,j)) * n!
を求めればok
n!通り全ての和みたいな問題は確率を考えるってのが典型なのかな
何かの企業コンテストで同じ発想の問題を見た記憶がある
#define int long long int n, a, f[100100], s[100100], res; signed main() { f[0] = 1; reps(i,1,100100) f[i] = f[i-1]*i %mod; reps(i,1,100100) s[i] = (s[i-1] + mop(i,mod-2)) %mod; cin >> n; rep(i,n) { cin >> a; (res += (s[i+1] + s[n-i] - 1) * a) %= mod; } (res *= f[n]) %= mod; cout << res << endl; }
鮮やかだなぁ・・