AGC028

B - Removing Blocks (600)

B - Removing Blocks

概要

個のブロックが横に並べてあり、左から番目のブロックにはコストが対応している。
これらのブロックを１つずつ全て壊していくことを考える。また、ブロックを壊すとき、と連結なすべてのブロック(ブロックを含む）分のコストがかかるとする。
全ての壊し方について、コストの総和を求めよ。(mod で解答)

制約

方針

ブロックについて、何回コストがかかるかを考える。
このとき、をブロックを壊したときにブロックのコストがかかる回数とすると、求める答えはとなる。

を固定して考える。
通りの各壊し方について、ブロックのコストがかかるのはブロックを壊すときの高々回である。
どのような壊し方でブロックのコストがかかるかというと、
ブロックからブロックの間でブロックを最も早く壊すような壊し方である。

このような壊し方が何通りあるかを考える。すなわちを求める。
ブロックからブロックまでのブロックの個数をとすると、である。
また、それ以外のブロックの個数は個である。

下記ステップでブロックを壊す順序を選んでいくことを考える。

1. ブロックからブロックまでに割り当てる順番の数字の組み合わせ、それ以外のブロックに割り当てる順番の数字の組み合わせを決める
2. ブロックからブロックまでに割り当てられた数字の順番を決める
3. それ以外のブロックに割り当てられた数字の順番を決める

1.は通り。2.はが先頭という制約があるため通り。3.は通り。
よって、

の和をとるときは、の累積和を前計算しておくとでの和がなくなり、オーダーになる。

感想

下記ブログを参考にしました。
sigma1113.hatenablog.com

数え上げの考え方の理解が難しい。。

解答

Submission #3919344 - AtCoder Grand Contest 028

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1e9 + 7;
 
ll mod(ll a, ll b){
  a %= b;
  return a < 0 ? a + b : a;
}
 
ll powmod(ll a, ll b){
  if(b == 0) return 1;
  if(b & 1) {
    return a * powmod(a, b - 1) % MOD;
  } else {
    ll d = powmod(a, b / 2) % MOD;
    return d * d % MOD;
  }
}
 
ll sub(ll a, ll b){
  a %= MOD, b %= MOD;
  a -= b;
  return a < 0 ? a + MOD : a;
}
 
 
ll inv(ll a){
	return powmod(a, MOD - 2);
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll n;
	cin >> n;
 
	ll a[n];
	rep(i, n) cin >> a[i];
 
	ll fact_n = 1;
	// fact_n = 1 * 2 * ... * n
	for(ll i = 1; i <= n; i++){
		fact_n *= i;
		fact_n %= MOD;
	}
	// cout << fact_n << endl;
 
	ll invs[n+1];
	// invs[i] = 1/i
	for(ll i = 1; i <= n; i++){
		invs[i] = inv(i);
	}
 
	ll s[n];
	// s[i] = 1/1 + 1/2 + ... + 1/(i+1)
	s[0] = 1;
	for(ll i = 1; i < n; i++){
		s[i] = s[i-1] + invs[i+1];
		s[i] %= MOD;
	}
 
	ll ans = 0;
	rep(i, n){
		ans += (s[i] + s[n-1-i] - 1) * a[i];
		ans %= MOD;
		// cout << i << " " << ((s[i] + s[n-1-i] - 1) * a[i]) % MOD << endl;
	}
	ans *= fact_n;
	ans %= MOD;
 
	cout << ans << endl;
}