记录编号	590949	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2005] 沼泽鳄鱼	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.247 s
提交时间	2024-07-13 17:29:22	内存使用	3.83 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#define mod 10000
using namespace std;
int n,m,S,T,tim,nf,cnt;
int map[60][60];
int vis[60][13];
typedef struct matrix
{
    int v[60][60];
}M;
M x,ans,f[13],emp;
M mmul(M a,M b)
{
    M c=emp;
    int i,j,k;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
                c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j])%mod;
    return c;
}
void pm(M x,int y)
{
    while(y)
    {
        if(y&1) ans=mmul(ans,x);
        x=mmul(x,x),y>>=1;
    }
}
int main()
{
    freopen("swamp.in","r",stdin);
    freopen("swamp.out","w",stdout);
    scanf("%d%d%d%d%d",&n,&m,&S,&T,&tim),S++,T++;
    int i,j,k,l,x,y,a,b;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b),a++,b++;
        map[a][b]=map[b][a]=1;
    }
    scanf("%d",&nf);
    for(i=1;i<=nf;i++)
    {
        scanf("%d",&a);
        for(j=0;j<a;j++)
        {
            scanf("%d",&b),b++;
            for(k=0;k<12;k+=a)   vis[b][k+j]=1;
        }
    }
    for(i=1;i<=n;i++)    f[12].v[i][i]=ans.v[i][i]=1;
    for(k=0;k<12;k++)
    {
        for(i=1;i<=n;i++)    if(!vis[i][k])
            for(j=1;j<=n;j++)    if(!vis[j][(k+1)%12]&&map[i][j])
                f[k].v[i][j]=1;
        f[12]=mmul(f[12],f[k]);
    }
    pm(f[12],tim/12);
    for(i=0;i<tim%12;i++)    ans=mmul(ans,f[i]);
    printf("%d",ans.v[S][T]);
    return 0;
}