记录编号	85265	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2005] 沼泽鳄鱼	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.100 s
提交时间	2013-12-30 21:53:03	内存使用	0.46 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
typedef int ll;
const int SIZEN=51,SIZEF=21;
int MOD=10000;
int N,M,Start,End,K,NFish;//桥墩和石桥数目,起点和终点,一条路线所用时间,鱼的数目
vector<int> P[SIZEF];//鱼的路径信息
class MATRIX{
public:
	int n,m;//n行m列
	ll s[SIZEN][SIZEN];
	MATRIX(){//初始化为零
		m=n=0;
		memset(s,0,sizeof(s));
	}
	void print(void){//调试接口,输出矩阵
		cout<<"size:"<<n<<" "<<m<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) cout<<s[i][j]<<" ";
			cout<<endl;
		}
	}
	void assign_one(int sn){//赋值为sn行的单位矩阵
		n=m=sn;
		for(int i=1;i<=n;i++) s[i][i]=1;
	}
};
MATRIX operator * (MATRIX a,MATRIX b){//矩阵乘法,结果对MOD取模
	MATRIX c;
	c.n=a.n;c.m=b.m;
	int i,j,k;
	for(i=1;i<=c.n;i++){
		for(j=1;j<=c.m;j++){
			c.s[i][j]=0;
			for(k=1;k<=a.m;k++){
				c.s[i][j]+=(a.s[i][k]*b.s[k][j])%MOD;
			}
			c.s[i][j]%=MOD;
		}
	}
	return c;
}
MATRIX quickpow(MATRIX a,ll n){//a^n,sn行/列
	MATRIX ans;ans.assign_one(a.n);
	while(n){
		if(n&1) ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
MATRIX G[13];//G[0]是没有鱼的图
MATRIX GM;//G[1]*...*G[12]
MATRIX F;//转移矩阵
void work(void){
	F.n=1,F.m=N;
	F.s[1][Start]=1;
	int tp=K/12;
	F=F*quickpow(GM,tp);
	tp=K-tp*12;
	for(int i=1;i<=tp;i++) F=F*G[i];
	printf("%d\n",F.s[1][End]);
}
void makegraph(void){
	int i,j,k,x,tot;
	for(i=1;i<=12;i++) G[i]=G[0];
	//G[0].print();
	for(i=1;i<=NFish;i++){
		tot=0;
		for(j=1;j<=12;j++){
			tot++,tot%=P[i].size();
			x=P[i][tot];
			for(k=1;k<=N;k++) G[j].s[k][x]=0;
		}
	}
	GM.assign_one(N);
	for(i=1;i<=12;i++) GM=GM*G[i];
}
void read(void){
	//在输入数据中,桥墩用0~N-1编号
	scanf("%d%d%d%d%d",&N,&M,&Start,&End,&K);
	Start++,End++;
	int i,j,a,b;
	G[0].n=G[0].m=N;
	for(i=1;i<=M;i++){
		scanf("%d%d",&a,&b);
		G[0].s[a+1][b+1]=G[0].s[b+1][a+1]=1;
	}
	scanf("%d",&NFish);
	int T,x;
	for(i=1;i<=NFish;i++){
		scanf("%d",&T);//食人鱼的周期
		for(j=1;j<=T;j++){
			scanf("%d",&x);
			P[i].push_back(x+1);
		}
	}
}
int main(){
	freopen("swamp.in","r",stdin);
	freopen("swamp.out","w",stdout);
	read();
	makegraph();
	work();
	return 0;
}