作者:聆听最遥远的歌声 | 来源:互联网 | 2023-05-17 10:32
题目大意:n个顶点,m条边,现在要求你在T步内能够从i走到j,求一共的方案数目解题思路:用到了离散数学的知识,从i到j的通路数图的邻接矩阵的T次幂(这里要用到一下矩阵快速幂)实验代码:#includ
题目大意:n个顶点,m条边,现在要求你在T步内能够从i走到j,求一共的方案数目
解题思路:用到了离散数学的知识,从i到j的通路数=图的邻接矩阵的T次幂(这里要用到一下矩阵快速幂)
实验代码:
#include
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int N,M,T;
struct Matrix{
ll a[102][102];
};
Matrix Matrix_mul(Matrix s1,Matrix s2)
{
Matrix c;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
c.a[i][j]=0;
for(int k=1;k<=N;k++)
{
c.a[i][j]+=(s1.a[i][k]*s2.a[k][j])%mod;
}
c.a[i][j]%=mod;
}
}
return c;
}
Matrix Matrix_pow(int x,Matrix res)
{
Matrix ans;//构造单位矩阵
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
if(i==j)
ans.a[i][j]=1;
else
ans.a[i][j]=0;
}
}
while(x)
{
if(x&1)
ans=Matrix_mul(ans,res);
x>>=1;
res=Matrix_mul(res,res);
}
return ans;
}
int main()
{
while(~scanf("%d%d",&N,&M))
{
int u,v;
Matrix res;
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= N; j++)
{
res.a[i][j] = 0;
}
}
for(int i=0;i{
scanf("%d%d",&u,&v);
res.a[u][v]=res.a[v][u]=1;
}
for(int i=1;i{
res.a[N][i]=0;//走到N点就不能走了,所以这里就使没有这样的一条路
}
res.a[N][N]=1;//提早到了N点,就相当于一直在N处打转
scanf("%d",&T);
Matrix result=Matrix_pow(T,res);
cout<}
}
上述还有完整的矩阵快速幂做法