题解 P3758 【[TJOI2017]可乐】

这道题我们可以从**邻接矩阵**的**幂**的意义考虑。 设现在有一个邻接矩阵$A$。 那么$A^k$的意义是什么？（两个点之间若有边则$A[u][v]=1$） 从$floyd$算法的角度考虑，不难发现$A^k$的第$i$行第$j$列的数字含义是从$i$到$j$经过$k$步的路径方案总数。 从这个角度考虑，这个点就有了一种做法。 首先将这个图的邻接矩阵建出来，然后直接算这个矩阵的$k$次方。 最后统计$\sum\limits_{i=1}^{n}A[1][i]$就是答案。 那么在原地停留和自爆怎么处理？ 在原地停留很简单，我们只要认为每个点都有一个从自己到自己的自环即可。 那自爆呢？ 我们可以将自爆这个**状态**也看成一个**城市**，就设它为编号$0$。 我们在邻接矩阵上从每个点都向这个点连一条边，这个点除了自己外不连其他出边。 这样就满足了任何一个点随时可以自爆，且无法恢复到其他状态。 最后，统计答案。$Ans=\sum\limits_{i=0}^{n}A[1][i]$ 代码如下 ```cpp #include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<set> #include<map> #include<queue> #include<stack> typedef long long ll; typedef unsigned long long ull; using namespace std; const int P=2017; struct Matrix{ int a[31][31]; inline Matrix operator * (const Matrix &rhs) { Matrix ret; memset(&ret,0,sizeof ret); for(int i=0;i<=30;i++) for(int j=0;j<=30;j++) for(int k=0;k<=30;k++) (ret.a[i][j]+=a[i][k]*rhs.a[k][j]%P)%=P; return ret; } }mp; Matrix ksm(Matrix &a,int b) { Matrix ret; memset(&ret,0,sizeof ret); for(int i=0;i<=30;i++) ret.a[i][i]=1; while(b) { if(b&1) ret=ret*a; a=a*a;b>>=1; } return ret; } int u,v,n,m,t; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); mp.a[u][v]=1;mp.a[v][u]=1; } for(int i=0;i<=n;i++) mp.a[i][i]=1; for(int i=1;i<=n;i++) mp.a[i][0]=1; int ans=0; scanf("%d",&t); Matrix anss=ksm(mp,t); for(int i=0;i<=n;i++) (ans+=anss.a[1][i])%=P; printf("%d\n",ans); } ```