沼泽鳄鱼

题目link：https://www.luogu.com.cn/problem/P2579

---

Part1：

首先不看鳄鱼，那么题目要求的就是豆豆从 $s$ 走到 $e$ 并走过 $k$ 条边的方案数（这里每过一个石桥需要 $k$ 单位的时间，因此也可将其看作走过 $k$ 条边）。

这里不难想到图论中邻接矩阵记作 $E(n$$,$ $n)$ 的一个特性，便是 $E^a$ 得到的矩阵 $E'$中，$E'$_$i,j$ 表示从 $i$ 到 $j$ 经过 $a$ 条边的路径方案数，根据矩阵乘法的定义及公式不难证明。

那么现在没有鳄鱼的情况就可以求出来了，根据邻接矩阵的特性容易得出答案为 $E^k$_$s,e$，而这个 $k$ 次方可以用矩阵快速幂来求出。

---

Part2：

既然没有鳄鱼的情况能够求出来了，那么来看看加上鳄鱼后这个邻接矩阵有什么变化。

容易发现在某一时刻，如果有一个鳄鱼在第 $u$ 个石墩上，那么邻接矩阵的第 $u$ 列都会变成 $0$ 。

这样以来，便容易求出某一时刻的邻接矩阵（方法即为当前时间对鳄鱼的周期取余并修改邻接矩阵）。

再来看看邻接矩阵的特性在其变化后是否仍然成立（这里这个特性改为在用当前时间的邻接矩阵 $*$ 后一单位时间的邻接矩阵 $*$ $...$ $*$ 后 $a$ 单位时间的邻接矩阵后得到的矩阵 $E'(n,$ $n)$ 中，$E'$_$i,j$ 表示从 $i$ 到 $j$ 经过 $a$ $+$ $1$ 条边的路径方案数）。当然容易得出是成立的，继续利用矩阵乘法的定义及公式不难证明。

现在，似乎已经可以求出在有鳄鱼的情况下的答案了（用每单位时间的邻接矩阵相乘），但是，题目中 $k$ 的大小为 $2$ $*$ $10^9$，直接炸掉。

---

Part3：

考虑优化，发现题目中还有一个条件——鳄鱼的周期大小只可能为 $2,3,4$。

这提供一个什么信息呢？那便是每经过 $12$ 个周期（$2,3,4$ 的最小公倍数），所有鳄鱼的位置便会循环一次，而这则是解决问题的关键。

因为得到了上面的结论，容易得出如果将每单位时间的邻接矩阵都列出，那么相隔 $12$ 个矩阵的邻接矩阵便是一样的，因此只会有 $12$ 个不同的邻接矩阵，且它们都是顺序排列的。

这样问题就迎刃而解了，先将前 $12$ 个单位时间的邻接矩阵求出，求出它们乘积的 $(k$ $/$ $12)$ 次方（矩阵快速幂解决），并对 $k$ $/$ $12$ 的余数进行一些处理。

---

时间复杂度 $Ο(n^3$ $*$ $log$ $k)$ 。

---

Code：

#include <cstdio>

const int MAXN = 50;
const int MAXNF = 20;
const int MOD = 10000;

int n, m, s, e, k, nf, T[MAXNF + 5], p[MAXNF + 5][5];

struct Mat {

    int N, arr[MAXN + 5][MAXN + 5];

    Mat() {}
    Mat(int _N, int fgr = 0) {
        N = _N;
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < N; ++j) {
                arr[i][j] = (i == j) ? fgr : 0;
            }
        }
    }

    void Prt() {
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < N; ++j) {
                printf("%d%c", arr[i][j], (j == N - 1) ? '
' : ' ');
            }
        }
        puts("");
    }

    void Dlt(int pos) {
        for(int i = 0; i < N; ++i) {
            arr[i][pos] = 0;
        }
    }

};

Mat operator* (const Mat &A, const Mat &B) {

    Mat res(A.N);

    for(int i = 0; i < res.N; ++i) {
        for(int j = 0; j < res.N; ++j) {
            for(int k = 0; k < res.N; ++k) {
                res.arr[i][j] += A.arr[i][k] * B.arr[k][j];
                res.arr[i][j] %= MOD;
            }
        }
    }

    return res;
}

Mat qpw(Mat A, int fgr) {

    Mat res(n, 1);

    for(; fgr; fgr >>= 1) {
        if(fgr & 1) res = res * A;
        A = A * A;
    }

    return res;
}

int main() {

    scanf("%d %d %d %d %d", &n, &m, &s, &e, &k);

    Mat adj(n);
    for(int i = 1, x, y; i <= m; ++i) {
        scanf("%d %d", &x, &y);
        adj.arr[x][y] = adj.arr[y][x] = 1;
    }

    scanf("%d", &nf);
    for(int i = 1; i <= nf; ++i) {
        scanf("%d", &T[i]);
        for(int j = 0; j < T[i]; ++j) {
            scanf("%d", &p[i][j]);
        }
    }

    Mat fac(n, 1), chg[15];
    for(int t = 1; t <= 12; ++t) {
        chg[t] = adj;
        for(int i = 1; i <= nf; ++i) {
            chg[t].Dlt(p[i][t % T[i]]);
        }
        fac = fac * chg[t];
    }
    fac = qpw(fac, k / 12);
    for(int i = 1; i <= k % 12; ++i) {
        fac = fac * chg[i];
    }

    printf("%d", fac.arr[s][e]);

    return 0;
}