蒜头君王国 概率计算(dp)"/>

计蒜客 A1596.蒜头君王国 概率计算(dp)

题目描述

原题链接

有一天，蒜头君当上了国王。蒜头君的王国有 n n n 坐城市，现在他需要在城市之间修建道路使得城市之间相互联通。
蒜头君是一个不会规划的人，他不知道哪些城市之间必须要有道路，所以对于任意两座城市之间，蒜头军会修建道路的概率为 p p p。
请你计算一下最后修建出来的道路使得 n n n 座城市都联通的概率。

输入格式

输入包含一个整数 n ( 1 ≤ n ≤ 20 ) n(1≤n≤20) n(1≤n≤20) 和一个实数 p ( 0 ≤ p ≤ 1 ) p(0≤p≤1) p(0≤p≤1).

输出格式

输出一行一个实数表示答案，输出结果误差在 1 0 − 5 10^{−5} 10−5 以内都认为正确。

输入样例

3 0.6

输出样例

0.6480000

分析

参考大佬的题解
题目让求 n n n个点都联通的概率 F ( n ) F(n) F(n)。不妨先求一下 n n n个点组成的图不连通的概率 G ( n ) G(n) G(n)
考虑n个点组成的图不连通有以下 n − 1 n-1 n−1中情况:
1 1 1个点连通, 且这 1 1 1个点组成的连通块, 与其余 n − 1 n-1 n−1个点没有边相连
2 2 2个点连通, 且这 2 2 2个点组成的连通块, 与其余 n − 2 n-2 n−2个点没有边相连
…
k k k个点连通, 且这 k k k个点组成的连通块, 与其余 n − k n-k n−k个点没有边相连
…
n − 1 n-1 n−1个点连通, 且这 n − 1 n-1 n−1个点组成的连通块, 与剩余的 1 1 1个点没有边相连


考虑有 k k k个点连通的情况:
首先要选 k k k个点, 而第 n n n个点一定选,则再从 n − 1 n-1 n−1个点中选择 k − 1 k-1 k−1个, 即 C n − 1 k − 1 C_{n-1}^{k-1} Cn−1k−1​
然后保证这 k k k个点连通, 即 F ( k ) F(k) F(k)
最后保证这 k k k的点与其余 n − k n-k n−k个点没有边相连, 即 ( 1 − p ) k ( n − k ) (1-p)^{k(n-k)} (1−p)k(n−k) ( p p p为两点间修路的概率)
从而根据上述 n − 1 n-1 n−1种情况求出 G ( n ) G(n) G(n), 则 题目所求 F ( n ) = 1 − G ( n ) F(n) = 1-G(n) F(n)=1−G(n)

实现

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const int N = 29;
int n;
double p;
double f[N]; // f[i]表示n个点都联通的概率
int c(int a, int b) // 计算组合数 C(a,b), 即从a个点中选b个点
{int sum = 1;for(int i=1; i<=b; i++) sum = sum*(a-b+i)/i;return sum;
}
int main()
{cin >> n >> p;f[1] = 1, f[2] = p; // 易知: 1个点联通的概率为1, 2个点联通概率为p;for(int i=3; i<=n; i++){double fail = 0; // 表示i个点不联通的概率for(int j=1; j<=i-1; j++){fail += ( c(i-1, j-1)*f[j]*pow(1.0-p,j*(i-j)) );}f[i] = 1.0-fail;}printf("%.7lf",f[n]);return 0;
}

关于上述实现中组合数 C n m C_n^m Cnm​的计算