学步园

    《编程之美》上有一篇文章专门讲解斐波那契递推式的计算。当n特别大的时候，譬如10^9仍然用递推求解显然不妥。但是巧妙的将递推式计算转换成矩阵的幂运算之后，可以利用分治法高效的求幂运算，从而将O（n）转换成了O(log(n))的时间复杂度。证明题目已经给出，我们需要做的仅仅是将矩阵的幂运算代码实现。

     我用了运算符重载实现矩阵的乘法运算。

     题目URL：http://poj.org/problem?id=3070

     我的AC代码。

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;

struct Matrix
{
	int d[2][2];

	Matrix()
	{
		memset(d, 0, sizeof(d));
	}

	void make()
	{
		d[0][0] = d[0][1] = d[1][0] = 1;
		d[1][1] = 0;
	}

	friend Matrix operator *(Matrix a, Matrix b)
	{
		Matrix m;

		for(int r=0; r<2; r++)
			for(int c=0; c<2; c++)
			{
				for(int i=0; i<2; i++) 
					m.d[r][c] = m.d[r][c] + a.d[r][i] * b.d[i][c];
				m.d[r][c] %= 10000;
			}
		return m;
	} 
};

Matrix power(Matrix m, int n)
{
	Matrix r;
	Matrix f;
	f.make();
	r.d[0][0] = r.d[1][1] = 1;

	for(; n; n>>=1)
	{
		if(n & 1)
		{
			r = r * f;
		}
		f = f * f;
	}
	return r;
}

int main()
{
	int n;
	Matrix a, r;

	while(scanf("%d", &n) && n != -1)
	{
		if(!n) printf("0\n");
		else
		{
			a.make();
			r = power(a, n);
			printf("%d\n", r.d[0][1]);
		}
	}

	system("pause");
	return 0;
}