Fibonacci 前 n 项和

矩阵乘法 T3 斐波那契

题目描述

大家都知道 $Fibonacci$ 数列吧，$f_1=1,f_2=1,f_3=2,f_4=3,\dots ,f_n=f_{n-1}+f_{n-2}$。

现在问题很简单，输入 $n$ 和 $m$，求 $\{f_n\}$ 的前 $n$ 项和 $S_n\mathrm{mod}m$。

输入格式

输入 $n,m$。

输出格式

输出前 $n$ 项和 $S_n\mathrm{mod}m$。

样例

输入

5 1000

输出

12

数据范围与提示

对于 $100\%$ 的数据，$1\le n\le 2\times 10^9,1\le m\le 10^9+10$。

思路

求第 n 项的值时, 可以用矩阵快速幂来求, 把求 $f_n$ 转换为 $A^n$ 的形式。

定义一个向量 $F_n=[f_n,f_{n+1}]$, 求 $F_{n+1}=F_n\times A$ 中满足条件的 $A$。即满足 $[f_n,f_{n+1}]\times A=[f_{n+1},f_{n+2}]$ 那么 $A$ 就是：$\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]$ 所得结果就是 $[f_n\times 0+f_{n+1}\times 1,f_n\times 1+f_{n+1}\times 1]$ , 而 $f_{n+2}=f_{n+1}+f_n$, 故 $A$ 满足条件。

因此 $F_n$ 就用 $F_n=F_0\times A^n$ 来求得, 虽然矩阵乘法不满足交换律, 但满足结合律, 因此可以用快速幂解决。 算 $A^5$ 时拆分为 $A^1\times A^4$ 等等。

而这里是让求前 n 项和, 我们需要构造一个能算出答案的矩阵。

考虑把答案也放到向量中, 定义 $F_n=[f_n,f_{n+1},S_n]$, $S_n$ 即前 n 项的和, 而 $F_{n+1}=[f_{n+1},f_{n+2},S_{n+1}]$。 构造矩阵 $A$ ：$$ \begin{bmatrix} 0&1&0 \ 1&1&1 \ 0&0&1 \end{bmatrix}

乘积为 $[f_{n+1}, f_{n}+f_{n+1}, f_{n+1}+S_{n}]$, 而 $S_{n+1} = S_{n} + f_{n+1}$。 最终时间复杂度为 $O(\log n)$。 ## 代码 ```c++ #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 3; LL n, m; void mul(LL c[], LL a[], LL b[][N]) { LL temp[N] = {}; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) temp[i] = (temp[i] + (LL)a[j] * b[j][i] % m) % m; memcpy(c, temp, sizeof temp); } void mul(LL c[][N], LL a[][N], LL b[][N]) { LL temp[N][N] = {}; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j] % m) % m; memcpy(c, temp, sizeof temp); } void solve() { cin >> n >> m; LL f1[N] = {1, 1, 1}; LL a[N][N] = { {0, 1, 0}, {1, 1, 1}, {0, 0, 1}}; n--; while (n) { if (n & 1) mul(f1, f1, a); mul(a, a, a); n >>= 1; } cout << f1[2] << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; } ```