「SDOI 2009」HH去散步

题目大意：给定 $N$ 个点 $M$ 条边的无向图，问从点 $A$ 走 $t$ 步到点 $B$ 有多少种方案？不能往复走一条边。$N ≤ 50，M ≤ 60，t ≤ 2^{30}$

如果按照结点建立邻接矩阵，不能排除往复走一条边的情况，可以按照边来建立邻接矩阵，将每条边拆成两条有向边，并将它们的关系设为 $0$，保证不能直接互相到达。

#include <cstdio>
#include <cstring>

const int N = 55, M = 125, P = 45989;
int head[N], pre[M], nxt[M], tot;

struct Matrix {
    int x[M][M];
    Matrix() { memset(x, 0, sizeof x); }
    Matrix operator * (const Matrix a) const {
        Matrix b;
        for (int i = 1; i <= tot; ++i)
            for (int j = 1; j <= tot; ++j)
                for (int k = 1; k <= tot; ++k)
                    b.x[i][j] = (b.x[i][j] + x[i][k] * a.x[k][j]) % P;
        return b;
    }
} a, unit;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
void add_edge(int u, int v) {
    pre[++tot] = head[u];
    head[u] = tot, nxt[tot] = v;
}
void build() {
    for (int i = 1; i <= tot; ++i) {
        unit.x[i][i] = 1;
        for (int j = head[nxt[i]]; j; j = pre[j])
            a.x[i][j] = 1;
        if (i & 1) a.x[i][i+1] = 0;
        else a.x[i][i-1] = 0;
    }
}
Matrix fast_pow(Matrix a, int b) {
    Matrix res = unit;
    for (; b; b >>= 1, a = a * a)
        if (b & 1) res = res * a;
    return res;
}

int main() {
    int n = read(), m = read(), t = read(), A = read() + 1, B = read() + 1;
    for (int i = 1; i <= m; ++i) {
        int u = read() + 1, v = read() + 1;
        add_edge(u, v), add_edge(v, u);
    }
    build(); a = fast_pow(a, t - 1);
    int ans = 0;
    for (int i = head[A]; i; i = pre[i])
        for (int j = head[B]; j; j = pre[j]) {
            if (j & 1) ans = (ans + a.x[i][j+1]) % P;
            else ans = (ans + a.x[i][j-1]) % P;
        }
    printf("%d\n", ans);
    return 0;
}

时间复杂度 $O(m^3\log t)$