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.