记录编号	128172	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2005] 沼泽鳄鱼	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.156 s
提交时间	2014-10-16 21:34:10	内存使用	1.21 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define Mod 10000LL
using namespace std;
int N,M,st,en,K,nfish;
vector<int> fish[101];
class Matrix{
	public:
	int ele[101][101],n,m;
	Matrix(){n=0;m=0;memset(ele,0,sizeof(ele));}
	Matrix operator*(const Matrix a)const{
		Matrix c;
		c.n=n; c.m=a.m;
		for(int i=1;i<=c.n;i++)
			for(int j=1;j<=c.m;j++)
				for(int k=1;k<=m;k++)
				{
					c.ele[i][j]+=ele[i][k]*a.ele[k][j];
					c.ele[i][j]%=Mod;
				}
		return c;
	}
	void empty(int N){
		n=N; m=N;
		for(int i=1;i<=N;i++) ele[i][i]=1;
	}
	void print(){
		cout<<"size"<<n<<' '<<m<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cout<<ele[i][j]<<' ';
			}
			cout<<endl;
		}
	}
} G[21];
Matrix pow(Matrix a,long long n){
	Matrix res; res.empty(a.n);
	for(;n;n>>=1,a=a*a) if(n&1) res=res*a;
	return res;
}
void init(){
	int x,y,T;
	cin>>N>>M>>st>>en>>K;
	st++; en++;
	G[0].n=N,G[0].m=N;
	for(int i=1;i<=M;i++){
		cin>>x>>y;
		G[0].ele[x+1][y+1]=1;
		G[0].ele[y+1][x+1]=1;
	}
	cin>>nfish;
	for(int i=1;i<=nfish;i++){
		cin>>T;
		for(int j=1;j<=T;j++){
			cin>>x;
			fish[i].push_back(x+1);
		}
	}
	for(int t=1;t<=12;t++){
		G[t]=G[0];
		for(int i=1;i<=nfish;i++){
			int tmp=fish[i][t%fish[i].size()];
			for(int j=1;j<=N;j++){
				G[t].ele[j][tmp]=0;
			}
		}
	}
	G[13].empty(N);
	for(int i=1;i<=12;i++) G[13]=G[13]*G[i];
}
int main(){
	freopen("swamp.in","r",stdin);
	freopen("swamp.out","w",stdout);
	init();
	int p=K/12;
	Matrix Ans;
	Ans.n=1; Ans.m=N;Ans.ele[1][st]=1;
	Ans=Ans*pow(G[13],p);
	for(int i=1;i<=K-p*12;i++) Ans=Ans*G[i];
	cout<<Ans.ele[1][en]<<endl;
	return 0;
}