有向图
题意:
意思是当Bobo位于 n+1,n+2,...,n+m节点后就不会移动了,求Bobo从节点 1开始经过无穷时间后Bobo停在这 m个点的概率分别是多少
思路:
- 这个问题告诉要我们求Bobo开始在节点 1处的答案,我们可以先求解一个子问题的答案,就是Bobo最终停在 n+1处的概率
- 对于这个子问题,要是我们知道Bobo从其他点开始,最终停在 n+1处的概率就好了。虽然我们不知道这些概率具体是多少,但是可以将它们设出来,这样就可以建立 n∗n的系数矩阵,外加一行的增广,这样就可以利用高斯消元求解出开始位于第 i个点,最终停在第 n+1个点的概率了。
- 而这个系数矩阵如何建立呢?考虑:
a[i][n+1]=p[i][n+1]+∑i=1n(p[i][j]∗a[i][n+1])
只需要对上面这个式子进行简单的移项就可以得到一个增广矩阵啦! - 这样,对于这 m个结束位置我们都可以建立这样一个 n∗(n+1)的增广矩阵,并且进行高斯消元,得到答案。但很不幸的是,我第一发TLE了。
- 来分析一下复杂度,高斯消元 O(n3), m个最终位置 O(m), T组数据 O(T);因此复杂度就是 O(T∗m∗n3)。显然我们需要去掉一个 m或者 n。
- 仔细观察这 m个增广矩阵,可以发现,它们的系数矩阵是一样的!!!并且高斯消元的过程中,具体如何消元跟常数列无关,只与系数矩阵有关,因此我们考虑将这 m个增广矩阵合并,变成一个 n∗(n+m)且保证有唯一解的增广矩阵。这样,最终复杂度降为 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]);
}
}