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 点确定下一个点走哪个点时，其概率都可以累加到没有走到其他点的概率上。
数组开不下用滚动。
1 #include2 #include 3 4 int head[55],nxt[2550],point[2550],size; 5 int num[55]; 6 double a[2][55][55],ans[55]; 7 //int ma[55][55] 8 9 void add(int a,int b){10 point[size]=b;11 nxt[size]=head[a];12 head[a]=size++;13 num[a]++;14 point[size]=a;15 nxt[size]=head[b];16 head[b]=size++;17 num[b]++;18 }19 20 int main(){21 int T;22 scanf("%d",&T);23 while(T--){24 int n,m,d;25 scanf("%d%d%d",&n,&m,&d);26 memset(head,-1,sizeof(head));27 size=0;28 memset(num,0,sizeof(num));29 while(m--){30 int u,v;31 scanf("%d%d",&u,&v);32 add(u,v);33 // ma[u][v]=ma[v][u]=1;34 }35 for(int i=1;i<=n;++i){36 for(int j=1;j<=n;++j){37 if(i!=j)a[0][i][j]=1.0/n;38 else a[0][i][j]=0;39 }40 }41 int o=0;42 // if(d>1000)d=1000;43 for(int i=1;i<=d;++i){44 memset(a[o^1],0,sizeof(a[o^1]));45 for(int j=1;j<=n;++j){46 for(int u=head[j];~u;u=nxt[u]){47 int v=point[u];48 for(int k=1;k<=n;++k){49 if(j!=k)a[o^1][j][k]+=a[o][v][k]/num[v];50 }51 }52 }53 o^=1;54 }55 for(int i=1;i<=n;++i){56 ans[i]=0;57 for(int j=1;j<=n;++j)ans[i]+=a[o][j][i];58 }59 for(int i=1;i<=n;++i)printf("%.10lf\n",ans[i]);60 }61 return 0;62 }