초학 매트릭스 곱셈 - 피 폴 라 치 수열

최근 에 WerKeyTom 을 들 었 어 요.FTD 의 설명 이자 행렬 곱셈 에 대해 알 게 되 었 습 니 다. 여기 서 정리 하 겠 습 니 다.
간단 한 인식:
설정 A = m * p, B = p * n, A * B = C (m * n), C [i, j] = ∑ A [i, k] * B [k, j] (1 < = k < = p)
피 폴 라 치 수열:
f (x) 를 피 폴 라 치 수열 의 x 항 으로 설정 하고 f (1) = 0, f (2) = 1, f (x) = f (x - 1) + f (x - 2), f (n) 를 구하 십시오.(1<=n<=10^9)。답 은 10 ^ 9 + 7 모형 을 취한 다.
분석:
분명 한 것 은 직접 구 하 러 가면 시간 은 O (n) 이 고 10 ^ 9 를 받 아들 일 수 없다 는 것 이다.
중학교 1 학년 때 저 는 아직 젊 어서 행렬 곱셈 을 할 줄 몰 랐 습 니 다. 그래서 저 는 초고 에 그림 을 그리고 그림 을 그 렸 습 니 다. 마침내 피 폴 라 치 수열 에 신기 한 규칙 이 있 음 을 발 견 했 습 니 다.
우리 먼저 피 폴 라 치 수열 을 보 자.
0,1,1,2,3,5,8,13,21,34,55,89……
분명히 있다
89
=34*1+55*1
=21*1+34*2
=13*2+21*3
=8*3+13*5
=…
우 리 는 세로 로 두 번 째 열 과 네 번 째 열 곱 수 를 보면 그들 은 또 하나의 피 폴 라 치 수열 이라는 것 을 알 수 있다. 정 리 를 통 해 얻 을 수 있다. f [n] = f [n - i] * f [i] + f [n - i + 1] * f [i + 1]
그럼 우리 각 도 를 바 꿔 서 생각해 보 자.
알 겠 습 니 다.
f [x], f [x + 1] 와 f [y], f [y + 1], f [y + 2]
알 수 있어 요.
f[x+y]=f[x]*f[y]+f[x+1]*f[y+1]，
알 수 있다
f[x+y+1]=f[x]*f[y+1]+f[x+1]*f[y+2]
그리고 새로 얻 은 f [x + y], f [x + y + 1] 로 f [x + y + y], f [x + y + 1 + y] 의 값 을 밀어 내 면 f [n] 의 값 을 얻 을 수 있다.
f [y], f [y + 1], f [y + 2] 는 상수 로 보고 미리 구한다.
시간 복잡 도 O (y + n / y)
그리고 마지막 질문: y =?y + n / y 가 가장 작다.
사실 y = √ n 일 때 y + n / y 가 가장 작다.
처음에는 나 도 할 줄 몰 랐 다. 그래서 수학 선생님 인 Mrs. chen 에 게 물 어 보 았 다. 초 는 알 았 다.즉시 증명:
우 리 는 평균치 부등식 이 있다 는 것 을 안다.
a+b>=2√ab(a,b>=0)
그렇게
y+n/y>=2√y(n/y)
        >= 2√n
분명 하 다. y = n / y, y = √ n, (a = b) 일 때 y + n / y (a + b) 의 값 만 최소 치 2 √ n (2 √ ab) 을 취 할 수 있다.   
그래서 시간 복잡 도 는 O (√ n) 입 니 다.
우리 본론 으로 들 어가 자.
[f[x],f[x+1]]*[...]=[f[x+1],f[x+2]]
이동 행렬 (유 매트릭스) 을 쉽게 내 놓 을 수 있 습 니 다.
[0,1]
[1,1]
행렬 곱셈 은 결합 성 이 있 기 때문에 미리 친구 행렬 에 곱셈 을 할 수 있 고 행렬 의 빠 른 멱 을 사용 하여 O (log n) 에서 해결 할 수 있 습 니 다.
코드:

type
	arr=array[1..2,1..2] of int64;
const
        mo=100000007;
var
	n,i,j,k:longint;
	a,b:arr;
procedure cheng(var a:arr;b:arr);
var c:arr;
begin
        c:=a;
	for i:=1 to 2 do
		for j:=1 to 2 do
		begin
			a[i,j]:=0;
			for k:=1 to 2 do
				a[i,j]:=(a[i,j]+c[i,k]*b[k,j]) mod mo;
		end;
end;
begin
	readln(n);
	if n=1 then
	begin
		writeln(0); halt;
	end;
	a[1,1]:=0; a[1,2]:=1; a[2,1]:=1; a[2,2]:=1;
	b:=a;
	n:=n-2;
	while n>0 do
	begin
		if n and 1=1 then cheng(a,b);
		n:=n>>1; cheng(b,b);
        end;
        writeln(a[1,2]);
end.