目录
显示
题目链接
https://www.luogu.org/problem/P3758
题解
参考了一下 Zhang_RQ 的题解。
我们先建一个邻接矩阵 \(A\):对于两个有边相连的点 \(i,j\) ,\(A_{i,j}=1\),特别地,\(A_{i,i}=1\)(可以停留在一个点不动),\(A_{i,0}=1\)(代表在这个点自爆)。
我们考虑邻接矩阵幂 \(A^k\) 的含义:\(A_{i,j}^k\) 代表了从 \(i\) 到 \(j\) 走 \(k\) 步的方案数。
这样答案就很清晰了:我们要求的就是 \(\sum_{i=0}^n A_{1,i}^t\)。
使用矩阵快速幂即可。
#include <cstdio> #include <cstring> #define MOD 2017 struct mat { int a[35][35]; mat() { memset(a,0,sizeof(a)); } }f; int n,m,t; mat init() { mat tmp; for(int i=0;i<=n;i++) tmp.a[i][i]=1; return tmp; } mat operator*(mat a,mat b) { mat ans; for(int k=0;k<=n;k++) for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%MOD; return ans; } mat fpow(mat x,int y) { mat ans=init(); while(y) { if(y&1)ans=ans*x; x=x*x; y>>=1; } return ans; } int main() { scanf("%d%d",&n,&m); f=init(); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); f.a[u][v]=f.a[v][u]=1; } for(int i=1;i<=n;i++) f.a[i][0]=1; scanf("%d",&t); mat res=fpow(f,t); int ans=0; for(int i=0;i<=n;i++) ans=(ans+res.a[1][i])%MOD; printf("%d\n",ans); return 0; }
邻接矩阵幂 $A^k$ 的含义可以用数学归纳法证
评论居然不支持{\LaTeX}
Orz