记录编号	281065	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2005] 沼泽鳄鱼	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.358 s
提交时间	2016-07-11 07:11:06	内存使用	0.49 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
int mod;
inline int add(int a,int b){if(a+b>=mod) return a+b-mod;return a+b;}
inline int mul(int a,int b){return (a*(long long)b)%mod;}
const int maxn = 60;
struct Matrix{
	int a[maxn][maxn];
	int n,m;
	void init(int nt,int mt){
		n=nt; m=mt;
		memset(a,0,sizeof(a));
	}
	void init_0(int lim){
		n = m  = lim;
		memset(a,0,sizeof(a));
		for(int i=1;i<=lim;++i) a[i][i] = 1;
	}
	void print(){
		printf("Matrix %d %d\n",n,m);
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				printf("%d ",a[i][j]);
			}
			printf("\n");
		}
	}
	Matrix operator*(const Matrix &b)const{
		Matrix c;			
		c.n=n;c.m=b.m; 
		for(int i=1;i<=c.n;++i){
			for(int j=1;j<=c.m;++j){
				c.a[i][j] = 0;
				for(int k=1;k<=m;++k){
					c.a[i][j] = add(c.a[i][j], mul(a[i][k],b.a[k][j]));
				}
			}
		}
		return c;
	}
	void operator *= (const Matrix &b){(*this) = (*this)*b;}
	Matrix operator+(const Matrix &b)const{
		Matrix c;
		c.n=n;c.m=b.m;
		for(int i=1,j;i<=n;++i){
			for(j=1;j<=m;j++) c.a[i][j] = add(a[i][j],b.a[i][j]);
		}
		return c;
	}
	void operator += (const Matrix &b){(*this) = (*this)+b;}
	Matrix operator*(const int &x)const{
		Matrix c;
		c.n=n;c.m=m;
		for(int i=1,j;i<=n;++i){
			for(j=1;j<=m;++j)  c.a[i][j] = mul(a[i][j],x);
		}
		return c;
	}
	void operator *=(const int &b){(*this) = (*this)*b;}
	bool operator == (const Matrix &x)const{
		if( n != x.n || m != x.m ) return false;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if( a[i][j] != x.a[i][j] ) return false;
			}
		}
		return true;
	}
}G[15];
// Matrix pow_mod(Matrix x,int p){
// 	Matrix t;
// 	t.init_0(2);
// 	while(p){
// 		if( p & 1 ) t = t*x;
// 		x = x*x;p>>=1;
// 	}
// 	return t;
// }
int N,M,st,ed,K,T;
Matrix pow_mod(Matrix x,int p){
	Matrix ans;
	ans.init_0(N);
	for(;p;p>>=1,x=x*x) if(p & 1) ans=ans*x;
	return ans;
}
inline void read(int &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');
	if( ch == '-' ) ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');
	if( flag ) x=-x;
}
int main(){
//	freopen("data.log","r",stdin);
	freopen("swamp.in","r",stdin);
	freopen("swamp.out","w",stdout);
	mod = 10000;
	read(N);read(M);read(st);read(ed);read(K);
	for(int i=1;i<=12;++i) G[i].init(N,N);
	int x,y;
	for(int i=1;i<=M;++i){
		read(x);read(y);
		++x;++y;
		for(int j=1;j<=12;++j){
			G[j].a[x][y] = G[j].a[y][x] = 1;
		}
	}
	// for(int i=1;i<=12;++i) G[i].print();
	read(T);
	for(int i=1;i<=T;++i){
		read(x);
		for(int j=1;j<=x;++j){
			read(y);++y;
			for(int k=0;k<(12/x);++k){
				int now = k*x;
				for(int t = 1;t<=N;++t){
					G[j+now].a[y][t] = 0;
					//printf("change G[%d].a[%d][%d]\n",j+now,y,t);
				}
			}
		}
	}
//	for(int i=1;i<=12;++i) G[i].print();
	int tmp = K/12;
	Matrix ans,p;
	ans.init_0(N);p.init_0(N);
	
	for(int i=1;i<=12;++i){
//		ans.print();
//		G[i].print();
//		ans.print();
		ans = ans*G[i];
//		G[i].print();
		if( i == (K % 12) ) p = ans;
		
	}
	// printf("--------------\n");
	// printf("tmp = %d\n",tmp);
//	ans.print();
//	p.print();
	ans = pow_mod(ans,tmp)*p;
//	ans.print();
	printf("%d",ans.a[st+1][ed+1]);
//	getchar();getchar();
//	while(1);
	return 0;
}