jiry_2's Blog

如果没有食人鱼的限制，那么K秒后的方案数就是邻接矩阵自乘K次后的B[S,E]，那么有了限制之后我们可以知道邻接矩阵一定以12个单位时间周期性变化。比如在第i个时刻第j个点上有鳄鱼。那么把第i-1时刻的矩阵中[1..n][j]置零，第i时刻的矩阵中[j][1..n]置零。很好想通。那么K/12的用快速幂。K%12的暴力求。

program p1898;
	const
		num=10000;
	type
		arr=array[1..50,1..50] of longint;
	var
		x:array[0..11] of arr;
		b,y,z:arr;
		f:array[1..20,0..4] of longint;
		n,i,j,m,s,e,k,k1,k2,nf:longint;
	function chen(k1,k2:arr):arr;
		var
			i,j,k:longint;
			k3:arr;
		begin
			fillchar(k3,sizeof(k3),0);
			for i:=1 to n do
				for j:=1 to n do
					for k:=1 to n do
						k3[i,j]:=(k1[i,k]*k2[k,j]+k3[i,j]) mod num;
			exit(k3);
		end;
	function quick(k1:arr;k2:longint):arr;
		var
			i,j:longint;
			k3:arr;
		begin
			if k2=0 then begin
				fillchar(k3,sizeof(k3),0);
				for i:=1 to n do
					k3[i,i]:=1;
				exit(k3);
			end;
			if k2=1 then exit(k1);
			k3:=quick(k1,k2 div 2);
			if k2 mod 2=0 then exit(chen(k3,k3));
			exit(chen(chen(k3,k3),k1));
		end;
	begin
		readln(n,m,s,e,k);
		fillchar(b,sizeof(b),0);
		for i:=1 to m do begin
			readln(k1,k2);
			b[k1+1,k2+1]:=1;
			b[k2+1,k1+1]:=1;
		end;
		readln(nf);
		for i:=1 to nf do begin
			read(f[i,0]);
			for j:=1 to f[i,0] do begin
				read(f[i,j]);
				inc(f[i,j]);
			end;
		end;
		for i:=0 to 11 do
			x[i]:=b;
		for i:=1 to nf do
			for k1:=0 to 11 do begin
				for k2:=1 to n do
					x[k1,k2,f[i,(k1+1) mod f[i,0]+1]]:=0;
				for k2:=1 to n do
					x[k1,f[i,k1 mod f[i,0]+1],k2]:=0;
			end;
		z:=x[0];
		for i:=1 to 11 do
			z:=chen(z,x[i]);
		y:=quick(z,k div 12);
		for i:=0 to k mod 12-1 do
			y:=chen(y,x[i]);
		writeln(y[s+1,e+1]);
	end.