【矩陣乘法】【快速幂】幼稚園數學題I

Description

某天，幼稚園學生LZH周測數學時吓哭了，一道題都做不出來。這下可麻煩了他馬上就會成為墊底的0分啊。他的期望也不高，做出最簡單的第一題就夠了

題目是這樣的，定義F(n)=((根号5+1)/2)^(n-1) ,當然為了凸顯題目的簡單當然不能是小數分數或無理數,F(x)是以需要向上取整,當然求F(n)是非常難的!是以幼稚園園長頭皮決定簡單一點,求下F(x)的前n項和就行了。

Input

輸入 一個正整數n（保證1<=n<=2^31-1）

Output

輸出 一個正整數S(n) 對1000000007 取餘就好了

Sample Input

樣例輸入1

1
           

樣例輸入2

2
           

Sample Output

樣例輸出1

1
           

樣例輸出2

2
           

Tips

暴力找規律

解題思路

題目不太完整，公式是這個

也就是斐波那契數列和的通項式

和之前一道例題一模一樣

Code

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int Mod = 1000000007;
long long n;

struct DT{
	int n, m;
	long long aed[5][5];
}A, B, Ac;

DT operator *(DT a, DT b){
	DT c;
	c.n = a.n, c.m = b.m;
	memset (c.aed, 0, sizeof (c.aed));
	for (int k = 1; k <= a.m; k++)
		for (int i = 1; i <= c.n; i++)
			for (int j = 1; j <= c.m; j++)
				c.aed[i][j] = (c.aed[i][j] + a.aed[i][k] * b.aed[k][j] % Mod) % Mod;
	return c;
}

void power (long long n){
	if (n == 1)
	{
		Ac = A;
		return;
	}
	power (n / 2);
	Ac = Ac * Ac;
	if (n % 2) Ac = Ac * A; 
}

int main(){
	A.n = A.m = 2;
	A.aed[1][2] = A.aed[2][1] = A.aed[2][2] = 1;
	B.n = 1, B.m = 2;
	B.aed[1][1] = B.aed[1][2] = 1;
	scanf ("%lld", &n);
	power (n + 1);
	B = B * Ac;
	printf ("%lld", B.aed[1][1] - 1);
}