洛谷3758 [TJOI2017]可乐

题意

一个机器人从 $N$ 点 $M$ 边有向图的 $1$ 出发，每秒可能有 $3$ 种行为：

1. 留在原地
2. 沿边去下一个城市
3. 自爆，自爆后不能再行动

求 $T$ 秒后的行为方案数。

$N\le 30 \ , \ M\le 100 \ , \ T\le 10^6$ 。

题解

只考虑行为 $2$ ，可以用矩阵快速幂来实现，初始的图 $^T$ 就是答案。

对于行为 $1$ ，相当于每个点都有个自环。

对于行为 $3$ ，可以建立一个自爆点，所有点都向它连边，而它的出度为 $0$ 。

#include<bits/stdc++.h>
#define ha 2017

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

struct matrix {
    int n,s[35][35];
    matrix(int len=0) { n=len; memset(s,0,sizeof(s)); for (int i=1;i<=n;i++) s[i][i]=1; }
    matrix operator * (const matrix &x) const {
        matrix y;
        y.n=n;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                for (int k=1;k<=n;k++)
                    y.s[i][j]=(y.s[i][j]+s[i][k]*x.s[k][j]%ha)%ha;
        return y;
    }
};
int n,m,t,a,b;

inline matrix qpow(matrix x,int y)
{
    matrix ans(n+1);
    while (y)
    {
        if (y&1) ans=ans*x;
        y>>=1;
        x=x*x;
    }
    return ans;
}

signed main()
{
    n=read(); m=read();
    matrix mp(n+1);
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        mp.s[a][b]=mp.s[b][a]=1;
    }
    for (int i=1;i<=n;i++) mp.s[i][n+1]=1;
    t=read();
    mp=qpow(mp,t);
    int ans=0;
    for (int i=1;i<=n+1;i++) ans=(ans+mp.s[1][i])%ha;
    return !printf("%d",ans);
}