jiry_2's Blog

如果从一个点到另一个点的时间都是1那么答案就是邻接矩阵自乘T次时B[1,N]的值，现在既然两点之间时间小于9，那么可以把每个点拆成9个，连成链状，如果I到J的时间为2，那么就由I向倒数第二个J连一条边。这样便可以使邻接矩阵中所有边的权值都为1，那么就可以用快速幂+矩阵乘法做了，要注意非常容易栈溢出。

program p1297;
	type
		arr=array[1..100,1..100] of longint;
	var
		b:array[1..10,1..10] of longint;
		z,x,y,k1,k2:arr;
		t,len,n,i,j,k:longint;
		ch:char;
	function chen(a2:longint):arr;
		var
			i,j,k:longint;
		begin	
			k1:=z; if a2=1 then k2:=z else k2:=x; 
			fillchar(chen,sizeof(chen),0);
			for i:=1 to n do
				for j:=1 to n do
					for k:=1 to n do
						chen[i,j]:=(k1[i,k]*k2[k,j]+chen[i,j]) mod 2009;
		end;
	function quick(k2:longint):arr;
		begin
			if k2=1 then exit(x);
			z:=quick(k2 div 2); z:=chen(1);
			if k2 mod 2=0 then exit(z);
			exit(chen(2));
		end;
	begin
		readln(n,t);
		for i:=1 to n do begin
			for j:=1 to n do begin
				read(ch);
				b[i,j]:=ord(ch)-ord('0');
			end;
			readln;
		end;
		fillchar(x,sizeof(x),0);
		for i:=1 to n do
			for j:=1 to n do begin
				if b[i,j]=0 then continue;
				x[i*9,j*9-b[i,j]+1]:=1;
				for k:=j*9-b[i,j]+2 to j*9 do
					x[k-1,k]:=1;
			end;
		n:=n*9;
		y:=quick(t);
		writeln(y[9,n]);
	end.