第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes (600)

B - Fusing Slimes

概要

数直線上にN個の点がある。点iの座標は正整数xiで表される。下記の操作をN-1回繰り返す。

• 最も右にある点以外の点のうち1点を選ぶ（点kとする）
• 点kをその点の右隣の点（点lとする）の位置に移動させる
• 移動後、点kと点lを同一視する（点の数が1つ減少したとみなす）

全ての操作の組み合わせは(N-1)!通りある。移動距離の合計を求めよ。

制約

2 ≦ N ≦ 10^5
1 ≦ xi ≦ 10^9

方針

元の出題は移動距離の総和の期待値 * (N-1)!ですが、点を選ぶ確率が等しいので移動距離の合計に読み替えました。

N-1回繰り返す操作を1まとまりとして「連」と呼ぶことにします。連は点を選ぶ順番を順列をみなすことで、1からn-1までの順列と対応します。
各連について、ある点が移動するごとに、(x1, x2), (x2, x3), ... , (x_(n-1), xn)の各区間が何回加算されるかを考えます。
例として、n=5（区間数4）で考えます。考える区間は(x1, x2), (x2, x3), (x3, x4), (x4, x5)です。
点を固定して考えてゆきます。

①点4
全ての連において(x4, x5)のみが加算されます。つまり、24回加算されます。

②点3
全ての連において(x3, x4)が加算されます。つまり、24回加算されます。
点4が点3より先に右に移動する連においては(x4, x5)も加算されます。
点3の行先にはすでに点4がなく、点3はもとの点4の位置を過ぎて点5の位置まで移動するためです。
この連の数は(1,2,3,4)の順列のうち、3より先に4がくる順列数と等しいです。
順列に「特定のx個の数字の後に1個の数字がくる」という制約を入れると組み合わせ数が1/(x+1)されます。
(直感的には、長さNの順列のうち、上記x+1個の数字の順列の(x+1)! 部分が、最後の1つが固定されることでx!になるイメージです)
つまり、12(= 4! / 2)回加算されます。

③点2
全ての連において(x2, x3)が加算されます。つまり、24回加算されます
点3が点2より先に右に移動する連において(x3, x4)も加算されます。つまり、12回加算されます
点3, 4が点2より先に右に移動する連において(x4, x5)も加算されます。つまり、8(= 4 ! / 3)回加算されます

③点1
全ての連において(x1, x2)が加算されます。つまり、24回加算されます
点2が点1より先に右に移動する連において(x2, x3)も加算されます。つまり、12回加算されます
点2, 3が点1より先に右に移動する連において(x3, x4)も加算されます。つまり、8(= 4 ! / 3)回加算されます
点2, 3, 4が点1より先に右に移動する連において(x4, x5)も加算されます。つまり、6(= 4 ! / 4)回加算されます

上記をまとめると、
(x1, x2)は24回
(x2, x3)は24+12 = 36回
(x3, x4)は24+12+8 = 44回
(x4, x5)は24+12+8+6 = 50回
加算されます。これを一般のnで計算すればよいです。

解答

Submission #9431200 - Dwango Programming Contest 6th

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
// combination
// O(n)
 
const ll MOD = 1e9 + 7;
const ll max_n = 101010;
ll fact[max_n];
bool fact_init = false;
 
ll pow(ll a, ll b){
	if(b == 0) return 1;
	if(b % 2 == 1) return a * pow(a, b - 1) % MOD;
 
	ll d = pow(a, b / 2) % MOD;
	return d * d % MOD;
}
 
ll comb(ll n, ll k){
	if(!fact_init){
		fact[0] = 1;
		fact[1] = 1;
 
		for(ll i = 2; i < max_n; i++){
			fact[i] = fact[i-1] * i;
			fact[i] %= MOD;
		}
 
		fact_init = true;
	}
 
	ll ret = fact[n];
	ret *= pow(fact[k],MOD-2);
	ret %= MOD;
	ret *= pow(fact[n-k],MOD-2);
	ret %= MOD;
	return ret;
 
	// X^(-1) = X^(p-2) (mod p) (Fermat's little theorem)
}
 
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;
 
	vector<ll> x(n);
	rep(i, n) cin >> x[i];
 
	ll _ = comb(1, 0);
	ll fct = fact[n-1];
 
	ll invs[n-1];
	invs[0] = 1;
	rep(i, n - 2){
		invs[i+1] = invs[i] + inv(i+2);
		invs[i+1] %= MOD;
	}
	
	ll ans = 0;
	rep(i, n-1) {
		ll t = (x[i+1] - x[i]) * fct;
		t %= MOD;
		t *= invs[i];
		t %= MOD;
 
		ans += t;
		ans %= MOD;
	}
 
	cout << ans << endl;
}