TopCoder SRM 781 : Div1 Medium RandomPartition

気付いてしまえば簡単。
https://community.topcoder.com/stat?c=problem_statement&pm=15955&rd=17857

問題

2N個の整数が与えられる。
これをN個ずつの集合に分ける。
片方は値を昇順にならべ、その数列をAとする。
もう片方は値を降順にならべ、その数列をBとする。

2つの数列の不安定さとは、|B[i]-A[i]|のN要素間の平均値を指す。
集合の分け方Comb(2N,N)通りにおいて、不安定さの期待値を求めよ。

解法

実は集合の分け方は関係なく不安定さは確定する。
元の2N個のうち小さい順N個がどこに行くかというと、AのprefixかBのsuffixに行き、その数は合計N個である。
つまり小さいN個は|B[i]-A[i]|の計算を行う際常に小さい方の値を担う。

結局、2N個の整数の上位N値の総和から下位N値の総和を引きNで割ればよい。

const ll mo=786433;

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

class RandomPartition {
	public:
	int expectedSum(vector <int> A, int N, int M, int B1, int B2) {
		
		int i;
		for(i=A.size();i<2*N;i++) {
			A.push_back((1LL*A[i-1]*B1+1LL*A[i-2]*B2)%M);
		}
		sort(ALL(A));
		ll sum=0;
		FOR(i,N) sum+=mo-A[i];
		FOR(i,N) sum+=A[i+N];
		sum=(sum%mo+mo)%mo;
		
		return sum*modpow(N)%mo;
		
		
	}
}

まとめ

450ptだしね。