有向图（概率期望+同余高斯消元）

有向图

题意：

意思是当Bobo位于 $n+1,n+2,...,n+m$n+1,n+2,...,n+m节点后就不会移动了，求Bobo从节点 $1$1开始经过无穷时间后Bobo停在这 $m$m个点的概率分别是多少

思路：

1. 这个问题告诉要我们求Bobo开始在节点 $1$1处的答案，我们可以先求解一个子问题的答案，就是Bobo最终停在 $n+1$n+1处的概率
2. 对于这个子问题，要是我们知道Bobo从其他点开始，最终停在 $n+1$n+1处的概率就好了。虽然我们不知道这些概率具体是多少，但是可以将它们设出来，这样就可以建立 $n\ast n$n∗n的系数矩阵，外加一行的增广，这样就可以利用高斯消元求解出开始位于第 $i$i个点，最终停在第 $n+1$n+1个点的概率了。
3. 而这个系数矩阵如何建立呢？考虑：
   $a\left[i\right][n+1]=p\left[i\right][n+1]+{\sum }_{i=1}^n\left(p\right[i\left]\right[j]\ast a[i\left]\right[n+1\left]\right)$a[i][n+1]=p[i][n+1]+∑i=1n​(p[i][j]∗a[i][n+1])
   只需要对上面这个式子进行简单的移项就可以得到一个增广矩阵啦！
4. 这样，对于这 $m$m个结束位置我们都可以建立这样一个 $n\ast (n+1)$n∗(n+1)的增广矩阵，并且进行高斯消元，得到答案。但很不幸的是，我第一发TLE了。
5. 来分析一下复杂度，高斯消元 $O\left(n^3\right)$O(n3)， $m$m个最终位置 $O\left(m\right)$O(m)， $T$T组数据 $O\left(T\right)$O(T)；因此复杂度就是 $O(T\ast m\ast n^3)$O(T∗m∗n3)。显然我们需要去掉一个 $m$m或者 $n$n。
6. 仔细观察这 $m$m个增广矩阵，可以发现，它们的系数矩阵是一样的！！！并且高斯消元的过程中，具体如何消元跟常数列无关，只与系数矩阵有关，因此我们考虑将这 $m$m个增广矩阵合并，变成一个 $n\ast (n+m)$n∗(n+m)且保证有唯一解的增广矩阵。这样，最终复杂度降为 $O(T\ast (n+m)\ast n^2)$O(T∗(n+m)∗n2)，应该是正解啦。

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e3+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;
 
int n, m;
ll invw;
ll a[maxn][maxn];
ll p[maxn][maxn];
 
ll fast(int a, int k) {
    ll ans=1, p=a;
    while(k) {
        if(k&1) ans=ans*p%mod;
        p=p*p%mod;
        k>>=1;
    }
    return ans;
}
 
ll inv(int a) { return fast(a,mod-2); }
 
void Gauss() {
    for(int i=1; i<=n; ++i) {
        int mr=i;
        for(int j=i+1; j<=n; ++j) if(a[j][i]>a[mr][i]) mr=j;
        swap(a[i],a[mr]);
        for(int j=1; j<=n; ++j) {
            if(j==i) continue;
            ll d=a[j][i]*inv(a[i][i])%mod;
            for(int k=i; k<=n+m; ++k) a[j][k]=(a[j][k]-d*a[i][k]%mod+mod)%mod;
        }
        for(int k=i+1; k<=n+m; ++k) a[i][k]=a[i][k]*inv(a[i][i])%mod; a[i][i]=1;
    }
}
 
int main(){
    invw=inv(10000);
    while(cin>>n>>m) {
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n+m; ++j) scanf("%lld", &p[i][j]);
        for(int i=1; i<=n; ++i) {
            for(int k=1; k<=n; ++k) {
                a[i][k]=p[i][k]*invw%mod;
                if(i==k) a[i][k]=(a[i][k]-1+mod)%mod;
            }
            for(int j=1; j<=m; ++j) a[i][n+j]=(mod-p[i][j+n])*invw%mod;
        }
        Gauss();
        for(int i=1; i<=m; ++i) printf("%lld%c", a[1][n+i], " \n"[i==m]);
    }
}