P5789 [TJOI2017] 可乐（数据加强版）矩阵乘法、邻接矩阵

题目链接

题目大意

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

输出可乐机器人的行为方案数，答案可能很大，请输出对 $2017$ 取模后的结果。

思路

首先需要知道，用邻接矩阵 $A_{i,j}=1$ 表示有一条 $i$ 到 $j$ 的有向边，则 $A^k$ 中的 $A_{i,j}^k$ 表示图上 $i$ 到 $j$ 恰好经过 $k$ 条边的路径数。

先根据所给的图建一个初始的矩阵，停在原地看成是走了一条自环，爆炸可以看成是指向$0$点的路且$0$号点要有自环（表示爆炸后只能待在$0$号点）。

求出$A^k$,$ans={\sum }_{i=0}^n$$A_{1,i}^k$.

code

#include<bits/stdc++.h>

using namespace std;
const int mod=2017;
int n,p;

struct matrix {
    int m[110][110];
    matrix (int option=0) {
        memset(m,0,sizeof(m));
        if(option==1) {
            for(int i=0;i<=100;++i)
                m[i][i]=1;
        }
    }
    matrix operator*(const matrix & x)const {
        matrix tmp(0);
        for(int i=0;i<=n;++i)
            for(int j=0;j<=n;++j)
                for(int k=0;k<=n;++k)
                    tmp.m[i][j]=(tmp.m[i][j]+m[i][k]*x.m[k][j]%mod)%mod;
        return tmp;
    }
};

matrix operator^(matrix & x,int k) {
    matrix e(1);
    while(k>0) {
        if(k&1) e=e*x;
        x=x*x;
        k>>=1;
    }
    return e;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>p;
    matrix ans(0);
    while(p--) {
        int u,v;
        cin>>u>>v;
        ans.m[u][v]=1;
        ans.m[v][u]=1;
    }
    for(int i=0;i<=n;++i)
        ans.m[i][i]=1,ans.m[i][0]=1;
    int t;
    cin>>t;
    ans=ans^t;
    int res=0;
    for(int i=0;i<=n;++i)
        res=(res+ans.m[1][i])%mod;
    cout<<res<<'\n';
    return 0;
}