SRM 620 div2 1000

给n个点(0, 1, 2, ..., n-1), 每对点之间有边的概率是p/1000, 每对点之间至多一条边
求图中有>=4个点的连通组件的概率

这题想了一天, 又向题解屈服了QAQ..
题解中结合了动态规划和对立事件..
想到了用动态规划来解, 但是状态很简单..
D[i], i个节点组成的图满足题意的概率..
那么递推公式就是D[i+1]=D[i]*P..P不知道如何计算..
也想到了对立事件, 即求图中仅有<4个点组件的概率P`, 那么答案就是1-P`..
但是没有结合二者深入思考..弱!..

观察1
..:
<4个点的组件只有四种形式..
O
O-O
O-O-O
O---O
 \ /
  O
..:
当要加入一个新节点, 会产生以下变化..
O     -> O-O
O-O   -> O-O-O or O---O
                   \ /
                    O
O-O-O -> O-O-O-O or O-O---O or ...
                       \ /
                        O
O---O -> ...
 \ /
  O
..:
观察发现..变化的是组成连通组件的点个数, 所以我们按节点个数来建立状态..

观察2
..:
D[a][b][c]
当前图中有a个1节点组件, b个2节点组件, c个3节点组件的概率..
f(r, a, b, c)
递归函数, 还要加入r个点, 状态是D[a][b][c]的概率..
f(n, 0, 0, 0)
我们的问题啦..
f(0, a, b, c)=1.0
终止条件, 这时候整个图就是a+b+c, 只有<4个点的组件..
递归函数详见题解>.<..

写出代码
..:

#include <bits/stdc++.h>
using namespace std;

bool   v[51][51][51];
double d[51][51][51];
double p;
inline double D(int R, int a, int b, int c) {
#define X 1-p
#define O p
    if (!v[a][b][c]) {
        v[a][b][c]=1;
        double r=.0;
        if (!R) {
            r=1.0;
        } else {
         r+=pow(X, a+2*b+3*c)*D(R-1, a+1, b, c);
         if (a>0) r+=pow(X, 2*b+3*c)*a*O*pow(X, a-1)*D(R-1, a-1, b+1, c);
         if (a>1) r+=pow(X, 2*b+3*c)*a*(a-1)/2*O*O*pow(X, a-2)*D(R-1, a-2, b, c+1);
         if (b>0) r+=pow(X, a+3*c)*2*b*O*pow(X, 2*b-1)*D(R-1, a, b-1, c+1),
                  r+=pow(X, a+3*c)*b*O*O*pow(X, 2*b-2)*D(R-1, a, b-1, c+1);
        }
        d[a][b][c]=r;
    }
    return d[a][b][c];
#undef X
#undef O
}
class RandomGraph {
public:
    double probability(int n, int p) {
        ::p=p/1000.0;
        return 1-D(n, 0, 0, 0);
    }
};