hdu7016 / 2021“MINIEYE杯”中國大學生算法設計超級聯賽（5）1005 Random Walk 2（高斯消元）

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

把下頭換成三目運算符就跑得飛快

#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' : ' ');
            }
        }
    }
}      

作者：xxy