题目
题解
众所周知，因为鳄鱼名字里有鱼，食人鱼名字里有鱼，所以鳄鱼=食人鱼
发现不能经过的点最多有$12$种情况，即$lcm(2,3,4)$
所以把$12$种情况的矩阵都处理出来，然后$12$个时间一起处理，最后剩下的$k\%12$个时间暴力乘起来即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int N=55,mod=10000;
struct Mx{
int a[N][N];
int* operator[] (int x) {return a[x];}
}a,emp,w[13];
int n,k,m,s,t,nfs;
int p[4];
Mx operator* (Mx a,Mx b)
{
Mx c=emp;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
for(int k=0;k<n;++k)
{
c[i][j]+=1ll*a[i][k]*b[k][j]%mod;
if(c[i][j]>=mod) c[i][j]-=mod;
}
return c;
}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
Mx Pow(Mx a,int b)
{
Mx ans=emp;
for(int i=0;i<n;++i)
ans[i][i]=1;
for(;b;b>>=1,a=a*a)
if(b&1) ans=ans*a;
return ans;
}
int main()
{
n=read(),m=read(),s=read(),t=read(),k=read();
for(int i=1,x,y;i<=m;++i)
x=read(),y=read(),a[x][y]=a[y][x]=1;
for(int i=1;i<=12;++i)
w[i]=a;
nfs=read();
for(int i=1,t;i<=nfs;++i)
{
t=read();
for(int j=0;j<t;++j)
p[j]=read();
for(int j=1;j<=12;++j)
for(int k=0;k<n;++k)
w[j][k][p[j%t]]=0;
}
a=emp;
for(int i=0;i<n;++i)
a[i][i]=1;
for(int i=1;i<=12;++i)
a=a*w[i];
a=Pow(a,k/12);
for(int i=1;i<=k%12;++i)
a=a*w[i];
return printf("%d",a[s][t]),0;
}
