洛谷P2151 [SDOI2009] HH去散步题解

题目链接：P2151 [SDOI2009] HH去散步

题意：

HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。

现在给你学校的地图（假设每条路的长度都是一样的都是 $1$ ），问长度为 $t$ ，从给定地点 $A$ 走到给定地点 $B$ 共有多少条符合条件的路径

输入格式：

第一行：五个整数 $n,m,t,A,B$。其中 $n$ 表示学校里的路口的个数， $m$ 表示学校里的路的条数，$t$ 表示HH想要散步的距离，$A$ 表示散步的出发点，而 $B$ 则表示散步的终点。

接下来 $m$ 行，每行一组 $A_i,B_i$ ，表示从路口 $A_i$ 到路口 $B_i$ 有一条路。数据保证 $A_i \ne B_i$ ，但不保证任意两个路口之间至多只有一条路相连接。路口编号从 $0$ 到 $n-1$ 。同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。答案模 $45989$ 。

输出格式：

一行，表示答案。

数据范围：

$n \le 50,~m \le 60,~t \le 2^{30},~0 \le A,B$

设 $f_{i,j}$ 表示不考虑限制走了 $i$ 步，到达 $j$ 的方案数，则

$f_{i,j} = \sum_{k \in S(j)} f_{i-1,k} \times s(k,j)$

其中 $S(j)$ 为能到达 $j$ 的节点的集合，$s(k,j)$ 表示重边数。

加入限制以后，这个 $S$ 就不好用了，考虑重新定义它。

定义 $S(j)$ 为终点为 $j$ 的边的集合（不包括反向边）

此时 $f_{i,j}$ 表示走了 $i$ 步，到达 $j$ 的方案数，式子形式基本不变

$f_{i,j} = \sum_{k \in S(j)} f_{i-1,k} \times s(k)$

然后就是简单的矩阵快速幂，注意顺序不要反了，$M_{i,j}$ 表示 $i \to j$ 时的转移系数。

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

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 45989;
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; }

int n,m,K,s,t,pos = 1,head[65]; 
struct Edge { int u,v,next; } e[135];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
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;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);

    cin >> n >> m >> K >> s >> t;
    if(m == 0) return cout << "0\n", 0;
    if(K == 0) return cout << (s == t) << '\n', 0;
    mat M(2 * m, vector<int>(2 * m)), A(1, vector<int>(2 * m));
    for(int i = 0, u, v; i < m; i++)
    {
        cin >> u >> v;
        addEdge(u,v); addEdge(v,u);
    }
    for(int k = 2; k <= pos; k++)
        for(int i = head[e[k].v]; i; i = e[i].next)
            if(k != (i ^ 1)) ++M[k - 2][i - 2];
    
    for(int i = head[s]; i; i = e[i].next) ++A[0][i - 2];
    if(K != 1) A = mul(A, qpow(M, K - 1)); int res = 0;
    for(int i = head[t]; i; i = e[i].next) add(res, A[0][(i ^ 1) - 2]);
    // for(int i = 0; i < 2 * m; i++) cout << A[0][i] << " \n"[i == 2 * m - 1];
    cout << res << '\n';
    return 0;
}