Codeforces 396(#232 Div1) D. On Sum of Number of Inversions in Permutations

問題

長さnの順列p[i]が与えられる。
p[i]よりも辞書順で前にある全ての順列について、転置の総数の和をmod 10^9 + 7で求めよ。

制約条件

n≦10^6とか

方針

若い順列のうち、先頭のi個がpに一致するものの転置の総数は簡単に求められて、
それをi=0〜nまで足す。

先頭のi個がpに一致する順列の転置の総数は、
i+1個目を置いて、i+1個目以降にあるi以下の登場する回数の総和を求める、
というように自分より後ろにある小さい数を数えていけば漏れ重複なく数えられる。

i+1番目に1からp[i+1]-1を置く場合、
まずi+1番目に置いたことによる転置の増加を数える。
1〜p[i+1]-1の中で使っていない整数の個数をm個とすれば、
それぞれの数に対して自分より小さい数が一個あるからm * (m - 1) / 2通りで、
あと順列の残りの部分は自由に配置できるのでそのlen!倍が個数。

残りi+2番以降の部分が自由になるので、その転置の総数を数える。
a, bのような二数の選び方がC[len][2]通り、場所の選び方がC[len][2]通り、残りの数の置き方が(len-2)!通りになる。

i+1番目にp[i+1]を置く場合、i+2番目以降の順列の作り方をあらかじめ前計算しておくと、
p[i+1]以下の使ってない整数の個数 * 順列の作り方の転置が、p[i+1]により新たに増える。

ソースコード

int n, p[MX];
int bit[MX];
void add(int i, int x){
	for(; i < MX; i += i & -i) bit[i] += x;
}
int sum(int i){
	int res = 0;
	for(; i; i -= i & -i) res += bit[i];
	return res;
}

ll fact[MX], C2[MX], way[MX];
inline ll calc(int len){
	return len >= 2 ? C2[len] * C2[len] % mod * fact[len - 2] % mod : 0;
}
int main(){
	
	fact[0] = 1;
	rep(i, MX - 1) fact[i+1] = fact[i] * (i+1) % mod;
	for(int i = 2; i < MX; i++) C2[i] = i * (i - 1ll) / 2 % mod;
	
	scanf("%d", &n);
	rep(i, n) scanf("%d", p + i);
	
	way[n] = 1;
	for(int i = n - 1; i >= 0; i--){
		int below = sum(p[i]);
		way[i] += below * fact[n - i - 1] % mod;
		way[i] += way[i + 1];
		way[i] %= mod;
		add(p[i], 1);
	}
	memset(bit, 0, sizeof(bit));
	
	ll ans = 0;
	rep(i, n){
		int cnt = sum(p[i] - 1);
		int below = p[i] - 1 - cnt;
		
		//i番目にp[i]より小さいものを置いたとき、i + 1番目以降の数同士で出来る転置の総数
		ans += calc(n - i - 1) * below;
		
		//i番目にp[i]より小さいものを置いたとき、(i番目, 別の何か)で出来る転置の総数
		if(below > 1) ans += C2[below] * fact[n - i - 1] % mod; //
		
		//i番目にp[i]を置いたときに、(i番目, 別の何か)でできる転置の総数
		ans += below * way[i + 1] % mod;
		ans %= mod;
		
		//binary indexed treeで置いたものだけ数える
		add(p[i], 1);
	}
	cout << ans << endl;
	
	return 0;
}