看了题解之后大概是知道要怎么用矩阵优化dp了，但是就是写不对只有十分QAQ，代码风格很好懂，求助大佬！

#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

int n, t;
const int m = 45989;
int cnt = 0;
int out[150], in[150];

template<typename T>
class Matrix
{
public:
    static const int maxn = 150;
    T val[maxn][maxn];

    Matrix(initializer_list<initializer_list<T>> l)
    {
        memset(val, 0, sizeof val);
        int i = 0, j = 0;

        for (auto &it : l)
        {
            for (auto &v : it)
                val[i][j++] = v;
            i++;
            j = 0;
        }
    }

    Matrix() { memset(val, 0, sizeof val); }

    Matrix operator*(const Matrix &b)
    {
        Matrix ans;
        T r = 0;

        for (int i = 0; i < maxn; i ++)
            for (int k = 0; k < maxn; k ++)
            {
                r = val[i][k];
                for (int j = 0; j < maxn; j ++)
                    (ans.val[i][j] += b.val[k][j] * r % m) %= m;
            }

        return ans;
    }

};

template<typename T>
Matrix<T> geteMatrix()
{
    Matrix<T> e;
    for (int i = 0; i < e.maxn; i++)
        e.val[i][i] = 1;
    return e;
}

template<typename T>
Matrix<T> matrixPow(Matrix<T> &a, int b)
{
    Matrix<T> ans = geteMatrix<T>();
    Matrix<T> tmp = a;

    while (b)
    {
        if (b & 1)
            ans = ans * tmp;
        tmp = tmp * tmp;
        b >>= 1;
    }
    return ans;
}

Matrix<long long> f, ft;

signed main()
{
    int n, t, a, b, m;
    cin >> n >> m >> t >> a >> b;

    for (int i = 1; i <= m; i ++)
    {
        int a, b;
        cin >> a >> b;

        out[cnt] = a, in[cnt++] = b;
        out[cnt] = b, in[cnt++] = a;
    }

    for (int i = 0; i < cnt; i ++)
    {
        for (int j = 0; j < cnt; j ++)
            if (i != j && in[i] == out[j] && i != (j ^ 1))
                ft.val[i][j] = 1;
    }

    for (int i = 0; i < cnt; i ++)
    if (in[i] == a)
    {
        f.val[i][0] = 1;
    }
    f = matrixPow(ft, t - 1) * f;
    int ans = 0;
    for (int i = 0; i < cnt; i ++)
    {
        if (out[i] == b)
            (ans += f.val[i][0]) %= m;
    }
    cout << ans << '\n';
}