emm

Problem

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

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

$n\leq 50, m\leq 60,t\leq 2^{30}$

Solution

对每个点新建多个虚点

每个虚点有一条入边，多条出边

同时对起点特殊建立

那么最多有 $2m+1$ 个点

记录每个虚点的入边是从哪条边过来的

矩阵转移就行了

Code

// Code by ajcxsu
// Problem: take a walk

#include<bits/stdc++.h>
#define MOD (45989)
using namespace std;

const int N=51, M=122;
int h[N], to[M], nexp[M], p=2;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
vector<int> nd[N];
int fr[M];
int idx;
struct matrix {
    int a[M][M];
    matrix() { memset(a, 0, sizeof(a)); }
    int * operator [] (int x) { return a[x]; }
    matrix operator * (matrix &b) {
        matrix c;
        for(int i=1;i<M;i++)
        for(int k=1;k<M;k++)
        for(int j=1;j<M;j++)
            (c[i][j]+=a[i][k]*b[k][j])%=MOD;
        return c;
    }
} S, T;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, t, a, b, na, nb, u, v;
    cin>>n>>m>>t>>a>>b;
    for(int i=0;i<m;i++) {
        cin>>u>>v, ins(u, v), ins(v, u), na=++idx, nb=++idx;
        fr[na]=p-1, fr[nb]=p-1;
        nd[u].push_back(na), nd[v].push_back(nb);
    }
    for(int i=0;i<n;i++)
        for(auto na:nd[i])
            for(int u=h[i];u;u=nexp[u])
                if(u!=fr[na] && (u^1)!=fr[na])
                    for(auto nb:nd[to[u]])
                        if(fr[nb]==u || fr[nb]==(u^1))
                            T[na][nb]=1;
    ++idx;
    assert(idx<M);
    for(int u=h[a];u;u=nexp[u])
        for(auto nb:nd[to[u]])
            if(fr[nb]==u || fr[nb]==(u^1))
                T[idx][nb]=1;
    a=idx, S[a][a]=1;
    while(t) {
        if(t&1) S=S*T;
        T=T*T, t>>=1;
    }
    int ans=0;
    for(auto na:nd[b])
        ans+=S[a][na];
    cout<<ans%MOD<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-2151.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆