Google Code Jam 2022 Round 1C : C. Intranets

割としんどい。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000877b42/0000000000afeb38

問題

整数M,Kが与えられる。
M頂点の完全無向グラフを考える。
M*(M-1)/2の各辺に優先度をつけたとする。

各頂点に対し、その点がつながる辺のうち優先度最大の1辺をactiveにしたとする。
優先度の付け方は(M*(M-1)/2)!通りあるが、そのうちactiveな辺のみ考えたグラフでは連結成分がK個になる確率はいくらか。

解法

Smallケースにおいては、
dp(i,x,y) := 優先度高い順にi番目までの辺を決めたとき、activeな辺が確定した頂点がx個で、それらの連結成分がy個
というDPをO(M^4)で解き、dp(M*(M-1)/2,M,K)を答えればよい。

LargeケースではMが大きいので、もっと計算量を減らそう。
ある辺が、両端の点に取って最大優先度であるようなものを考えると、その辺の数は連結成分の数に一致する。
よって、そのような辺を数え上げることにしよう。

f(x) := 上記辺がちょうどx個あるような確率
とすると求めたいのはf(K)である。
これを直接求めるのは難しいので、
g(x) := 上記辺がx個以上あるような確率

を求め、g(K)、g(K+1)、g(K+2)…を包除原理の要領で足し引きしてf(x)を求めよう。
g(1)、g(2)、…g(x)はEditorialの公式でまとめてO(x)で求められるし、x個の辺の選び方もまとめてO(x)で求められる。

ll M,K;
const ll mo=1000000007;

ll from[53][53];
ll to[53][53];


ll G[505050];

const int NUM_=1400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

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_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>M>>K;
	ll E=M*(M-1)/2;
	
	ll q=1;
	ll ret=0;
	for(i=2;i<=M;i+=2) {
		(q*=modpow(comb(M,2)-comb(M-i,2)))%=mo;
		if(i>=2*K) {
			ll G=fact[M]*factr[M-i]%mo*modpow(modpow(2,i/2))%mo*q%mo;
			ll a=comb(i/2,K)*G%mo;
			if((i/2-K)%2) a=mo-a;
			ret+=a;
		}
		
	}
	
	cout<<"Case #"<<_loop<<": "<<ret%mo<<endl;
}

void init() {
	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;
}

まとめ

Largeでマッチングの問題に落とし込むの、思いつける気がしないな…。