CF 16E Fish

Idea

对于(n)条鱼，它们两两不相遇的方案数为(frac{n(n-1)}{2})
对于鱼(i)吃掉鱼(j)，要经过以下三个事件

1. 鱼(i)，鱼(j)都在湖里；记为事件(A)
2. 鱼(i)，鱼(j)相遇；记为事件(B)
3. 鱼(i)吃掉鱼(j)；记为事件(C)

所以(P( ext{i吃j})=P(A)+P(B)+P(C))
设(f[x])为湖中鱼状态为(x)的状态，则

[f[x Xor (1<<j)]+=f[x] imes frac{2a[i][j]}{n(n-1)},i,jin x; ]

(n)为 ((x)_2) 下1的个数

Code

double f[1<<20]; 
double a[20][20];
int n,cnt;
inline int cal(int x){
	int cnt=0;
	while(x){
		cnt++;
		x^=x&(-x); 
	}
	return cnt;
}
signed main(){
	n=read();
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	scanf("%lf",&a[i][j]);
	f[(1<<n)-1]=1;
	for(int k=(1<<n)-1;k>0;k--)
	if(f[k])
	for(int i=0;i<n;i++)
	if((1<<i)&k)
	for(int j=0;j<n;j++)
	if(i!=j&&(1<<j)&k){
		cnt=cal(k);
		if(cnt>1) f[k^(1<<j)]+=f[k]*2*a[i][j]/cnt/(cnt-1);
	}
	for(int i=0;i<n;i++)
	printf("%.6lf ",f[1<<i]);
	return 0;
}