题目地址：洛谷：【P2151】[SDOI2009]HH去散步 – 洛谷、BZOJ：Problem 1875. — [SDOI2009]HH去散步

题目描述

HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间 内，走过一定的距离。 但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。
现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地 点A走到给定地点B共有多少条符合条件的路径

题意简述

给你一个无向图，求从a走到b且长度为t的路径总数，每条边经过次数不限，但是不能连续双向经过同一条边。

输入输出格式

输入格式：
第一行：五个整数N，M，t，A，B。其中N表示学校里的路口的个数，M表示学校里的 路的条数，t表示HH想要散步的距离，A表示散步的出发点，而B则表示散步的终点。
接下来M行，每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。数据保证Ai != Bi，但 不保证任意两个路口之间至多只有一条路相连接。 路口编号从0到N − 1。 同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。 答案模45989。

输出格式：
一行，表示答案。

输入输出样例

输入样例#1：

4 5 3 0 0
0 1
0 2
0 3
2 1
3 2

输出样例#1：

4

说明

对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。
对于100%的数据，N ≤ 50，M ≤ 60，t ≤ 2^30，0 ≤ A,B

题解

参考资料：题解 P2151 【[SDOI2009]HH去散步】 – roufaen 的博客 – 洛谷博客
可以考虑用边DP，dp[i][j]表示已经走出距离i，且最后走过的一条边是j的方案数。显然这里需要把无向边拆成两条有向边考虑。转移也很显然，对于一条边i(u, v)及对应的状态dp[t][i]，可以从j(w, u)对应的dp[t-1][j]转移过来，不过要判断i和j在原来的无向图中是否为同一条边。
我们观察到t的范围很大，而上述转移在两个距离之间显然是固定的线性变换，可以考虑使用矩阵快速幂加速转移。优化后的复杂度为O(4m^2 \log t)。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 205, MO = 45989;

int n, m;

struct Matrix {
    int a[MAXN][MAXN];
    Matrix() {
        memset(a, 0, sizeof(a));
    }
    inline Matrix operator*(const Matrix &rhs) const {
        Matrix res;
        for(int i = 0; i < m << 1; i++) {
            for(int j = 0; j < m << 1; j++) {
                for(int k = 0; k < m << 1; k++) {
                    res.a[i][j] = (res.a[i][j] + a[i][k] * rhs.a[k][j]) % MO;
                }
            }
        }
        return res;
    }
    inline Matrix& operator*=(const Matrix &x) {
        return *this = *this * x;
    }
};

inline Matrix fpow(Matrix x, LL k) {
    Matrix res;
    for(int i = 0; i < m << 1; i++) {
        res.a[i][i] = 1;
    }
    while(k) {
        if(k & 1) res *= x;
        x *= x;
        k >>= 1;
    }
    return res;
}

struct Edge {
    int u, v;
} edges[MAXN];

LL t;
int a, b;
Matrix def, trans;

int main() {
    n = readint(); m = readint(); t = readint(); a = readint(); b = readint();
    for(int i = 0, u, v; i < m; i++) {
        u = readint(); v = readint();
        edges[i << 1] = Edge {u, v};
        edges[i << 1 | 1] = Edge {v, u};
    }
    for(int i = 0; i < m << 1; i++) {
        def.a[i][0] = (edges[i].u == a);
    }
    for(int i = 0; i < m << 1; i++) {
        for(int j = 0; j < m << 1; j++) {
            trans.a[j][i] = (edges[i].v == edges[j].u && i != (j ^ 1));
        }
    }
    trans = fpow(trans, t - 1);
    def = trans * def;
    int ans = 0;
    for(int i = 0; i < m << 1; i++) {
        if(edges[i].v == b) ans = (ans + def.a[i][0]) % MO;
    }
    printf("%d", ans);
    return 0;
}