kmjp's blog

競技プログラミング参加記です

TopCoder SRM 798: Div1 Medium ExpectedValue

ミスがもったいない。
https://community.topcoder.com/stat?c=problem_statement&pm=16219&rd=18491

問題

正整数Nが与えられる。
1~NのPermutationのうち、全iに対しP[i]!=iを成す、すなわち攪乱順列を成すものを考える。
f(P)を、2要素を選んで要素をswapする処理を繰り返し、Pを昇順にする最低処理回数とする。
攪乱順列のいずれかを等確率で選んだ時、f(P)の期待値を求めよ。

解法

N要素の攪乱順列の数g(N)は定番でg(N)=(N-1)*(g(N-1)+g(N-2))で求められる。
h(N)を全攪乱順列におけるf(P)の総和とすると、h(N)/g(N)が解である。
よってあとはh(N)を求めることを考えよう。

N頂点からなるグラフで、i→P[i]と辺が張ってあるケースを考える。
長さkの閉路があると、それらを昇順に戻すのにswap回数が(k-1)回かかる。
先頭の要素が、長さmの閉路に含まれるとすると、

  • 先頭以外の閉路に含まれる要素の選び方がP(N-1,m-1)通り
  • それらを昇順に戻すのにswap回数が(k-1)回
  • 残りN-m要素の攪乱順列の組み合わせはf(N-m)通り
  • 残りN-m要素の攪乱順列による解への寄与分は、m要素の閉路1つにつきh(N-m)通り

なので、mを総当たりしながら
h(N) += P(N-1,m-1)**1
を計算すればよい。

上記手順ではO(N^2)かかるが、攪乱順列の計算式を応用してO(N)でも解ける様子。

const ll mo=1000000007;
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll modpow(ll a, ll n=mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll memo[1515];
ll kan[1515];

class ExpectedValue {
	public:
	
	ll hoge(int N) {
		if(memo[N]>=0) return memo[N];
		if(N==1) return 0;
		if(N==0) return 0;
		ll ret=0;
		
		int num;
		for(num=2;num<=N;num++) (ret+=comb(N-1,num-1)*fact[num-1]%mo*((num-1)*kan[N-num]%mo+hoge(N-num)))%=mo;
		return memo[N]=ret;
	}
	
	int solve(int N) {
		int i;
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
		
		kan[0]=1;
		for(i=2;i<=N;i++) kan[i]=(kan[i-1]+kan[i-2])*(i-1)%mo;
		
		MINUS(memo);
		return hoge(N)*modpow(kan[N])%mo;
		
	}
}

まとめ

凡ミス地獄からいい加減抜けたい。

*1:m-1)*g(m)+h(N-m