jiry_2's Blog

就是裸的矩乘，要用快速乘（类似于快速幂）来防止爆INT64。还有要注意在最后的时候答案要先对M取模后再对G取模（坑了我好久）

program p2875;
	type
		arr=array[1..2,1..2] of int64;
	var
		j,k:longint;
		m,a,c,x,n,g,i:int64;
		k1,k2:arr;
	function quick2(k1,k2:int64):int64;
		var
			i,j,k,k3,k4:int64;
		begin
			k:=k2; i:=0;
			while k>0 do begin
				if k and 1>0 then 
					i:=(i+k1) mod m;
				k1:=k1*2 mod m; k:=k div 2;
			end;
			exit(i);
		end;
	function chen(k1,k2:arr):arr;
		var
			i,j,k:longint;
			k3:arr;
		begin
			fillchar(k3,sizeof(k3),0);
			for i:=1 to 2 do
				for j:=1 to 2 do
					for k:=1 to 2 do
						k3[i,j]:=(k3[i,j]+quick2(k1[i,k],k2[k,j]))mod m;
			exit(k3);
		end;
	function quick1(k1:arr;k2:int64):arr;
		var
			j,k:int64;
			i,k3,k4:arr;
		begin
			k:=k2-1; i:=k1;
			while k>0 do begin
				if k and 1>0 then 
					i:=chen(i,k1);
				k1:=chen(k1,k1); k:=k div 2;
			end;
			exit(i);
		end;
	begin
		readln(m,a,c,x,n,g);
		k1[1,1]:=a; k1[1,2]:=1;
		k1[2,1]:=0; k1[2,2]:=1;
		k1:=quick1(k1,n);
		i:=((quick2(k1[1,1],x)+quick2(k1[1,2],c)) mod m)mod g;
		writeln(i);
	end.

如果从一个点到另一个点的时间都是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.

如果没有食人鱼的限制，那么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.