题解：
乍一看还是挺懵逼的。和HH去散步很像，思路也是类似的。
复制一段我在HH去散步的题解里面写的一段话吧：
考虑f[i][j]表示i和j是否右边相连，有为1，否则为0，那么f同时可以表示从每个点出发走一步到其他点的方案数。
于是用一个和f长得一模一样的矩阵g来表示从每个点出发到其他点的方案数。
那么考虑g如何转移。
其实只要用g*f就可以表示一次转移了。
为什么？
设当前转移到了第t次，则g[i][j]表示i到j走t-1次的方案数（因为还没有更新）
那么矩阵乘法做了什么？
$g[i][j] = sum_{l = 1}^{n}{g[i][l] * f[l][i]}$
也就是它枚举了点i走了t - 1次到l,然后再从l走一次到j的方案数。
是否能转移则要看l 到 j是否有边，而f[l][j]的意义刚好就是这样。
但这题有一些特殊的限制，就是会有食人鱼周期性的游动。
这样的话，转移就不再是一成不变的了，而是每天都有不同的不能去的地方，这样的话直接矩阵加速就做不了了。
但是暴力做矩阵乘法还是对的，因为这里的矩阵乘法实际上就是做一次DP
那么如何解决这个问题呢？
观察到题目给的一个特殊性质：周期只有2,3,4三种。gcd(2, 3, 4) = 12.这意味着每过12天，每天可走的路线又会与12天前重复。
所以如果我们把12天缩成1天，那么每天可走的路就是固定的了。
因此我们预处理出这12天每天可以走的路线，然后暴力转移12次，把12天的矩阵都浓缩成1个，然后再做矩阵乘法即可。
因为我们已经把12天缩成1天了，因此我们要乘的次数也变为了12分之一。
然后剩下的不能被12整除的天数就在末尾暴力乘即可。
由于矩阵乘法没有交换律，因此在暴力乘的过程中要格外注意顺序问题。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define AC 52 5 #define mod 10000 6 7 int n, m, s, t, k, num; 8 int g[AC][AC], go[AC][AC];//g记录连边情况,go表示第i条鱼，j时刻在哪 9 10 struct matrix{ 11 int s[AC][AC]; 12 }ans, f, p[15], box; 13 14 inline int read() 15 { 16 int x = 0;char c = getchar(); 17 while(c > '9' || c < '0') c = getchar(); 18 while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); 19 return x; 20 } 21 22 matrix cal(matrix x, matrix y) 23 { 24 for(R i = 1; i <= n; i ++) 25 for(R j = 1; j <= n; j ++) 26 { 27 box.s[i][j] = 0; 28 for(R l = 1; l <= n; l ++) 29 box.s[i][j] = (box.s[i][j] + x.s[i][l] * y.s[l][j]) % mod; 30 } 31 return box; 32 } 33 34 inline void pre() 35 { 36 int a, b, T; 37 n = read(), m = read(), s = read() + 1, t = read() + 1, k = read(); 38 for(R i = 1; i <= m; i ++)//读入桥 39 { 40 a = read() + 1, b = read() + 1; 41 g[a][b] = g[b][a] = 1; 42 } 43 num = read(); 44 for(R i = 1; i <= num; i ++)//读入鱼 45 { 46 T = read(); 47 for(R j = 0; j < T; j ++) go[i][j] = read() + 1; 48 for(R j = T; j < 12; j ++) go[i][j] = go[i][j - T]; 49 } 50 } 51 52 void qpow(int have) 53 { 54 if(have <= 0) return ; 55 while(have) 56 { 57 if(have & 1) ans = cal(ans, f); 58 f = cal(f, f); 59 have >>= 1; 60 } 61 } 62 63 void work() 64 { 65 for(R i = 0; i <= 11; i ++)//枚举时刻 66 { 67 for(R j = 1; j <= n; j ++)//枚举石墩 68 for(R l = 1; l <= n; l ++) p[i].s[j][l] = g[j][l]; 69 for(R j = 1; j <= num; j ++)//枚举鱼 70 { 71 int x = go[j][i];//获取这条鱼在这个时刻在哪里 72 for(R l = 1; l <= n; l ++) p[i].s[l][x] = 0;//枚举从哪个石墩来到x 73 } 74 } 75 if(k <= 12) 76 { 77 ans = p[1]; 78 for(R i = 2; i <= min(k, 11); i ++) ans = cal(ans, p[i]); 79 if(k == 12) ans = cal(ans, p[0]); 80 printf("%d ", ans.s[s][t]); 81 return ; 82 } 83 ans = p[1]; 84 for(R i = 2; i <= 11; i ++) ans = cal(ans, p[i]); 85 ans = cal(ans, p[0]); 86 f = ans; 87 qpow(k / 12 - 1);//因为有一个1在ans那 88 int b = k % 12; 89 for(R i = 1; i <= b; i ++) ans = cal(ans, p[i]); 90 printf("%d ", ans.s[s][t]); 91 } 92 93 int main() 94 { 95 // freopen("in.in", "r", stdin); 96 pre(); 97 work(); 98 // fclose(stdin); 99 return 0; 100 }