自动搬运

查看原文

来自洛谷，原作者为

	Zhang_RQ In solitude, where we are least alone.

搬运于2025-08-24 21:52:24，当前版本为作者最后更新于2018-03-29 19:37:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题我们可以从邻接矩阵的幂的意义考虑。

设现在有一个邻接矩阵$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]$

代码如下

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