题解 CF16E 【Fish】
xukuan
2020-10-02 18:18:00
概率期望dp的状态一般设置成：当前状态为i，到最终状态的期望或概率
一看数据范围，$1 \leq n \leq 18$，果断状压
用$f_i$表示当前状态为i，到只剩一条鱼的概率
我们看i吃j的概率是多少：
1. i和j都在鱼群里
2. i遇上了j（估计很多人会漏掉这个问题）
3. i吃掉了j
所以概率是$\frac{1}{\frac{1}{2}count(s)count(s-1)}*a_{i,j}$
直接上代码。
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=20;
ll n;
double a[N][N],f[1<<N];
inline ll lowbit(ll x){
return x&(-x);
}
inline ll count(ll x){
ll ans=0;
for(ll i=x; i; i-=lowbit(i)) ans++;
return ans;
}
int main(){
scanf("%lld",&n);
for(ll i=0; i<n; i++){
for(ll j=0; j<n; j++) scanf("%lf",&a[i][j]);
}
f[(1<<n)-1]=1;
for(ll i=(1<<n)-1; i; i--){
ll sum=count(i);
for(ll j=0; j<n; j++){
if(i&(1<<j)){
for(ll k=0; k<n; k++){
if(i==j) continue;
if(i&(1<<k)) f[i-(1<<j)]+=f[i]*(2.0/sum/(sum-1))*a[k][j];
}
}
}
}
for(ll i=0; i<n; i++) printf("%.6lf ",f[1<<i]);
return 0;
}
```