3070 fibonacci.txt

Pku 3070 Fabbonacci矩阵乘法解法c++代码

#include <iostream>
using namespace std;


const int MAX = 10000;
const int MaxMatrixSize=2;//NOTES:MaxMatrixSize

typedef long long int64;//NOTES:int64

template<class T> inline T multiplyMod(T a,T b,T m) {return (T)((((int64)(a)*(int64)(b)%(int64)(m))+(int64)(m))%(int64)(m));}//NOTES:multiplyMod(

template<class T> inline void mulModMatrix(int n,T m,T C[MaxMatrixSize][MaxMatrixSize],T _A[MaxMatrixSize][MaxMatrixSize],T _B[MaxMatrixSize][MaxMatrixSize])//NOTES:mulModMatrix(
  { T A[MaxMatrixSize][MaxMatrixSize],B[MaxMatrixSize][MaxMatrixSize];
  for (int i=0;i<n;i++) for (int j=0;j<n;j++) A[i][j]=_A[i][j],B[i][j]=_B[i][j],C[i][j]=0;
  for (int i=0;i<n;i++) for (int j=0;j<n;j++) for (int k=0;k<n;k++) C[i][j]=(C[i][j]+multiplyMod(A[i][k],B[k][j],m))%m;}


template<class T> inline void show(int n,T A[MaxMatrixSize][MaxMatrixSize])//NOTES:mulMatrix(
  {
  for (int i=0;i<n;i++,cout<<endl) for (int j=0;j<n;j++) cout<<A[i][j]<<" ";}



int A[2][2];
int B[2][2];
int C[2][2];
int D[2][2];

void pow(int a[2][2],int n,int ret[2][2])
{
	if (n<=1)
	{
		for (int i = 0;i<2;i++) for (int j = 0;j<2;j++) ret[i][j] = a[i][j];
		return;
	}

	if ((n&1))
	{
		pow(a,n-1,ret);
		mulModMatrix(2,MAX,ret,ret,a);	
	}
	else
	{	
		pow(a,n/2,ret);	
		mulModMatrix<int>(2,MAX,ret,ret,ret);	
	}
}


int main()
{
	A[0][0] = 1;
	A[0][1] = 1;
	A[1][0] = 1;
	A[1][1] = 0;

	int input;
	while(1)
	{
		scanf("%d",&input);
		if(input==-1)
		{
			break;
		}
		if(!input)
			printf("0\n");
		else
		{
			pow(A,input,D);
			printf("%d\n",D[0][1]);	
		}
	}

	return 0;
	
}