Codeforces 16E Fish(상압 dp+ 확률)

코드

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <list>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define LL long long
#define lowbit(x) ((x)&(-x))
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1|1
#define MP(a, b) make_pair(a, b)
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int maxn = 1e5 + 10;
const double eps = 1e-8;
const double PI = acos(-1.0);
typedef pair<int, int> pii;
double dp[1<<19];
double p[20][20];


int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> p[i][j];
    dp[(1 << n) - 1] = 1.0;
    for (int s = (1 << n) - 1; s > 0; s--)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if ((s & (1 << i)) && (s & (1 << j)))
                {
                    if (i == j) continue;
                    int num = __builtin_popcount(s);
                    dp[s ^ (1 << j)] += dp[s] * p[i][j] / (num * (num - 1) / 2);
                }
    for (int i = 0; i < n; i++)
        printf("%.6f ", dp[1<<i]);
    return 0;
}