[TJOI2017]可乐

DP 矩阵乘法 快速幂

---

题面

$1$号城市上有个机器人，有三种行为： 停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现 在给地图，在第$0$秒时可乐机器人在$1$号城市，问经过了$t$秒，可乐机器人的行为方案数是多少？

• $t\leq10^6,n\leq30$

解析

显然可以$DP$。
设$f[u][t]$表示第$t$秒到第$u$点的方案数。
则有转移方程式：(点$v$是点$u$的邻点）

$$f[u][t]=f[u][t+1]+f[v][t+1]+1$$
记搜一下得$ans=f[1][0]$。
复杂度$O(nt)$。

实际上，如果$t\leq10^{18}$，此题仍然可做。
把图上信息转化为邻接矩阵$A$。（$u,v$间如有边则$A[u][v]=A[v][u]=1$)
从$Floyd$角度来看，发现$A^k$的第$i$行第$j$列数表示的是从$i$到$j$走$k$步的路径方案数。
（同理，在另一种情况下可表示最短路径）
于是，$A^k$中$\sum_{i=0}^n A[1][i]$即为答案。

有点难度的是状态表示：

• 在原地停留：每个点都有一个从自己到自己的自环。

• 自爆：进入一个虚拟的、出不去的城市（如$0$城市）。

注意要允许$0$城市有自环，否则自爆的方案数就会乘$0$消失。

// luogu-judger-enable-o2
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=105,mod=2017;
int n,m,p,ans;
struct Matrix
{
  int a[105][105];
  Matrix operator *(Matrix b)
  {
    Matrix c;memset(c.a,0,sizeof(c.a));
    fp(k,0,n)
      fp(i,0,n)
      fp(j,0,n)
      (c.a[i][j]+=a[i][k]*b.a[k][j]%mod)%=mod;
    return c;
  }
}S,T;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();m=gi();
  fp(i,1,m)
    {
      re int u=gi(),v=gi();
      T.a[u][v]=T.a[v][u]=1;
      T.a[u][0]=T.a[v][0]=1;
      T.a[u][u]=T.a[v][v]=1;
    }
  T.a[0][0]=1;
  p=gi();
  fp(i,0,n) S.a[i][i]=1;
  while(p)
    {
      if(p&1) S=S*T;
      T=T*T;
      p>>=1;
    }
  fp(i,0,n) (ans+=S.a[1][i])%=mod;
  printf("%d\n",ans);
  return 0;
}