TopCoder SRM 838 : Div1 Medium DistinctFaces

Easyより楽だった…。
https://community.topcoder.com/stat?c=problem_statement&pm=17819

問題

いくつかのサイコロがある。それぞれのサイズをS[i]とすると、そのサイコロを振ると1～S[i]のいずれかの目が等確率で出る。

これらのサイコロを一気に振ったとき、ユニークな目の個数の期待値を答えよ。

解法

サイコロをサイズの大きい順に並べた状態で以下を考える。
f(n) := n番目のサイコロの目が、(1～(n-1))番目のサイコロのいずれとも異なる確率
とすると、解はsum(f(n))となる。

なので、f(n)を順次求めて行けばよい。

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

class DistinctFaces {
	public:
	int expectation(vector <int> count, vector <int> size) {
		vector<pair<int,int>> V;
		int i;
		FOR(i,count.size()) V.push_back({size[i],count[i]});
		sort(ALL(V));
		reverse(ALL(V));
		ll mul=1;
		ll sum=0;
		FORR(b,V) {
			ll s=b.first;
			ll a=(s-1)*modpow(s)%mo;
			FOR(i,b.second) {
				sum+=mul;
				(mul*=a)%=mo;
			}
		}
		return sum%mo;
		
	}
}

まとめ

割とすんなり解けたと思ったけど、そこそこ考察に時間かかってるな。