记录编号	361248	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2005] 沼泽鳄鱼	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.181 s
提交时间	2017-01-03 15:40:18	内存使用	5.53 MiB

#include<cstdio>
#include<cstring>
using namespace std;
const int N=110,mod=10000;
int n,m,s,t,k,nfish,cnt,sit[N][N][N];
bool go[N][N],vis[N][N];
struct matrix{
	int a[N][N];
	matrix(){memset(a,0,sizeof a);}
	void operator *= (const matrix x){
		matrix ans;
		for (int i=0;i<n;i++)
		for (int j=0;j<n;j++)
		for (int k=0;k<n;k++)
			(ans.a[i][j]+=a[i][k]*x.a[k][j])%=mod;
		memcpy(a,ans.a,sizeof a);
	}
}x,ans,I;
matrix mi(matrix x,int y){
	matrix ans=I;
	for (;y;y>>=1,x*=x)
		if (y&1) ans*=x;
	return ans;
}
int P(int x,int y){return x*12+y;}
int main()
{
	freopen("swamp.in","r",stdin);
	freopen("swamp.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&m,&s,&t,&k);
	for (int i=0;i<n;i++) I.a[i][i]=1;
	for (int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		go[x][y]=go[y][x]=1;
	}
	scanf("%d",&nfish);
	for (int i=1,T,p;i<=nfish;i++){
		scanf("%d",&T);
		for (int i=0;i<T;i++){
			scanf("%d",&p);
			for (int j=i;j<=12;j+=T) vis[p][j]=1;
		}
	}
	for (int s=0;s<n;s++){
		sit[s][s][0]=1;
		for (int T=0;T<12;T++)
		for (int i=0;i<n;i++)
		for (int j=0;j<n;j++)
		if (go[i][j]&&!vis[j][T+1])
			(sit[s][j][T+1]+=sit[s][i][T])%=mod;
		for (int i=0;i<n;i++)
			x.a[s][i]=sit[s][i][12];
	}
	ans.a[0][s]=1;
	ans*=mi(x,k/12);k%=12;
	int Ans=0;
	for (int i=0;i<n;i++)
		(Ans+=ans.a[0][i]*sit[i][t][k])%=mod;
	printf("%d\n",Ans);
	return 0;
}