Problem F CodeForces 16E

343 阅读 0 评论 227 点赞

我是靠谱客的博主凶狠狗，最近开发中收集的这篇文章主要介绍Problem F CodeForces 16E，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

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 a_ij, and the second will eat up the first with the probability a_ji = 1 - a_ij. 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.

Input

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. a_ij (0 ≤ a_ij ≤ 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: a_ij = 1 - a_ji. All real numbers are given with not more than 6 characters after the decimal point.

Output

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.

Sample Input

Input

2
0 0.5
0.5 0

Output

0.500000 0.500000

Input

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

Output

1.000000 0.000000 0.000000 0.000000 0.000000 

解析：

status{x1,x2,x3,x4,………xn-1,xn}表示每只鱼是否还活着的状态

xi=1表示第i条鱼还活着

xi=0表示第i条鱼已经被吃掉了

dp(status)表示形成status这种状态的概率

那么刚开始的时候（第一天），所有的鱼都活着。

那么dp({1,1,1,1….,1,1,1})=1。

假设当前状态status活着的鱼有t条

此时，如果鱼j活着，鱼k也活着，那么j把k吃掉的概率是多少呢？

P(j吃掉k)=P(j,k相遇)*P(相遇时j可以吃掉k)=1/C(t,2)*P(相遇时j可以吃掉k)

dp(newstatus) += P(j吃掉k)*dp(status)

newstatus:j吃掉k之后的新状态

#include <iostream>
#include <stdio.h>
using namespace std;
double prob[18][18];
double dp[1<<18];

int getFish(int status)//获得该数字表示的鱼的数目
{
    int fish = 0;
    while(status!=0)
    {
        fish += status&1;
        status = status>>1;
    }
    return fish;
}

int main()
{
    int n;
    cin.sync_with_stdio(false);
    cin>>n;
    for(int i =0;i<n;i++)
    {
        for(int j =0;j<n;j++)
        {
            cin>>prob[i][j];
        }
    }
    dp[(1<<n)-1]=1;
    for(int i=(1<<n)-1;i>=1;i--)
    {
        int fish = getFish(i);
        if(fish==1)//鱼为1结束
            continue;
        double choose = 2*dp[i]/fish/(fish-1);//被选中的概率
        for(int j = 0;j < n;j++)//对于i状态而言
            if(i&(1<<j))//每一位判断，如果鱼j被吃掉
            {
                for(int k = 0;k < n;k++)
                    if(i&(1<<k))
                    {
                        dp[i^(1<<k)] += choose*prob[j][k];//吃掉之后新的状态的概率
                    }
            }
    }
    for(int i =0;i<n;i++)
    {
        printf("%.6f ",dp[1<<i])//最后剩下的情况;
    }
    return 0;

}