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

CF#230よりは簡単か。
http://codeforces.com/contest/396/problem/D

問題

1～NのpermutationとなるPが与えられる。
辞書順でP以下のpermutationにおけるinversion数の総和を求めよ。

解法

n要素のpermutationの数をF(n)とする。
F(n)はF(n-1)から再帰的に計算できる。
既に1～(n-1)のpermutationがあって、どこかにnを追加して数列を作ろうとすると、元のn倍の数の数列ができる。
よって1～(n-1)から得られるinversion数はF(n-1)*n。
また、全部でn!個ある整数のうち、nは平均的に(n-1)/2個反転すると考えられるので、nによるinversion数はn!*(n-1)/2。
あわせてF(n) = F(n-1)*n + n!*(n-1)/2。

後はBIT等で1～Nのうち未登場の数を管理しながら、先頭の要素から処理をする。
i要素目P[i]を考える。
i要素目の値がP[i]未満の場合、残り(N-i)要素はどんな並びでもこのpermutationはP以上にはならないので、(P中におけるP[i]未満の未登場の整数)*F(N-i)の分答えに加算できる。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void update(int e, V val) {e++; while(e<=1<<ME) bit[e-1]+=val,e+=e&-e;}
};
BIT<int,21> bt;

ll numinv[1010000];
ll mo=1000000007;
ll P[1010000];
int N,A[1010000];

BIT<int,21> bit;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	P[0]=P[1]=1;
	for(i=2;i<=1001000;i++) {
		numinv[i]=(i*numinv[i-1]+1LL*i*(i-1)/2%mo*P[i-1]) % mo;
		P[i]=P[i-1]*i%mo;
	}
	
	cin>>N;
	FOR(i,N) bit.update(i+1,1);
	ll ls=0;
	ll ret=0;
	FOR(i,N) {
		cin>>x;
		y=bit.total(x-1);
		// less than x
		ret += y*P[N-i-1]%mo*ls+1LL*y*(y-1)/2%mo*P[N-i-1]+y*numinv[N-i-1];
		ret %= mo;
		// take x
		ls = (ls+y)%mo;
		bit.update(x,-1);
	}
	ret += ls;
	
	cout<<ret%mo<<endl;
}

まとめ

これはCでもいいんじゃないかな。