给你一个连通的无向图，等概率随机选取一个起点，走d步，每一步等概率走到相邻的点。问走完d步之后，每个点没有被经过的概率。
推状态的关键当然就是对这个“从任意起点走完d步点node没被经过的概率”的理解了，转一下方向，这句话的意思其实等价于“我避开点node走d步到达其它点的概率之和”；
设状态方程p[node][d][i]为避开node走d步到达i点的概率，那么Σp[node][n][i],(i=1~n)即“从任意起点走完d步点node没被经过的概率”
初始时每个点的状态相当于走0步到达该点的状态，即p[node][0][i] = 1.0/n，（i != node）；
之后，走d步到达i点的概率等价于走d-1步到达与i邻接的点g[i][j]的概率和，（g[i][j] != node）;
根据以上分析求解就很容易了。因为是分别求点所以可以把数组第一维省略掉节省内存。
主要代码：
void dp()
{
for(int i = ; i <= n; i++) p[][i] = 1.0/n;
for(int node = ; node <= n; node++)
{
for(int d = ; d <= k; d++)
for(int i = ; i <= n; i++)
p[d][i] = ; for(int d = ; d <= k; d++)
for(int i = ; i <= n; i++)
{
if(i == node) continue ;
double sum = 0.0;
int sz = g[i].size();
if(sz == ) continue;
for(int j = ; j < g[i].size(); j++)
{
if(g[i][j] == node) { continue ;}
sum += p[d-][g[i][j]];
}
p[d][i] = sum/(sz);
}
double ans = 0.0;
for(int i = ; i <= n; i++)
{
ans += p[k][i];
}
printf("%.10lf\n", ans);
}
}
hdu 5001