题解 | #Fibonacci（矩阵快速幂法）#

#include<iostream>
#include<cstdio>

using namespace std;

const int MAXN = 10;

struct Matrix {
	int row;
	int col;
	int matrix[MAXN][MAXN];
	Matrix() {}
	Matrix(int r,int c):row(r),col(c) {}
};


Matrix Multiple(Matrix x,Matrix y) {
	Matrix answer = Matrix(x.row,y.col);
	for(int i =0; i < x.row; ++i) {
		for(int j = 0; j < y.col; ++j) {
			answer.matrix[i][j] = 0;
			for(int k = 0; k < x.col; ++k) {
				answer.matrix[i][j] += x.matrix[i][k] * y.matrix[k][j];
			}
		}
	}
	return answer;
}


Matrix QuickPower(Matrix x,int n) {   //x^n
	Matrix answer = Matrix(x.row,x.col);
	for(int i = 0; i < x.row; ++i) {
		for(int j = 0; j < x.col; ++j) {
			if(i == j) {
				answer.matrix[i][j] = 1;
			} else {
				answer.matrix[i][j] = 0;
			}
		}
	}
	while(n != 0) {
		if(n % 2 == 1) {
			answer = Multiple(answer,x);
		}
		n /= 2;
		x = Multiple(x,x);
	}
	return answer;
}


int main() {
	int n;
	while(scanf("%d",&n) != EOF) {
		Matrix fibonacci = Matrix(2,2);
		fibonacci.matrix[0][0] = 1;
		fibonacci.matrix[0][1] = 1;
		fibonacci.matrix[1][0] = 1;
		fibonacci.matrix[1][1] = 0;
		Matrix answer = QuickPower(fibonacci,n);
		printf("%d\n",answer.matrix[0][1]);
	}
	return 0;
}