洛谷P5789 [TJOI2017]可乐 题解

题目链接：P5789 [TJOI2017]可乐（数据加强版） （双倍经验：P3758）

题意：

加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 $1$ 号城市上。这个可乐机器人有三种行为： 停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给加里敦星球城市图，在第 $0$ 秒时可乐机器人在 $1$ 号城市，问经过了 $t$ 秒，可乐机器人的行为方案数是多少？

输入格式：

第一行输入两个正整数 $N,M$ ，$N$ 表示城市个数，$M$ 表示道路个数。

接下来 $M$ 行输入 $u,v$ ，表示 $u,v$ 之间有一条双向道路。

最后输入时间 $t$ 。

输出格式：

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

数据范围：

$n,m\leq 100,~t\leq 10^9$ 。

朴素的无向图邻接矩阵快速幂，自爆的话，加个虚点“天堂”就好啦~

注意每个点要连自环，并且向虚点的边是有向边。

至于为什么无向图邻接矩阵可以直接矩阵快速幂，想想转移矩阵的贡献关系就知道啦~

时间复杂度 $\mathcal{O}(n^3 \log t)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 2017;
typedef vector< vector<int> > mat;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : x; }
#define N ((int)())

mat mul(mat A, mat B)
{
    int n = A.size(), m = A[0].size(), p = B[0].size();
    mat C(n, vector<int>(p));
    for(int k = 0; k < m; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < p; j++)
                add(C[i][j], A[i][k] * B[k][j] % mod);
    return C;
}
mat qpow(mat A, int b)
{
    int n = max(A.size(), A[0].size());
    mat ans(n, vector<int>(n));
    for(int i = 0; i < n; i++) ans[i][i] = 1;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = mul(ans, A);
        A = mul(A, A);
    }
    return ans;
}
int sum(mat M,int n)
{
    int res = 0;
    for(int i = 0; i < n; i++) res += M[0][i];
    return res % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n,m,t; cin >> n >> m; ++n;
    mat M(n, vector<int>(n));
    for(int i = 0,u,v; i < m; i++)
    {
        cin >> u >> v; --u, --v;
        M[u][v] = M[v][u] = 1;
    }
    for(int i = 0; i < n; i++) M[i][i] = 1;
    for(int i = 0; i < n - 1; i++) M[i][n - 1] = 1;
    cin >> t; cout << sum(qpow(M,t), n) << '\n';
    return 0;
}