Deltix Round, Summer 2021 : F. Sports Betting

Fまで割とサクサク解けた回。
https://codeforces.com/contest/1556/problem/F

問題

Nチームでスポーツの総当たり戦を行う。
各チームの強さはA[i]とする。
各試合の勝率は、互いの強さの比となるものとする。

あるチームが勝利チームであるとは、他の全チームに直接または間接的に勝利した状態をいう。
ある試合結果において、勝利チームは複数となることもあり得る。
勝利チーム数の期待値を求めよ。

解法

F(i,mask) := i番のチームが、maskで示すチーム群に直接勝利する確率
G(mask) := mask内の全チームは、mask内において互いに勝利チームである確率

G(mask)を求めると、mask内のチームがmask外に全勝すれば、勝利チーム数はBitcount(mask)だけとなる。
G(mask)の求め方だが、これはmask内に勝利者でないチームが出るケースを引けばよい。
これは、maskを勝利チームとそうでないチームに分離するパターンを総当たりし、その確率を求めればよい。
これはO(N^2*2^N)でF(i,mask)を求めておけば、O(N*3^N)で列挙することができる。

int N;
ll A[14];
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;
}

ll G[1<<14];
ll allwin[14][1<<14];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
	}
	int mask;
	FOR(i,N) {
		FOR(mask,1<<N) {
			allwin[i][mask]=1;
			FOR(j,N) if(mask&(1<<j)) (allwin[i][mask]*=A[i]*modpow(A[i]+A[j])%mo)%=mo;
		}
	}
	
	
	ll ret=0;
	FOR(mask,1<<N) if(mask) {
		G[mask]=1;
		for(int sm=mask;sm>=0;sm--) {
			sm&=mask;
			int oth=mask^sm;
			if(oth==0||oth==mask) continue;
			ll win=1;
			FOR(x,N) if(sm&(1<<x)) (win*=allwin[x][oth])%=mo;
			(G[mask]+=mo-G[sm]%mo*win)%=mo;
		}
		G[mask]=(G[mask]+mo)%mo;
		ll pat=__builtin_popcount(mask)*G[mask]%mo;
		FOR(x,N) if(mask&(1<<x)) {
			FOR(y,N) if((mask&(1<<y))==0) {
				(pat*=A[x]*modpow(A[x]+A[y])%mo)%=mo;
			}
		}
		ret+=pat;
	}
	cout<<ret%mo<<endl;
	
}

まとめ

F問題(Div1D問題相当)の割には易しめかも。