AtCoder Grand Contest 028 B - Removing Blocks

B - Removing Blocks

一つのあまりのとり忘れで黄パフォを棒に振った。以下説明。

番目を取り除くことで、番目が加算されるときのことを考えます。番目と番目が連結であるための条件は、から番目の全てのブロックが残っていることです。

次に、これらのブロックを取り除く順番を考えます。から番目のブロックのうち、番目は一番最初に取り除かれなければならず、その他は番目のブロックが取り除かれた後であれば、いつ取り除いても構いません。

ここで、個のブロックを全て'x'とおくと、求めたい通り数は、

「個のブロックを1列に並べるとき、先頭の'x'に番目のブロックをあてはめ、その他の'x'に残りをあてはめて並べるときの場合の数」

になります。これを求めるのは簡単で、

という式になります（文字を並べて、その中に特定の部分文字列が存在する場合の数っぽいもの）。簡単にすると、

という式になります。この値については、逆元を用いてで割った余りを求めることができます。

後はこの通り数の計算を各ブロックについて行います。の遷移をを例にして見てみると、

j=1 : 1 2 3 4
j=2 : 2 1 2 3
j=3 : 3 2 1 2
j=4 : 4 3 2 1

という感じにスライドして動いています。つまり、一番最初の和だけ求めて、後は両端だけ見ればいいです。。自分のコードをちゃんと読もうという教訓。

Submission #3401530 - AtCoder Grand Contest 028

#include "bits/stdc++.h"

using namespace std;
using ll = long long;

const long long MOD = 1e9 + 7;

// mod m での a の逆元
ll modinv(ll a, ll m) {
	ll b = m, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

ll n, ans, sum, a[100010];
ll fact = 1, ifact[100010], invcul[100010];

int main() {
	cin >> n;
	for (int i = 0;i < n;i++)cin >> a[i];
	for (ll i = 2;i <= n;i++) {
		fact *= i;//階乗を求める
		fact %= MOD;
	}
	for (int i = 0;i < n;i++) {
		ifact[i + 1] = modinv(i + 1, MOD);
		invcul[i + 1] = fact * ifact[i + 1] % MOD;
		sum += invcul[i + 1];
		sum %= MOD;//ここを忘れていた。切腹。
	}
	ans += sum * a[0] % MOD;
	for (int i = 1;i < n;i++) {
		sum -= invcul[n - i + 1];
		sum += MOD;
		sum += invcul[i + 1];
		sum %= MOD;
		ans += sum * a[i] % MOD;
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}