[SDOI2009] HH去散步

传送门

题目分析

首先观察数据范围\(N \le 50\)，\(M \le 60\)，\(t \le 2^{30}\)

\(N,M\)很小，但\(t\)很大，不足以支持依赖于\(t\)的动态规划，那就要向其他方向去思考。

对于这类定长路径且支持邻接矩阵的图论，我们有一个很好用的结论兼工具——矩阵乘法。对于一个邻接矩阵进行\(k\)次乘法，\(G_{i,j}\)的含义变为从\(i\)出发，经过\(k\)条边(可重)到达\(j\)的方案数，与本题十分契合

但需要解决的还有不能后撤步这一问题，对此，因为数据范围较小，我们可以将边与点进行转化，将每一条边拆成两条有向边，关于某一个点\(u\)将指向\(u\)的边连向从\(u\)向外连且不为当前边的边。这样构造出邻接矩阵，然后使用矩阵快速幂跑出\(k\)次幂，最后的答案就是从\(start\)连出的边集与连入\(end\)的边集两两配对所得答案之和

结论证明

证明一

摘自博客

证明2

摘自OI Wiki

实现

#include<bits/stdc++.h>
using namespace std;
const int N = 55, M = 125;
typedef long long LL;
const LL mod = 45989;
struct matrix {
    int n, m;
    LL mat[M][M];
    inline void init(int _n, int _m) {
        n = _n, m = _m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                mat[i][j] = 0;
    }//初始化
    inline matrix operator * (const matrix& o)const {
        matrix ret;
        ret.init(n, o.m);
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= o.m;j++)
                for (int k = 1;k <= m;k++)
                    ret.mat[i][j] = ((ret.mat[i][j] + mat[i][k] * o.mat[k][j] % mod) % mod + mod) % mod;
        return ret;
    }//矩阵乘法
    inline matrix matrix_power(matrix a, LL k) {
        matrix ret;
        ret.init(a.n, a.n);
        for (int i = 1; i <= a.n; i++)
            ret.mat[i][i] = 1;
        while (k) {
            if (k & 1)
                ret = ret * a;
            a = a * a;
            k >>= 1;
        }
        return ret;
    }//矩阵快速幂
};
int n, m, st, ed;
LL t;
vector<int>edge_in[N], edge_out[N];//与每一个点相连的边集
matrix G;//邻接矩阵
int main() {
    scanf("%d%d%lld%d%d", &n, &m, &t, &st, &ed);
    st++, ed++;
    G.init(m * 2, m * 2);//每条边要拆成2条单向边，所以是2*m
    for (int i = 1;i <= m;i++) {
        int u, v;scanf("%d%d", &u, &v);
        u++, v++;
        edge_in[u].push_back(i);
        edge_out[v].push_back(i);
        edge_out[u].push_back(i + m);
        edge_in[v].push_back(i + m);
    }
    for (int i = 1;i <= n;i++)
        for (auto e1 : edge_in[i])
            for (auto e2 : edge_out[i])
                if (abs(e1 - e2) != m && abs(e1 - e2) != 0) G.mat[e1][e2] = 1;
    //构造邻接矩阵
    G = G.matrix_power(G, t - 1);
    //对于边，我们出发时并未计算第1条边，所以t要减一
    LL ans = 0;
    for (auto e_st : edge_out[st])
        for (auto e_ed : edge_in[ed])
            if (abs(e_st - e_ed) != m && abs(e_st - e_ed) != 0)
                ans = (ans + G.mat[e_st][e_ed]) % mod;
    for (auto e_st : edge_out[st])
        for (auto e_ed : edge_in[ed])
            if (abs(e_st - e_ed) == m || abs(e_st - e_ed) == 0)
                ans = (ans + G.mat[e_st][e_ed]) % mod;
    //统计答案
    printf("%lld", ans);
    return 0;
}