由于

an = an-1 + an-2

所以

an = (1, 1)(an-2, an-1)T

an-1 = (0, 1)(an-2, an-1)T

所以，有变换矩阵

matrix = ((0, 1), (1, 1))

使得

matrix * (an-2, an-1)T = (an-1, an)T

可以观察到，若a0=0，则matrix也可表示为 ((a0, a1), (a1, a2))。

于是构造初始矩阵ret为单位矩阵，经过n次变换ret[0][1]将表示an：

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > matrix_mul(vector<vector<int> > m1,
                                vector<vector<int> >m2) {
    vector<vector<int> > tmp = {
        {1, 0},
        {0, 1}
    };
    tmp[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
    tmp[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
    tmp[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
    tmp[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];
    return tmp;
}

int main() {
    int n;
    scanf("%d", &n);
    vector<vector<int> > matrix = {
        {0, 1},
        {1, 1}
    };
    vector<vector<int> > ret = {
        {1, 0},
        {0, 1}
    };
    while (n) {
        if (n & 1) {
            ret = matrix_mul(matrix, ret);
        }
        matrix = matrix_mul(matrix, matrix);
        n >>= 1;
    }
    printf("%d\n", ret[0][1]);
}