题目地址：Codeforces：Problem – 16E – Codeforces、洛谷：【CF16E】Fish – 洛谷

题目描述

n fish, numbered from 1 to n, live in a lake. Every day right one pair of fish meet, and the probability of each other pair meeting is the same. If two fish with indexes i and j meet, the first will eat up the second with the probability aij, and the second will eat up the first with the probability aji = 1 - aij. The described process goes on until there are at least two fish in the lake. For each fish find out the probability that it will survive to be the last in the lake.
有n条鱼，每天每对鱼等可能相遇，每条鱼把其他鱼吃掉有一个概率，保证输赢概率和为1，求最后只剩某条鱼的概率。

输入输出格式

输入格式：
The first line contains integer n (1 ≤ n ≤ 18) — the amount of fish in the lake. Then there follow n lines with n real numbers each — matrix a. aij (0 ≤ aij ≤ 1) — the probability that fish with index i eats up fish with index j. It’s guaranteed that the main diagonal contains zeros only, and for other elements the following is true: aij = 1 - aji. All real numbers are given with not more than 6 characters after the decimal point.

输出格式：
Output n space-separated real numbers accurate to not less than 6 decimal places. Number with index i should be equal to the probability that fish with index i will survive to be the last in the lake.

输入输出样例

输入样例#1：

2
0 0.5
0.5 0

输出样例#1：

0.500000 0.500000 

输入样例#2：

5
0 1 1 1 1
0 0 0.5 0.5 0.5
0 0.5 0 0.5 0.5
0 0.5 0.5 0 0.5
0 0.5 0.5 0.5 0

输出样例#2：

1.000000 0.000000 0.000000 0.000000 0.000000 

题解

n的范围适合状压，我们考虑状压解决。我们知道，枚举一对鱼的情况，可以完成概率的DP转移，如下：
dp[S] = \sum_{i=1, i \in S}^n \sum_{j=1, j \notin S}^n dp[S \cap {j}] \times \mathrm{P}(i \ \text{meets} \ j) \times \mathrm{P}(i \ \text{eats} \ j)
我们知道，对于每对鱼相遇是等可能的，因此有
\mathrm{P}(i \ \text{meets} \ j) = \frac{1}{\mathrm{C}_{cnt[S] + 1}^2} = \frac{2}{cnt[S] (cnt[S] + 1)}
这里的cnt数组表示S集合里有多少元素。

代码

// Code by KSkun, 2018/3
#include <cstdio>

const int MAXN = 20;

int n;
double p[MAXN][MAXN], dp[1 << MAXN], cnt[1 << MAXN];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            scanf("%lf", &p[i][j]);
        }
    }
    for(int i = 0; i < (1 << n); i++) {
        cnt[i] = cnt[i >> 1] + (i & 1);
    }
    dp[(1 << n) - 1] = 1;
    for(int s = (1 << n) - 1; s; s--) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == j) continue;
                if((s & (1 << (i - 1))) && (s & (1 << (j - 1)))) {
                    dp[s ^ (1 << (j - 1))] += dp[s] * p[i][j] / (cnt[s] * (cnt[s] - 1) / 2);
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        printf("%.10lf ", dp[1 << (i - 1)]);
    }
    return 0;
}