超级斐波那契数列的计算

super_fibonacci.cpp

// 笔试题目的简单实现
// 请看博客: https://corvo.myseu.cn/2018/04/20/2018-04-20-斐波那契数列的Log(n)解法/

#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <limits.h>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <bitset>
#include <queue>
#include <functional>

using namespace std;


unsigned long long orig_m_mtx[][5] = {
    {2018, 1, 0, 0, 0},
    {2017, 0, 1, 0, 0},
    {2016, 0, 0, 1, 0},
    {2015, 0, 0, 0, 1},
    {2014, 0, 0, 0, 0},
};


const unsigned long long max_div = 1000000003;

unsigned long long mk_rlt(unsigned long long m_mtx[][5]) {
    unsigned long long rlt = 0;
    for(int i = 0; i < 5; i++) {
        rlt += m_mtx[i][0];
        rlt %= max_div;
    }
    return rlt;
}

// m_mtx_tmp = orig_m_mtx * m_mtx
void mk_times(unsigned long long orig_m_mtx[][5], unsigned long long m_mtx[][5],
        unsigned long long m_mtx_tmp[][5]) {
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            m_mtx_tmp[i][j] = 0;
            for(int k = 0; k < 5; k++) {
                m_mtx_tmp[i][j] += orig_m_mtx[i][k] * m_mtx[k][j];
                m_mtx_tmp[i][j] %= max_div;
            }
        }
    }
}


// 将m_mtx进行幂运算, 结果存在m_mtx_tmp中
void mk_twice(unsigned long long m_mtx[][5], unsigned long long m_mtx_tmp[][5]) {
    mk_times(m_mtx, m_mtx, m_mtx_tmp);
}

// 将第二个数组保存在第一个数组里
void save_mtx(unsigned long long m_mtx[][5], unsigned long long m_mtx_tmp[][5]) {
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            m_mtx[i][j] = m_mtx_tmp[i][j];
        }
    }
}


void printMtx(int m_mtx[][5]){
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; j++) {
            cout << m_mtx[i][j] << " ";
        }
        cout << endl;
    }
}


unsigned long long get_rlt(unsigned long long n) {
    if(n < 5) return 1;
    int cur = n - 4;

    unsigned long long m_mtx[5][5];
    unsigned long long m_mtx_tmp[5][5];


    unsigned long long mtx_rlt[5][5] {
        {1, 0, 0, 0, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 0, 0, 1},
    };
    save_mtx(m_mtx, orig_m_mtx);

    while(cur > 0) {
        if(cur % 2 == 1) {
            mk_times(m_mtx, mtx_rlt, m_mtx_tmp);
            save_mtx(mtx_rlt, m_mtx_tmp);
        }
        mk_twice(m_mtx, m_mtx_tmp);
        save_mtx(m_mtx, m_mtx_tmp);
        cur  = cur >> 1;
    }

    return mk_rlt(mtx_rlt);
}



int main()
{
    unsigned long long n;
    cout << get_rlt(100000);
    return 0;
}