Description：

一个无向图，会循环出现一些点不能在某个时刻到达，周期只可能是 $2,3,4$ ，问从 $s$ 到 $t$ 经过 $k$ 的路径条数。

$1\le n\le 50,1\le k\le2\times 10^9$

Solution：

$lcm(2,3,4)=12$ ，所以先构造 $12$ 个转移矩阵分别对应每个时间，可以先不考虑不能到达构造出一个矩阵，然后把不能到达的点在矩阵中删掉，然后把这 $12$ 个矩阵乘起来，设 $k=i\times 12+j$ ，对于 $i$ 用整个的矩阵算， $j$ 再单独算，之所以这样是因为矩阵乘法没有交换律所以不能把相同的合在一起。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

	

} 

int n,m,s,e,k;

int h;

#define MOD 10000

#define MAXN 51

struct matrix

{

	int m[MAXN][MAXN];

	matrix(){memset(m,0,sizeof(m));}

	void init()

	{

		memset(m,0,sizeof(m));

		for(int i = 1;i <= n;++i)m[i][i] = 1;

		return;

	}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int i = 1;i <= n;++i)

			for(int j = 1;j <= n;++j)

				for(int k = 1;k <= n;++k)

					c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j] % MOD) % MOD;

		return c;

	}

	friend matrix operator ^ (matrix a,int b)

	{

		matrix res;

		if(b == 0)

		{

			res.init();

			return res;	

		}

		res = a;--b;

		while(b > 0)

		{

			if(b & 1)res = res * a;

			a = a * a;

			b = b >> 1;

		}

		return res;

	}

}f[13],tr,res;

bool ava[13][MAXN];

int main()

{

	scanf("%d%d%d%d%d",&n,&m,&s,&e,&k);

	++s;++e;

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		a = read();b = read();

		++a;++b;

		tr.m[a][b] = tr.m[b][a] = 1;

	}

	for(int i = 1;i <= 12;++i)f[i] = tr;

	scanf("%d",&h);

	for(int i = 1;i <= h;++i)

	{

		a = read();

		for(int j = 1;j <= a;++j)

		{

			b = read();++b;

			for(int x = j - 1;x < 12;x += a)

				for(int y = 1;y <= n;++y)

					f[(x - 1 + 12) % 12 + 1].m[y][b] = 0;

		}

	}

	f[0].init();

	for(int i = 1;i <= 12;++i)f[0] = f[0] * f[i];

	int bloc = k / 12,rem = k % 12;

	res = f[0] ^ bloc;

	for(int i = 1;i <= rem;++i)res = res * f[i];

	cout << res.m[s][e] << endl;

	return 0;

}