题目
输入一个整数 n ，求斐波那契数列的第 n 项。
假定从0开始，第0项为0。(n<=39)
样例
输入整数 n=5
返回 5

解法

yxc的总结
增加一条结论Sn = fn+2 - 1

// 滚动变量
class Solution {
public:
    int Fibonacci(int n) {
        int a = 0, b = 1;
        while (n--) {
            b = a + b;
            a = b - a;
        }
        return a;
    }
};
// 快速矩阵幂

补充

斐波那契

必须得用快速矩阵幂

#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 1e4;
void mul(int a[2], int f[2][2]) {
    int res[2];
    memset(res, 0, sizeof res);
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++) {
            res[i] = (res[i] + a[j] * f[j][i]) % MOD;
        }
    memcpy(a, res, sizeof res);
}
void mulself(int f[2][2]) {
    int res[2][2];
    memset(res, 0, sizeof res);
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                res[i][j] = (res[i][j] + f[i][k] * f[k][j]) % MOD;
    memcpy(f, res, sizeof res);
}
void fi(int n) {
    int a[2] = {0, 1};
    int f[2][2] = {{0, 1}, {1, 1}};
    while (n) {
        if (n & 1) mul(a, f);
        mulself(f);
        n >>= 1;
    }
    printf("%d\n", a[0] % MOD);
}
int main() {
    int n;
    while (scanf("%d", &n), n != -1) {
        fi(n);
    }
    return 0;
}