HDU 5607 graph（矩阵乘法）

时间：2023-03-08 20:28:15

题意

在一个 \(n\) 个节点 \(m\) 条边的有向图上随机游走，有 \(Q\) 个询问，每次给定一个起点 \(u\) 和步数 \(K\) ，每次回答最后停在每个节点的概率。

\(1 \leq n \leq 50\)

\(1 \leq m \leq 1000\)

\(1 \leq Q \leq 20\)

\(1 \leq K \leq 10^9\)

思路

同样构造一个“起始矩阵” \(A_{1n}\) 和一个“转移矩阵” \(B_{nn}\) 。如果知道 \(B_{i,j}\) 的含义，就是 \(i\) 点到 \(j\) 点的“转移系数” ，矩阵乘法就不是问题了。

对于每个询问 \((u,K)\) ，\(A_{1,u}=1\) ，\(B_{i,j}\) 为 \(i\) 点走到 \(j\) 点的概率，然后输出 \(A*B^K\) 矩阵的每一项即可。

代码

#include<bits/stdc++.h>

#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)

#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)

typedef long long LL;

using namespace std;

const int N=55;

const int M=1005;

const int P=1e9+7;

struct Matrix

{

	int n,m,a[N][N];

	int *operator [](const int x){return a[x];}

	void resize(int _n,int _m){n=_n,m=_m;}

	Matrix operator *(const Matrix &_)const

	{

		Matrix res;res.resize(n,_.m);

		FOR(i,1,n)FOR(j,1,_.m)

		{

			res[i][j]=0;

			FOR(k,1,m)(res[i][j]+=1ll*a[i][k]*_.a[k][j]%P)%=P;

		}

		return res;

	}

	Matrix operator *=(const Matrix &_){return (*this)=(*this)*_;}

};

LL inv[M];

Matrix A,B;

int oud[N],U[M],V[M];

int n,m,Q;

Matrix Pow(Matrix a,int p)

{

	Matrix res;res.resize(a.n,a.n);

	FOR(i,1,res.n)FOR(j,1,res.n)res[i][j]=(i==j);

	for(;p>0;p>>=1,a*=a)if(p&1)res*=a;

	return res;

}

LL frac(LL x,LL y){return x*inv[y]%P;}

int main()

{

	inv[0]=inv[1]=1;FOR(i,2,N-1)inv[i]=(P-P/i)*inv[P%i]%P;

	while(~scanf("%d%d",&n,&m))

	{

		A.resize(1,n),B.resize(n,n);

		memset(oud,0,sizeof(oud));

		FOR(i,1,m)scanf("%d%d",&U[i],&V[i]),oud[U[i]]++;

		FOR(i,1,n)FOR(j,1,n)B[i][j]=0;

		FOR(i,1,m)(B[U[i]][V[i]]+=frac(1,oud[U[i]]))%=P;

		scanf("%d",&Q);

		while(Q--)

		{

			int u,K;

			scanf("%d%d",&u,&K);

			FOR(i,1,n)A[1][i]=(i==u);

			A*=Pow(B,K);

			FOR(i,1,n)printf("%d ",A[1][i]);

			puts("");

		}

	}

	return 0;

}

相关文章