题解 | #Fibonacci#

#include <iostream>
#include <cstdio>

using namespace std;

/**
 * 矩阵维数
 */
const int DIMENSION = 2;

/**
 * 矩阵
 */
struct Matrix {
    int row;
    int col;
    int matrix[DIMENSION][DIMENSION];

    Matrix(int row, int col) {
        this->row = row;
        this->col = col;
    }
};

/**
 * 矩阵乘法
 * @param x
 * @param y
 * @return
 */
Matrix multiply(Matrix x, Matrix y);

/**
 * 矩阵求幂
 * @param x
 * @return
 */
Matrix quickPower(Matrix x, int n);

/**
 * 打印矩阵
 * @param x
 */
void printMatrix(Matrix x);


/**
 * Fibonacci--上海交通大学
 * @return
 */
int main() {
    int n;
    while (cin >> n) {
        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 power = quickPower(fibonacci, n);
        Matrix tmp = Matrix(2, 1);
        tmp.matrix[0][0] = 1;
        tmp.matrix[1][0] = 0;
        Matrix ans = multiply(power, tmp);
        /*
         * 可以打印矩阵进行验证
         */
        //printMatrix(ans);
        cout << ans.matrix[1][0] << endl;

    }

    return 0;
}

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

Matrix quickPower(Matrix x, int n) {
    Matrix ans = Matrix(x.row, x.col);
    for (int i = 0; i < ans.row; ++i) {
        for (int j = 0; j < ans.col; ++j) {
            if (i == j) {
                ans.matrix[i][j] = 1;
            } else {
                ans.matrix[i][j] = 0;
            }
        }
    }

    while (n != 0) {
        if (n % 2 == 1) {
            ans = multiply(ans, x);
        }
        n = n >> 1;
        x = multiply(x, x);
    }

    return ans;
}

void printMatrix(Matrix x) {
    for (int i = 0; i < x.row; ++i) {
        for (int j = 0; j < x.col; ++j) {
            if (j == 0) {
                cout << x.matrix[i][j];
            } else {
                cout << " " << x.matrix[i][j];
            }
        }
        cout << endl;
    }
}