【题解】跑步 矩阵快速幂 BZOJ – 3792

题目链接：https://www.mina.moe/BZPRO/JudgeOnline/3792.html

QAQ 大水题我都不会啊嘤嘤嘤

肯定要矩阵快速幂啦！

先把无向边拆成有向边。

然后呢矩阵 $d[x][y]$表示第 $x$条有向边能否转移到第 $y$条有向边

然后防止从反向边转移就行啦。

最后计算 $s$的出边到 $i$的入边的转移数之和就行啦。

另外这题如果乘法取模中间结果开了 long long 会超时。。。本机 AC 提交 TLE，坑我了半天。。。

#include <bits/stdc++.h>

#define REG register
#define MS (125)
#define MOD (45989)
#define pls(a, b) ((a) + (b) >= MOD ? (a) + (b) - MOD : (a) + (b))
#define mul(a, b) ((a) * (b) % MOD)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, s, u[MS], v[MS], cnt, d[MS][MS], res[MS][MS], tmp[MS][MS];

LL q;

inline void M_mul(int (&a)[MS][MS], int (&b)[MS][MS])
{
    memset(tmp, 0, sizeof(tmp));
    for (REG int k = 0; k < cnt; k += 1)
        for (REG int i = 0; i < cnt; i += 1)
            for (REG int j = 0; j < cnt; j += 1)
                tmp[i][j] = pls(tmp[i][j], mul(a[i][k], b[k][j]));
    memmove(a, tmp, sizeof(a));
}

inline void M_qpow(REG LL k)
{
    for (REG int i = 0; i < cnt; i += 1) res[i][i] = 1;
    while (k)
    {
        if (k & 1) M_mul(res, d);
        M_mul(d, d), k >>= 1;
    }
}

int se[MS], sc;

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(s), IN(q);
    for (REG int i = 1; i <= m; i += 1)
    {
        IN(u[cnt]), IN(v[cnt]), cnt++;
        u[cnt] = v[cnt - 1], v[cnt] = u[cnt - 1], cnt++;
    }
    for (REG int i = 0; i < cnt; i += 1)
        for (REG int j = 0; j < cnt; j += 1)
            if (i != j && i != (j ^ 1) && v[i] == u[j])
                d[i][j] = 1;
    M_qpow(q - 1);
    for (REG int i = 0; i < cnt; i += 1)
        if (u[i] == s) se[++sc] = i;
    for (REG int i = 1; i <= n; i += 1)
    {
        REG int ans = 0;
        for (REG int j = 0; j < cnt; j += 1)
            if (v[j] == i)
                for (REG int k = 1; k <= sc; k += 1)
                    ans = pls(ans, res[se[k]][j]);
        printf("%d\n", ans);
    }
    return 0;
}