9
7
2013
1

【BZOJ2875】【Noi2012】随机数生成器【矩乘】

就是裸的矩乘,要用快速乘(类似于快速幂)来防止爆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.

 

Category: 矩阵乘法 | Tags: | Read Count: 2435
Avatar_small
Rajasthan Board 10th 说:
2022年8月17日 03:15

The Data Sheet & Question Paper 2023 will be available on the official website in the month of January 2023 for students currently enrolled in classes 10 and 12. After the official release of the RBSE Question Paper 2023, RBSE 10th Exam New Model Paper 2023, RBSE 10th Exam Guess Paper 2023, and RBSE 10th Sample Question Paper 2023, Rajasthan Board 10th Important Question Paper 2023 we will also make it available here on this page for all candidates who are currently enrolled in secondary school or matriculation to quickly download the Rajasthan Board 10th Question Paper 2023. The Board of Secondary Education, often known as RBSE, is the regulatory body for both public and private schools. It has been operated by the Rajasthan Government.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com