E. Fish+状态压缩dp+codeforces

263 阅读 0 评论 174 点赞

我是靠谱客的博主甜甜哈密瓜，最近开发中收集的这篇文章主要介绍E. Fish+状态压缩dp+codeforces，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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 probabilitya_ij, and the second will eat up the first with the probabilitya_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 follown lines with n real numbers each — matrixa. a_ij (0 ≤ a_ij ≤ 1) — the probability that fish with indexi 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 indexi should be equal to the probability that fish with indexi will survive to be the last in the lake.

Sample test(s)

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

解决方案：状态压缩dp。可用二进制来枚举鱼的存活，1表示活，0表示死。dp[1111..00]，表示出现某些鱼活，某些鱼死的概率。则dp[j被吃后的状态]=dp[j被吃前的状态]*p*mat[i][j]，p为两鱼相遇的概率；p=C（2，m）m为剩余的个数。最后可得出每条鱼的存活率。

code：#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int s=1<<19;
double dp[s];
double mat[20][20];
int n;
int bit_count(int x){
    int sum=0;
    while(x){
        sum+=x&1;
        x=x>>1;
    }
    return sum;
}
int main()
{
    while(~scanf("%d",&n)){
       // cout<<bit_count(n)<<endl;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                scanf("%lf",&mat[i][j]);
            }
        }
        dp[(1<<n)-1]=1;
        for(int i=(1<<n)-1;i>=1;i--){
            int cnt=bit_count(i);
            if(cnt==1) continue;
           // cout<<i<<cnt<<endl;
            double p=2*dp[i]/(cnt*(cnt-1));
         // cout<<p<<endl;
            for(int l=0;l<n;l++)if(i&(1<<l)){
                for(int k=0;k<n;k++)if(i&(1<<k)){
                    dp[i^(1<<k)]+=p*mat[l][k];
                }
            }
        }
        for(int i=0;i<n;i++){
            printf("%.6f%c",dp[1<<i],i==n-1?'n':' ');
        }
    }
    return 0;
}