Codeforces ECR #057 : E. The Top Scorer

Eが難しいよね…。
https://codeforces.com/contest/1096/problem/E

問題

P人である競技を行った。
各人のスコアは非負整数であり、その総和はSである。
優勝者は、最多スコアを取った人である。もし最多スコアが同着なら、ランダムで等確率で誰か1名が優勝者となる。

番号１番の人のスコアはR以上であったことがわかっている。
その条件のもとあらゆるスコア配分が等確率で生じるとき、その人の優勝確率を求めよ。

解法

全体のスコアの組み合わせはである。
あとはそのうち番号１番の人が優勝者となる組み合わせとそれぞれにおける優勝確率を求めよう。

F(S,X,Y) := P人中Y人がX点で同着最多スコアで、かつ番号1番がそこに含まれる組み合わせ
とすると、X,Yを総当たりしつつ(F(S,X,Y)/Y)の総和を求めればよい。

1番以外の(P-1)人のうち(Y-1)人が同着X点で、残り(P-Y)人で(S-XY)点を分け合い、かつ彼らはX点未満とする。
G(S,X,Y) := Y人の各人がX点以下で、かつ総和がS点となる組み合わせ
とするととなる。あとはG(S,X,Y)を考えよう。

(Y+1)点以上取った人がi人いるケースを包む除く原理で取り除く、と考えると

となる。

int P,R,S;
ll mo=998244353;

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

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


ll hoge(int sum,int num,int ma) {
	if(num==0) return sum==0;
	
	ll ret=0;
	for(int i=0;i<=num;i++) {
		if(sum-i*(ma+1)<0) break;
		ll pat=comb(num,i)*comb(sum-i*(ma+1)+num-1,num-1)%mo;
		if(i%2) ret+=mo-pat;
		else ret+=pat;
	}
	
	return ret%mo;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P>>S>>R;
	
	ll ret=0;
	
	for(i=R;i<=S;i++) {
		for(x=1;x<=P;x++) {
			(ret+=comb(P-1,x-1)*modpow(x)%mo*hoge(S-i*x,P-x,i-1))%=mo;
		}
	}
	
	
	ret=ret*modpow(comb(S-R+P-1,P-1))%mo;
	cout<<ret<<endl;
}

まとめ

点数で包除原理やるかと思ったら、人数でやるのか…。