基础数学算法-佳佳的斐波那契

题目-佳佳的斐波那契

问题分析

观察式子
$$T(n)=f_1+2f_2+3f_3+...+n{f}_n$$

我们设$P_n=n\cdot S_n-T_n$
那么有
$$P_n=(n-1)f_1+(n-2)f_2+...+f_{n-1}$$

再观察
$$P_{n+1}=n{f}_1+(n-1)f_2+...+2f_{n-1}+f_n$$

注意到, $P_{n+1}-P_n=S_n$

算法步骤

定义矩阵$F_n=[f_n,f_{n+1},S_n,P_n]$

有等式
[ f n + 1 , f n + 2 , S n + 1 , P n + 1 ] = [ f n , f n + 1 , S n , P n ] × [ 0 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 ] [f_{n + 1}, f_{n + 2}, S_{n + 1}, P_{n + 1}] = [f_n, f_{n + 1}, S_n, P_n] \times \begin{bmatrix} 0 & 1 & 0 & 0\\ 1 & 1 & 1 & 0\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 \end{bmatrix} [fn+1​,fn+2​,Sn+1​,Pn+1​]=[fn​,fn+1​,Sn​,Pn​]× ​0100​1100​0110​0011​ ​

那么定义 A = [ 0 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 ] A = \begin{bmatrix} 0 & 1 & 0 & 0\\ 1 & 1 & 1 & 0\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 \end{bmatrix} A= ​0100​1100​0110​0011​ ​, 假设计算出了$F_n$, $T_n=n\cdot S_n-P_n$

代码实现

注意$tmp$的数据类型是$longlong$, 因为最终结果需要$n$, 在快速幂过程中需要另外一个变量$k=n-1$进行计算

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 4;

int n, m;

void mul(LL c[], LL a[], LL b[][N]) {
   
    LL tmp[N] = {
   0};
    for (int i = 0; i < N; ++i) {
   
        for (int j = 0; j < N; ++j) {
   
            tmp[i] = (tmp[i] + a[j] % m * b[j][i] % m) % m;
        }
    }
    memcpy(c, tmp, sizeof tmp);
}

void mul(LL c[][N], LL a[][N], LL b[][N]) {
   
    LL tmp[N][N] = {
   0};
    for (int i = 0; i < N; ++i) {
   
        for (int j = 0; j < N; ++j) {
   
            for (int k = 0; k < N; ++k) {
   
                tmp[i][j] = (tmp[i][j] + a[i][k] % m * b[k][j] % m) % m;
            }
        }
    }
    memcpy(c, tmp, sizeof tmp);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    LL f1[4] = {
   1, 1, 1, 0};
    LL A[4][4] = {
   {
   0, 1, 0, 0},
                  {
   1, 1, 1, 0},
                  {
   0, 0, 1, 1},
                  {
   0, 0, 0, 1}};

    int k = n - 1;
    while (k) {
   
        if (k & 1) mul(f1, f1, A);
        mul(A, A, A);
        k >>= 1;
    }

    LL ans = n * f1[2] - f1[3];
    ans = (ans % m + m) % m;

    cout << ans << '\n';
    return 0;
}