https://acm.hdu.edu.cn/showproblem.php?pid=7016
题意：
n个点的有向完全图，在图上游走
每次以p[i][j]的概率从i走向j
如果某次在原地没有动，那么游走结束
对所有i j回答起点在i，游走到j结束的概率
设起点在s
用常见的解决图上随机游走问题的方法
设f[j]表示从起点走到j，还能继续走下去的概率
f[j]=∑ f[k]*p[k][j] (k≠j) + p[s][j] (s≠j)
k相当于是枚举走到j的前一步，k不能等于j，因为要可以继续走下去
后面的p[s][j]是没有前一步，j就是第一步，直接s到j，同理不能原地踏步
a[j]表示从起点走到j，游走结束的概率
a[j]=f[j]*p[j][j] + p[j][j] (s=j)
后面的p[j][j]是从起点走了一步就走不下去的概率
然后用高斯消元可以O(n^3)求出f，进而求出a
但这是一个起点，再枚举起点就是O(n^4)了
我们发现当终点相同时，f的式子只有最后面的常数项p不一项
也就是说对于所有的f[i][j]，i∈[i,n]，j相同（不同起点同终点），高斯消元的系数矩阵是一样的，增广矩阵只有最后一列是不同的
那么我们可以把所有增广矩阵的最后一列放到一起，变成n*2n的增广矩阵
这样解出来的增广矩阵第i行第n+j列就是以f[j][i]
hdu不知道为啥
f[j][k]-=t*f[i][k]%mod; if(f[j][k]<0) f[j][k]+=mod;
这样写一直TLE
把下头换成三目运算符就跑得飞快
f[i][k]=f[i][k]<0 ? f[i][k]+mod : f[i][k];
#include<bits/stdc++.h> using namespace std; #define N 302 #define mod 998244353 int n,m; int w[N][N],p[N][N]; typedef long long LL; LL f[N][N<<1]; inline LL poww(LL a,LL b) { LL c=1; for(;b;a=a*a%mod,b>>=1) if(b&1) c=c*a%mod; return c; } inline void gauss() { int r; LL inv,t; for(int i=1;i<=n;++i) { r=i; while(r<=n && !f[r][i]) ++r; if(r>n) continue; if(r!=i) swap(f[i],f[r]); inv=poww(f[i][i],mod-2); for(int j=i;j<=m;++j) f[i][j]=f[i][j]*inv%mod; for(int j=i+1;j<=n;++j) { t=f[j][i]; for(int k=i;k<=m;++k) { f[j][k]-=t*f[i][k]%mod; //if(f[j][k]<0) f[j][k]+=mod; f[j][k]=f[j][k]<0 ? f[j][k]+mod : f[j][k]; } } } for(int i=n;i;--i) for(int k=n+1;k<=m;++k) { for(int j=i+1;j<=n;++j) { f[i][k]-=f[i][j]*f[j][k]%mod; f[i][k]=f[i][k]<0 ? f[i][k]+mod : f[i][k]; } } } int main() { int T,sum,ans; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&w[i][j]); for(int i=1;i<=n;++i) { sum=0; for(int j=1;j<=n;++j) sum+=w[i][j]; sum=poww(sum,mod-2); for(int j=1;j<=n;++j) p[i][j]=1ll*w[i][j]*sum%mod; } for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) if(j!=i) f[i][j]=mod-p[j][i]; f[i][i]=1; for(int j=1;j<=n;++j) if(i!=j) f[i][n+j]=p[j][i]; f[i][n+i]=0; } m=n<<1; gauss(); for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { ans=f[j][n+i]*p[j][j]%mod; if(i==j) ans=(ans+p[j][j])%mod; printf("%d%c",ans,j==n ? ‘\n‘ : ‘ ‘); } } } }
hdu7016 / 2021“MINIEYE杯”中国大学生算法设计超级联赛（5）1005 Random Walk 2（高斯消元）