Codeforces ECR #109 : E. Assimilation IV

不参加だった回。
https://codeforces.com/contest/1525/problem/E

問題

N個の町とM個の場所があり、それぞれの距離が1～Nで与えられる。
ここで町を順に指定すると、その町はそれぞれ指定順に距離がN以下、(N-1)以下、(N-2)以下…の場所を管理できる。
町の指定順N!が等確率で選択されたとき、どの町にも管理されない場所の個数の期待値を求めよ。

解法

場所ごとに、その場所が管理されない確率を求められれば、その総和が解となる。
これには、i番目の町を選ぶとき、距離が(N-i)より大きな町が選ばれる確率をそれぞれ掛け合わせればよい。

int H,W;
int D[21][50505];
const 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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>D[y][x];
	ll ret=0;
	FOR(x,W) {
		vector<int> V;
		FOR(y,H) V.push_back(D[y][x]);
		sort(ALL(V));
		ll safe=1;
		FOR(y,H) {
			int ok=V[y]-1-y;
			safe=safe*ok%mo*modpow(H-y)%mo;
		}
		(ret+=(1+mo-safe))%=mo;
	}
	cout<<ret<<endl;
}

まとめ

問題設定は長くてややこしいけど、コードは短い。