Codeforces #956 : Div2 E. I Love Balls

これはすんなり。
https://codeforces.com/contest/1983/problem/E

問題

N個のボールのうち、K個は特別なボールである。
各ボールには整数値が書かれている。

2人でボールを交互に取り合う。
各自のターンでは、残されたボールのうちランダムで1つ取り、そこに書かれた整数値を自身のスコアに加える。
この時、特別なボールを取ると、さらに1つボールを取ることができる。

両者のスコアの期待値を求めよ。

解法

特別でないボールは(N-K)個ある。
よって先手はceil((N-K)/2)回、後手はfloor((N-K)/2)回特別でないボールを取るチャンスがあるので、両者スコアをその比率で分配する。
特別なボールはK個あるが、これらを取るチャンスは先手はceil((N-K+1)/2)回、後手はfloor((N-K+1)/2)回あるので、両者スコアをその比率で分配する。

int T;
int N,K;
ll V[505050];
const ll mo=1000000007;

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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		
		ll X=0,Y=0;
		FOR(i,N) {
			cin>>V[i];
			if(i<K) X+=V[i];
			else Y+=V[i];
		}
		if(K==N) {
			cout<<X%mo<<" "<<0<<endl;
			continue;
		}
		x=(N-K+1)/2;
		y=(N-K)-x;
		ll a=Y%mo*x%mo*modpow(x+y)%mo;
		if(x==y) x++;
		else y++;
		(a+=X%mo*x%mo*modpow(x+y))%=mo;
		
		cout<<a%mo<<" "<<(X+Y+mo-a)%mo<<endl;
			
	}
}

まとめ

Div2とはいえEの割に易しめな気がする。