游客 注册 | 登录
中文 | En

3262 - 鳄鱼

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

在观看完各种动物后，有一部分MM 由于没有看到自己喜欢的动物而很生气，她们把绝恋扔在一边自己去玩了，绝恋正在纠结，忽然听到MM 的呼救声，天赐良机！！

绝恋发现，MM 们被困在鳄鱼馆的角落里了，鳄鱼馆其实就是一个大池塘，中间建设了许多的石墩和石桥，且每两座石墩之间至多只有一座石桥。池塘中有许多鳄鱼。绝恋及时赶到鳄鱼馆营救MM，但也不敢拿自己的性命开玩笑，于是他开始了仔细的实地勘察，并得到了一些惊人的结论：鳄鱼的行进路线有周期性，这个周期只可能是2，3 或者4 个单位时间。每个单位时间里，鳄鱼可以从一个石墩游到另一个石墩。每到一个石墩，如果上面有人它就会实施攻击，否则继续它的周期运动。如果没有到石墩，它是不会攻击人的。

借助先进的仪器，绝恋很快就摸清了所有鳄鱼的运动规律，他要开始设计自己的行动路线了。每个单位时间里，他只可以沿着石桥从一个石墩走到另一个石墩，而不可以停在某座石墩上不动，因为站着不动还会有其它危险。如果绝恋和某条鳄鱼在同一时刻到达了某座石墩，就会遭到鳄鱼的袭击，他当然不希望发生这样的事情。

绝恋开始在start 石墩上，而MM 们被困在end 石墩上，绝恋要从start 出发，恰好经过Step 个单位时间后到达end 石墩，石墩可以重复经过(包括start 和nd)，绝恋希望你能告诉他绝恋有多少条满足上述条件的路线，以便计算成功救出MM的几率。

题目输入

第一行包含五个正整数N，M，Start，End 和Step，分别表示石墩数目、石桥数目、Start 石墩和End 石墩的编号和一条路线所需的单位时间。石墩用0 到N–1 的整数编号。

第2 到M + 1 行，给出石桥的相关信息。每行两个整数x 和y，0 ≤ x, y ≤ N–1，表示这座石桥连接着编号为x 和y 的两座石墩。

第M + 2 行是一个整数NFish，表示鳄鱼的数目。

第M + 3 到M + 2 + NFish 行，每行给出一条鳄鱼的相关信息。每行的第一个整数是T，T = 2，3 或4，表示鳄鱼的运动周期。接下来有T 个数，表示一个周期内鳄鱼的行进路线。

题目输出

输出路线的种数，因为这个数可能很大，你只要输出该数除以10000 的余数就行了。

输入/输出样例

输入格式

6 8 1 5 3
0 2
2 1
1 0
0 5
5 1
1 4
4 3
3 5
1
3 0 5 1

输出格式

2

C++解答

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define Mod 10000
#define Maxn 101
using namespace std;
int N,M,st,en,step,nfish;
vector<int> fish[Maxn];
class Matrix{
	public:
	int ele[Maxn][Maxn],n,m;
	Matrix(){
		n=0;m=0;
		memset(ele,0,sizeof(ele));
	}
	Matrix operator*(const Matrix a){
		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<=a.m;k++){
					c.ele[i][j]+=ele[i][k]*a.ele[k][j];
					c.ele[i][j]%=Mod;
				}
		return c;
	}
	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;
		}
	}
	void empty(int N){
		n=N; m=N;
		for(int i=1;i<=N;i++) ele[i][i]=1;
	}
} G[21],Gr;
Matrix Pow(Matrix a,long long n){
	Matrix res; res.empty(N);
	for(;n;n>>=1,a=a*a) if(n&1) res=res*a;
	return res;
}
void work(){
	int p=step/12;
	Matrix Ans;
	Ans.n=1; Ans.m=N; Ans.ele[1][st]=1;
	Ans=Ans*Pow(Gr,p);
	for(int i=1;i<=step-12*p;i++) Ans=Ans*G[i];
	cout<<Ans.ele[1][en]%Mod<<endl;
}
void init(){
	int x,y;
	cin>>N>>M>>st>>en>>step;
	st++; en++;
	G[0].n=N; G[0].m=N;
	for(int i=1;i<=M;i++){
		cin>>x>>y;
		G[0].ele[y+1][x+1]=1;
		G[0].ele[x+1][y+1]=1;
	}
	int T;
	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=t%fish[i].size();
			for(int j=1;j<=N;j++){
				G[t].ele[j][fish[i][tmp]]=0;
			}
		}
	}
	Gr=G[1];
	for(int i=2;i<=12;i++) Gr=Gr*G[i];
}
int main(){
	init();
	work();
	return 0;
}
请先登陆