Submission #1687763

---

Source Code Expand

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"
#include "random"

using namespace std;

const long long int MOD = 1000000007;
const long double EPS = 0.00000001;
const long double PI = 3.1415926535897932384626433;

long long int N, M, K, H, W, L, R;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> N;
	string s;
	cin >> s;
	long double p;
	long double a = 0;
	long double b = 0;
	bool flag = true;
	for (auto i : s) {
		if (i == '/') {
			flag = false;
		}
		else if (flag) {
			a *= 10;
			a += i - '0';
		}
		else {
			b *= 10;
			b += i - '0';
		}
	}
	p = a / b;
	vector<vector<int>>battle(N);
	vector<pair<int,int>>c_win(N);
	for (int i = 0; i < N; i++) {
		c_win[i].second = N - i;
		for (int j = 0; j < N; j++) {
			cin >> K;
			if (i != j) {
				battle[i].push_back(K);
			}
			if (K) {
				c_win[i].first++;
			}
		}
	}
	vector<int>order(N);
	sort(c_win.begin(), c_win.end());
	reverse(c_win.begin(), c_win.end());
	for (int i = 0; i < N; i++) {
		order[N - c_win[i].second] = i;
	}
	vector<vector<vector<long double>>>dp(N, vector<vector<long double>>(N + 1, vector<long double>(N + 1)));
	for (int i = 0; i < N; i++) {
		dp[i][0][0] = 1;
		for (int j = 1; j < N; j++) {
			for (int k = 0; k < j; k++) {
				if (battle[i][j - 1]) {
					dp[i][j][k] += dp[i][j - 1][k] * ((long double)1 - p);
					dp[i][j][k + 1] += dp[i][j - 1][k] * p;
				}
				else {
					dp[i][j][k + 1] += dp[i][j - 1][k] * ((long double)1 - p);
					dp[i][j][k] += dp[i][j - 1][k] * p;
				}
			}
		}
	}
	long double ans = 1;
	for (int i = 0; i < N; i++) {
		for (int j = i+1; j < N; j++) {
			int fst, snd;
			if (order[i] > order[j]) {
				fst = j;
				snd = i;
			}
			else {
				fst = i;
				snd = j;
			}
			long double box = 0;
			long double sum = 0;
			if (fst == i) {
				for (int k = 0; k < N; k++) {
					sum += dp[snd][N - 1][k];
					box += dp[fst][N - 1][k] * sum;
				}
			}
			else {
				for (int k = 0; k < N; k++) {
					box += dp[fst][N - 1][k] * sum;
					sum += dp[snd][N - 1][k];
				}
			}
			ans *= box;
		}
	}
	cout << setprecision(20) << ans << endl;
	return 0;
}

Submission Info

Judge Result