斐波那契

AcWing-205-斐波那契

分析

见《进阶指南》第154页。

实现

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

typedef long long LL;
const int N = 2, M = 10000;

void mul (int f[N], int a[N][N]) {
    int res[N];
    memset(res, 0, sizeof(res));
    for (int j = 0; j < N; ++ j)
        for (int k = 0; k < N; ++ k)
            res[j] = (res[j] + (LL)f[k] * a[k][j]) % M;
    memcpy(f, res, sizeof(res));
}
void mul (int a[N][N]) {
    int res[N][N];
    memset(res, 0, sizeof(res));
    for (int i = 0; i < N; ++ i)
        for (int k = 0; k < N; ++ k)
            for (int j = 0; j < N; ++ j)
                res[i][j] = (res[i][j] + (LL)a[i][k] * a[k][j]) % M;
    memcpy(a, res, sizeof(res));
}

int main () {
    int n;
    while (cin >> n && n != -1) {
        int f[N] = { 0, 1 };
        int a[N][N] = { { 0, 1 }, { 1, 1 } };

        while (n > 0) {
            if (n & 1) mul(f, a);
            mul(a);
            n /= 2;
        }
        cout << f[0] << endl;
    }
    return 0;
}