I used to think I could be anything, but now I know that I couldn't do anything. So I started traveling.
The nation looks like a connected bidirectional graph, and I am randomly walking on it. It means when I am at node i, I will travel to an adjacent node with the same probability in the next step. I will pick up the start node randomly (each node in the graph has the same probability.), and travel for d steps, noting that I may go through some nodes multiple times.
If I miss some sights at a node, it will make me unhappy. So I wonder for each node, what is the probability that my path doesn't contain it.
题意：有一张双连通图，有个人在图上等概率随机选择起点，每一步等概率随机选择下一个走的点，一共走 d 步，问每个点没有被走到的概率是多少。
组数20，点数50，边数2450，总步数10000，暴力更新复杂度 20 × 50 × 2450 × 10000，重点：时限15秒！
随便暴……
dp [ i ] [ j ] [ k ] 表示当前第 i 轮，正位于 j 点，途中没有经过 k 点的概率总和。
每一轮在 j 点确定下一个点走哪个点时，其概率都可以累加到没有走到其他点的概率上。
数组开不下用滚动。
#include<stdio.h>
#include<string.h> int head[],nxt[],point[],size;
int num[];
double a[][][],ans[];
//int ma[55][55] void add(int a,int b){
point[size]=b;
nxt[size]=head[a];
head[a]=size++;
num[a]++;
point[size]=a;
nxt[size]=head[b];
head[b]=size++;
num[b]++;
} int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m,d;
scanf("%d%d%d",&n,&m,&d);
memset(head,-,sizeof(head));
size=;
memset(num,,sizeof(num));
while(m--){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
// ma[u][v]=ma[v][u]=1;
}
for(int i=;i<=n;++i){
for(int j=;j<=n;++j){
if(i!=j)a[][i][j]=1.0/n;
else a[][i][j]=;
}
}
int o=;
// if(d>1000)d=1000;
for(int i=;i<=d;++i){
memset(a[o^],,sizeof(a[o^]));
for(int j=;j<=n;++j){
for(int u=head[j];~u;u=nxt[u]){
int v=point[u];
for(int k=;k<=n;++k){
if(j!=k)a[o^][j][k]+=a[o][v][k]/num[v];
}
}
}
o^=;
}
for(int i=;i<=n;++i){
ans[i]=;
for(int j=;j<=n;++j)ans[i]+=a[o][j][i];
}
for(int i=;i<=n;++i)printf("%.10lf\n",ans[i]);
}
return ;
}