杭电oj3306：Another kind of Fibonacci（矩阵快速幂）

Another kind of Fibonacci

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

As we all known , the Fibonacci series : F(0) = 1, F(1) = 1, F(N) = F(N - 1) + F(N - 2) (N >= 2).Now we define another kind of Fibonacci : A(0) = 1 , A(1) = 1 , A(N) = X * A(N - 1) + Y * A(N - 2) (N >= 2).And we want to Calculate S(N) , S(N) = A(0)^2 +A(1)^{2+……+A(n)}2.

Input

There are several test cases.

Each test case will contain three integers , N, X , Y .

N : 2<= N <= 2^31 – 1

X : 2<= X <= 2^31 – 1

Y : 2<= Y <= 2^31 – 1

Output

For each test case , output the answer of S(n).If the answer is too big , divide it by 10007 and give me the reminder.

Sample Input

2 1 1

3 2 3

Sample Output

6

196

思路见下图:

#include<iostream>

#include<cstring>

using namespace std;

const int maxn = 5;

typedef long long LL;

struct Matrix{

	int matrix[maxn][maxn];

}ori, ans;

int n = 4, N, X, Y, m = 10007;

void init()

{

	for(int i=0;i<n;i++)

		for(int j=0;j<n;j++)

			ori.matrix[i][j] = ans.matrix[i][j] = 0;

	ori.matrix[0][0] = ori.matrix[2][1] = 1;

	ori.matrix[0][1] = ori.matrix[1][1] = X * X % m;

	ori.matrix[0][2] = ori.matrix[1][2] = Y * Y % m;

	ori.matrix[0][3] = ori.matrix[1][3] = ((2 * X) % m) * Y % m;

	ori.matrix[3][1] = X;

	ori.matrix[3][3] = Y;

	ans.matrix[0][0] = 2;

	ans.matrix[1][0] = ans.matrix[2][0] = ans.matrix[3][0] = 1;

}

Matrix multiply(Matrix a, Matrix b)

{

	Matrix temp;

	memset(temp.matrix, 0, sizeof(temp.matrix));

	for(int i=0;i<n;i++)

		for(int j=0;j<n;j++)

			for(int k=0;k<n;k++)

				temp.matrix[i][j] = (temp.matrix[i][j] + ((a.matrix[i][k] * b.matrix[k][j]) % m)) % m;

	return temp;

}

//矩阵的b次幂

Matrix binaryPow(int b)

{

	Matrix temp;

	memset(temp.matrix, 0, sizeof(temp.matrix));

	for(int i=0;i<n;i++)

		temp.matrix[i][i] = 1;

	while(b > 0)

	{

		if(b & 1)

			temp = multiply(ori, temp);

		ori = multiply(ori, ori);

		b >>= 1;

	}

	return temp;

}

int main()

{

	//freopen("in.txt","r", stdin);

	while(cin>>N>>X>>Y)

	{

		X %= m;

		Y %= m;

		init();

		Matrix temp = binaryPow(N - 1);

		ans = multiply(temp, ans);

		cout<<ans.matrix[0][0]<<endl;

	}

	return 0;

}

巴特西

杭电oj3306：Another kind of Fibonacci（矩阵快速幂）

Another kind of Fibonacci

最新文章

热门文章