CodeForces 16E Fish

题意

有n条鱼，他们相遇时会吃掉对方；
给出他们相遇时双方获胜的概率，直到只剩下一条鱼为止；
求：每条鱼活到最后的概率

题解

[状压DP + 概率 DP]
状态表示：
    n 位 二进制表示 第 i 条是否死掉(为 1 表示 死掉)
属性：
    sum
集合划分：
    state --> state' = state | (1 << i) 
    	边权: 其他活着的鱼干掉第i条鱼的概率
==> dp[state'] += dp[state] * getP(state, j)
        state' = state|(1<<i)  
        【表示在死掉的鱼的状态集合为 state 的基础在死第 i 条鱼的概率】
初始状态：
    dp[0] = 1.00
目标状态：
    ans[i] = dp[((1<<n)-1) ^ (1 << i)]
    11111 ^ 10000 = 01111 (其他鱼全死)

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define read(a) scanf("%d", &a)
#define readl(a) scanf("%lld", &a)
#define readf(a) scanf("%lf", &a)
#define readc(a) scanf("%c", &a)
#define reads(a) scanf("%s", a)
#define Buff ios::sync_with_stdio(false)
#define mem(a) memset(a, 0, sizeof a)
#define pb push_back
const int INF = 1e9 + 7;
const int N = 20;
const int M = 1e6 + 7;
const ll mod = 1e9 + 7;
double p[N][N], dp[1 << N];
int n;
double getP(int x, int j) // 被吃掉的总概率
{
    int cnt0 = 0;
    double res = 0.00;
    for(int i = 0; i < n; i++)
        if(!(x & (1 << i)))
        {
            cnt0++;
            res += p[i][j];
        }    
    double tmp = (cnt0*1.00) * (cnt0 - 1.00) / 2.00; 
    return res / tmp;
}
signed main()
{
    Buff;
    cin >> n;
    int states = (1 << n) - 1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)  
            cin >> p[i][j];

    dp[0] = 1.00;
    for(int i = 0; i < states; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(!(i & (1 << j)))
            {
                int u = i | (1 << j);
                double pp = getP(i, j);
                dp[u] += dp[i] * pp;
            }
        }
    }

    for(int i = 0; i < n; i++)
        printf("%.6f ", dp[states^(1<<i)]);

    return 0;
}
/**
wa1:
    概率算错了一发
**/