T19:Fish

1）题目意思

湖里有 n 条鱼。每天随机等概率选出一对鱼相遇（所有鱼对概率一样）。相遇后两条鱼必有一条被吃掉：

• 鱼 i 吃掉鱼 j 的概率是 a[i][j]
• 鱼 j 吃掉鱼 i 的概率是 a[j][i] = 1 - a[i][j]

一直重复，直到只剩 1 条鱼。要求输出每条鱼成为“最后幸存者”的概率，输出保留 6 位小数（题面说 6 位），每个概率之间空格分隔。

n <= 18，a[i][j] 是小数。

---

2）思路解析（状态压缩 DP，倒推集合概率）

关键观察

过程只会减少鱼的数量，不会增加，所以可以用“还活着的鱼集合”作为状态。

用 mask 表示当前还活着的鱼集合：

• mask 的第 i 位为 1 表示鱼 i 还活着（用 0..n-1 表示编号 1..n）

定义：

• dp[mask] 表示“某一时刻活着的鱼集合恰好是 mask 的概率”（从开始状态一路演化到这个状态的概率）

开始时所有鱼都活着：

• FULL = (1<<n) - 1
• dp[FULL] = 1

我们从“大集合”往“小集合”转移。因为一次相遇会死一条鱼，所以 mask 会去掉一个 bit。

转移怎么计算

在状态 mask 下，设当前活着的鱼数量为 k。每天等概率选一对活鱼相遇，鱼对数量是：

• pairs = k*(k-1)/2

从 mask 转移到 mask2 = mask without j（表示鱼 j 被吃掉），需要考虑：在 mask 中谁会吃掉 j。

如果 i 和 j 相遇，并且 i 吃掉 j，就会进入 mask2。所以从 mask 到 mask2 的概率增量为：

• 在所有鱼对中选到 (i,j) 的概率是 1/pairs
• 在选到 (i,j) 后，j 被吃掉的概率是 a[i][j]

因此：

• dp[mask2] += dp[mask] * ( sum over i in mask, i!=j of a[i][j] ) / pairs

这样我们枚举 mask，再枚举要死掉的鱼 j，把概率分给更小的集合。

最终答案

当只剩一条鱼 i 时，集合就是 mask = (1<<i)，它的概率 dp[1<<i] 就是鱼 i 成为最后幸存者的概率。

---

3）代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN=18;                                           // n 最大 18
static long double a[MAXN][MAXN];                            // a[i][j]：i 吃 j 的概率
static long double dp[1<<MAXN];                              // dp[mask]：活鱼集合为 mask 的概率

int main(){                                                  // 主函数入口
    ios::sync_with_stdio(false);                             // 加速输入输出
    cin.tie(nullptr);                                        // 加速输入输出

    int n;                                                   // 鱼的数量
    cin>>n;                                                  // 读入 n

    for(int i=0;i<n;i++){                                    // 读入矩阵 a
        for(int j=0;j<n;j++){                                // 读入矩阵 a
            double x;                                        // 用 double 读入更方便
            cin>>x;                                          // 读入 a[i][j]
            a[i][j]=(long double)x;                          // 转成 long double 保存提高精度
        }
    }

    int FULL=(1<<n)-1;                                       // FULL 表示所有鱼都活着的集合
    for(int mask=0;mask<=FULL;mask++){                       // 初始化 dp
        dp[mask]=0.0L;                                       // 初始概率设为 0
    }
    dp[FULL]=1.0L;                                           // 初始状态：所有鱼都活着，概率为 1

    for(int mask=FULL;mask>=1;mask--){                       // 从大集合往小集合枚举状态
        int k=__builtin_popcount((unsigned)mask);            // k 表示当前活鱼数量
        if(k<=1)continue;                                    // 只剩 0 或 1 条鱼就无法继续转移

        long double pairs=(long double)k*(k-1)/2.0L;         // 当前状态下活鱼对的数量
        long double curp=dp[mask];                           // 当前集合出现的概率
        if(curp==0.0L)continue;                              // 概率为 0 则跳过

        for(int j=0;j<n;j++){                                // 枚举将要被吃掉的鱼 j
            if(!(mask&(1<<j)))continue;                      // j 不在集合里说明已死，跳过

            long double kill=0.0L;                           // kill 累加“j 被吃掉”的总概率贡献
            for(int i=0;i<n;i++){                            // 枚举可能吃掉 j 的鱼 i
                if(i==j)continue;                            // i 和 j 不能相同
                if(!(mask&(1<<i)))continue;                  // i 不在集合里说明已死，跳过
                kill+=a[i][j];                               // 若 i 与 j 相遇，i 吃 j 的概率为 a[i][j]
            }

            int nmask=mask^(1<<j);                           // 去掉 j 后的新集合 nmask
            dp[nmask]+=curp*kill/pairs;                      // 把概率从 mask 分配到 nmask
        }
    }

    cout.setf(ios::fixed);                                   // 固定小数输出格式
    cout<<setprecision(6);                                   // 按题目要求输出 6 位小数

    for(int i=0;i<n;i++){                                    // 输出每条鱼成为最后一条鱼的概率
        cout<<(double)dp[1<<i]<<" ";                         // dp[1<<i] 就是只剩 i 的概率
    }
    cout<<endl;                                              // 换行输出结束
    return 0;                                                // 程序结束
}