[洛谷 3758][TJOI2017]可乐

题目链接

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;
}