【概率dp】vijos 3747 随机图

题目描述

在一张图内，两点$i,j$之间有$p$的概率的概率生成一条边。求该图不出现大小$\ge 4$连通块的概率。

$n \le 100,答案在实数意义下$

---

题目分析

首先应当想到的是枚举连通块大小为$1,2,3$的点数。

有一种想法是枚举出三种点个数之后组合算出这种情况下的方案数。但是这个方案数会非常大，不取模则不现实。

于是应当dp地来看这个问题，考虑每次加一个点后概率是如何变化的。于是只需要分类讨论一下5种情况就好了。

重点在于用dp的视角看待这个问题

 #include<bits/stdc++.h>

 int n;

 double p,q,ans,f[][][];

 double qmi(double a, int b)

 {

     double ret = ;

     for (; b; b>>=,a=a*a)

         if (b&) ret *= a;

     return ret;

 }

 int main()

 {

     scanf("%d%lf",&n,&p);

     q = (1000.0-p)/1000.0, p /= 1000.0;

     f[][][] = ;

     for (int ix=,i,j,k; ix<=n; ix++)

         for (int jx=; jx<=ix; jx++)

             for (int kx=; kx+jx<=ix; kx+=)

                 if ((ix-jx-kx)%==){

                     i = jx, j = kx, k = ix-jx-kx;

                     if (i) f[i][j][k] += qmi(q, ix-)*f[i-][j][k];

                     if (j) f[i][j][k] += qmi(q, ix-)*p*(i+1.0)*f[i+][j-][k];

                     if (k){

                         f[i][j][k] += qmi(q, ix-)*p*(j+2.0)*f[i][j+][k-]+qmi(q, ix-)*p*p*(j/+)*f[i][j+][k-]+qmi(q, ix-)*p*p*(i+2.0)*(i+1.0)/2.0*f[i+][j][k-];

                     }

                 }

     for (int i=; i<=n; i++)

         for (int j=; i+j<=n; j+=)

             if ((n-i-j)%==)

                 ans += f[i][j][n-i-j];

     printf("%.4lf\n",1.0-ans);

     return ;

 }

END