简化思考
本题如果去掉食人鱼的限制，就变成了一个裸的邻接矩阵k次幂，用矩阵快速幂乱搞一通即可。
初步思想
如果没有限制，能不能将这个如果变成现实呢？
我们可以考虑去掉每个食人鱼的影响，即食人鱼到那里就把对应的边去掉，然后再做快速幂。
但是这个做法是与时间有关的，对于每一个时间我们都要重新构造邻接矩阵，这样做错的离谱，构造完了根本就不关快速幂的事了。
观察题目，我们可以发现有几个很显眼的数字：这个周期只可能是2，3或者4个单位时间。
既然如此，那么关于时间的邻接矩阵一定会有循环。
循环节最大为：lcm(2,3,4)=12。
因此我们可以直接先求出所有食人鱼周期的lcm，然后构造出周期以内的所有邻接矩阵。
构造方法：
枚举lcm以内的时间，枚举食人鱼，找到每个食人鱼在对应时间的位置，将到达该位置的路径全部删除即可。
因为我们有以下恒等式：
因此我们可以将周期以内的邻接矩阵全部累乘，接着对累乘结果做一次矩阵快速幂，然后再乘上余下的周期内的矩阵即可。
代码
用上重载非常方便1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
typedef long long LL;
const int maxn=55,mod=10000;
struct Matrix {
LL n,m,a[maxn][maxn];
Matrix() {}
Matrix(LL n,LL m) {
init(n,m);
}
Matrix(LL n,LL m,char E) { //单位矩阵
init(n,m);
for(int i=1; i<=n; i++)a[i][i]=1;
}
void init(LL n,LL m) {
this->n=n;
this->m=m;
memset(a,0,sizeof(a));
}
LL* operator [] (const LL x) {
return a[x];
}
Matrix operator * (Matrix& b) {
Matrix c(n,b.m);
for(int i=1; i<=n; i++)
for(int j=1; j<=b.m; j++)
for(int k=1; k<=m; k++)
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
return c;
}
void operator *= (Matrix& b) {
*this=*this*b;
}
Matrix operator ^ (LL b) {
Matrix ans(n,m,'e'),a=*this;
while(b>0) {
if(b&1)ans=ans*a;
a*=a;
b>>=1;
}
return ans;
}
} state[15];
int n,m,Start,End,k,q,len[25],a[25][15],LCM;
int main() {
n=Get_Int();
m=Get_Int();
Start=Get_Int()+1;
End=Get_Int()+1;
k=Get_Int();
Matrix Ori(n,n);
for(int i=1; i<=m; i++) {
int x=Get_Int()+1,y=Get_Int()+1;
Ori[x][y]=Ori[y][x]=1;
}
q=Get_Int();
for(int i=1; i<=q; i++) {
len[i]=Get_Int();
for(int j=1; j<=len[i]; j++)a[i][j]=Get_Int()+1;
if(i==1)LCM=len[i];
else LCM=LCM/__gcd(LCM,len[i])*len[i];
}
for(int i=1; i<=LCM; i++) {
state[i]=Ori;
for(int j=1; j<=q; j++) {
int to=i%len[j]+1;
for(int k=1; k<=n; k++)state[i][k][a[j][to]]=0;
}
}
Matrix b(n,n,'E');
for(int i=1; i<=LCM; i++)b*=state[i];
Matrix ans(n,n);
ans=b^(k/LCM);
for(int i=1; i<=k%LCM; i++)ans*=state[i];
printf("%lld\n",ans[Start][End]);
return 0;
}
