P2579 [ZJOI2005]沼泽鳄鱼

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int read(){
    char ch=getchar(); int w=1,c=0;
    for (;!isdigit(ch);ch=getchar()) if (ch==‘-‘) w=-1;
    for (;isdigit(ch);ch=getchar()) c=(c<<3)+(c<<1)+(ch^48);
    return w*c;
}
const int mod=10000;
int n,m,S,E,K,P;
struct Matrix{
    int a[51][51];
    Matrix (){memset(a,0,sizeof a); }
    Matrix operator *(const Matrix &b) const {
        Matrix ret;
        for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
        for (int k=0;k<n;k++)
        ret.a[i][j]=(ret.a[i][j]+a[i][k]*b.a[k][j])%mod;
        return ret;
    }
}g[12],base,o,ans;
int main(){
    n=read(); m=read(); S=read(); E=read(); K=read();
    for (int i=1;i<=m;i++){
        int x=read(),y=read();
        o.a[x][y]=o.a[y][x]=1;
    }
    for (int i=0;i<12;i++) g[i]=o;
    P=read();
    while (P--){
        int T=read();
        for (int i=0;i<T;i++){
            int x=read();
            for (int j=i;j<12;j+=T){
                for (int k=0;k<n;k++)
                g[j].a[k][x]=0;
            }
        }
    }
    base=g[1];
    for (int i=2;i<12;i++) base=base*g[i];
    base=base*g[0];
    for (int i=0;i<n;i++) ans.a[i][i]=1; 
    int nn=K/12;
    for (;nn;nn>>=1,base=base*base)
    if (nn&1) ans=ans*base;
    for (int i=1;i<=K%12;i++) ans=ans*g[i];
    cout<<ans.a[S][E]<<"\n";
    return 0;
}