题目描述

大家都知道 Fibonacci 数列吧，$f _ 1 = 1, f _ 2 = 1, f _ 3 = 2, f _ 4 = 3, \cdots ,f _ n = f _ {n − 1} + f _ {n − 2}$。

现在问题很简单，输入 $n$ 和 $m$，求 $f _ n$ 的前 $n$ 项和 $S _ n \mod m$。

输入格式

共一行，包含两个整数 $n$ 和 $m$。

输出格式

输出前 $n$ 项和 $S _ n\mod m$ 的值。

数据范围

$1 \leq n \leq 2000000000$（别数了，$2 \times 10 ^ 9$）
$1 \leq m \leq 1000000010$（$10 ^ 9 + 10$）

输入样例：

5 1000

输出样例：

12

看数据范围，基本可以肯定是矩阵快速幂了，那么怎么构造矩阵呢？

这里给出一个万能，但较为复杂的矩阵构造方式。

首先推一下公式

$f _ n = f _ {n - 1} + f _ {n - 2}$
$S _ n - S _ {n - 1} = f _ n$
$= f _ {n - 1} + f _ {n - 2}$
$= S _ {n - 1} - S _ {n - 3}$
所以 $S _ n - S _ {n - 1} = S _ {n - 1} - S _ {n - 3}$
$S _ n = 2 \times S _ {n - 1} - S _ {n - 3}$

那么有递推式了，怎么构造矩阵呢？

结论：对于数列 $\{a _ n\}$，若$a _ i = k _ 1 a _ {i - 1} + k _ 2 a _ {i - 2} + \cdots + k _ i a _ 0$，那么
$$ \left[\begin{matrix} k _ 1 & k _ 2 & \cdots & k _ {i - 1} & k _ i \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ \end{matrix}\right] ^ n \left[\begin{matrix} a _ {i - 1} \\ a _ {i - 2} \\ \vdots \\ a _ 1 \\ a _ 0 \\ \end{matrix}\right] = \left[\begin{matrix} a _ {n + i - 1} \\ a _ {n + i - 2} \\ \vdots \\ a _ {n + 1} \\ a _ n \\ \end{matrix}\right] $$

证明：

因为
$$ \left[\begin{matrix} k _ 1 & k _ 2 & \cdots & k _ {i - 1} & k _ i \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a _ {i - 1} \\ a _ {i - 2} \\ \vdots \\ a _ 1 \\ a _ 0 \\ \end{matrix}\right] = \left[\begin{matrix} a _ i \\ a _ {i - 1} \\ \vdots \\ a _ 2 \\ a _ 1 \\ \end{matrix}\right] $$

所以此结论对于 $n = 1$ 成立

假设此结论对于 $n = N$ 成立，那么有
$$ \left[\begin{matrix} k _ 1 & k _ 2 & \cdots & k _ {i - 1} & k _ i \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ \end{matrix}\right] ^ N \left[\begin{matrix} a _ {i - 1} \\ a _ {i - 2} \\ \vdots \\ a _ 1 \\ a _ 0 \\ \end{matrix}\right] = \left[\begin{matrix} a _ {N + i - 1} \\ a _ {N + i - 2} \\ \vdots \\ a _ {N + 1} \\ a _ N \\ \end{matrix}\right] $$

两边同时左乘矩阵
$$ \left[\begin{matrix} k _ 1 & k _ 2 & \cdots & k _ {i - 1} & k _ i \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ \end{matrix}\right] $$

得
$$ \left[\begin{matrix} k _ 1 & k _ 2 & \cdots & k _ {i - 1} & k _ i \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ \end{matrix}\right] ^ {N + 1} \left[\begin{matrix} a _ {i - 1} \\ a _ {i - 2} \\ \vdots \\ a _ 1 \\ a _ 0 \\ \end{matrix}\right] = \left[\begin{matrix} k _ 1 & k _ 2 & \cdots & k _ {i - 1} & k _ i \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a _ {N + i - 1} \\ a _ {N + i - 2} \\ \vdots \\ a _ {N + 1} \\ a _ N \\ \end{matrix}\right] = \left[\begin{matrix} k _ 1 \times a _ {N + i - 1} + k _ 2 \times a _ {N + i - 2} + \cdots + k _ i \times a _ N \\ a _ {N + i - 1} \\ \vdots \\ a _ {N + 2} \\ a _ {N + 1} \\ \end{matrix}\right] = \left[\begin{matrix} a _ {N + i} \\ a _ {N + i - 1} \\ \vdots \\ a _ {N + 2} \\ a _ {N + 1} \\ \end{matrix}\right] $$

所以此结论对于 $n = N$ 也成立。

所以此结论对于任意的 $n \in N ^ +$ 都成立，证毕

由上述结论，可以构造出矩阵
$$ A = \left[\begin{matrix} 2 & 0 & -1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{matrix}\right],\ S = \left[\begin{matrix} S _ 2 \\ S _ 1 \\ S _ 0 \\ \end{matrix}\right] = \left[\begin{matrix} f _ 0 + f _ 1 + f _ 2 \\ f _ 0 + f _ 1 \\ f _ 0 \\ \end{matrix}\right] = \left[\begin{matrix} 2 \\ 1 \\ 0 \\ \end{matrix}\right] $$

找到矩阵之后，用矩阵快速幂求出 $A ^ n$，然后再乘上矩阵 $S$，即可求出 $S _ n$

时间复杂度 $\mathcal O(\log n)$

注：该题矩阵快速幂的时间复杂度虽然是 $\mathcal O(\log n)$，看似能跑的飞快，但实际上还有 $27$ 的常数，并不能跑的飞快，当然过这题毫无压力

$C++$ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

typedef long long ll;

const int N = 3;

int n, m;
ll A[N][N] =    // 上述矩阵 A
{
    {2, 0, -1},
    {1, 0, 0},
    {0, 1, 0}
};
ll S[N] = {2, 1, 0}; // 上述矩阵 S（转置）

void multi(ll A[], ll B[][N]) // 计算方阵 B 乘向量 A，并将结果储存在 A 中
{
    ll ans[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            ans[i] += A[j] * B[i][j] % m;
    for (int i = 0; i < N; i ++ )
        A[i] = ans[i] % m;
}

void multi(ll A[][N], ll B[][N]) // 计算方阵 A * B，并将结果储存在 A 中
{
    ll ans[N][N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
                ans[i][j] += A[i][k] * B[k][j] % m;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            A[i][j] = ans[i][j] % m;
}

int main()
{
    scanf("%d%d", &n, &m);

    while (n)        // 矩阵快速幂
    {
        if (n & 1) multi(S, A);
        multi(A, A);
        n >>= 1;
    }

    printf("%lld", (S[2] % m + m) % m);

    return 0;
}