使用矩陣快速冪優化遞推問題

對于一個遞推問題，如遞推式的每一項系數都為常數，我們可以使用矩陣快速冪來對算法進行優化。
一般形式為：
$F_n=F_1\times A^{n?1}$
由于遞推式的每一項系數都為常數，因此對于每一步的遞推，$A$里面都是相同的常數。
對于$A^{n?1}$部分使用快速冪求解，根據$F_n$就能得到最終答案。

矩陣快速冪：

void mul(int c[][N], int a[][N], int b[][N])
{int temp[N][N] = {0};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);
}
while (k){if (k & 1) mul(f, f, a);mul(a, a, a);k >>= 1;}

斐波那契數列的前n項和

大家都知道 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(modm)$。

輸入格式

共一行，包含兩個整數$n$ 和 $m$。

輸出格式

輸出前 $n$ 項和 $S_n(modm)$ 的值。

數據范圍
$1\le n\le 2000000000,$
$1\le m\le 1000000010$

輸入樣例：

5 1000

輸出樣例：

12

我們有遞推關系:
$f_n=f_{n?1}+f_{n?2}$
$S_n=S_{n?1}+f_n$
設$F_n=[f_n,f_{n+1},S_n]$，有$F_n\times A=F_{n+1}$，根據遞推關系求解矩陣$A$。
$[f_n,f_{n+1},S_n]\times \left[\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right]=[f_{n+1},f_{n+2},S_{n+1}]$

求解得到$A=\left[\begin{array}{ccc}0& 1& 0\\ 1& 1& 1\\ 0& 0& 1\end{array}\right]$

$F_1=[1,1,1]$，最終答案為$F_1\times A^{n?1}$，對于$A^{n?1}$部分采用快速冪來計算，時間復雜度為$O(logn?3^3)$。

佳佳的斐波那契

佳佳對數學，尤其對數列十分感興趣。

在研究完 Fibonacci 數列后，他創造出許多稀奇古怪的數列。

例如用 $S(n)$ 表示 Fibonacci 前 $n$ 項和 $modm$ 的值，即 $S(n)=(F_1+F_2+\dots +F_n)modm$，其中 $F_1=F_2=1,F_i=F_{i?1}+F_{i?2}$。

可這對佳佳來說還是小菜一碟。

終于，她找到了一個自己解決不了的問題。

用 $T(n)=(F_1+2F_2+3F_3+\dots +n{F}_n)modm$ 表示 Fibonacci 數列前 $n$ 項變形后的和 $modm$ 的值。

現在佳佳告訴你了一個 $n$ 和 $m$，請求出 $T(n)$的值。

輸入格式

共一行，包含兩個整數 $n$ 和 $m$。

輸出格式

共一行，輸出 $T(n)$ 的值。

數據范圍
$1\le n,m\le 2^{31?1}$

輸入樣例：

5 5

輸出樣例：

1

樣例解釋
$T(5)=(1+2\times 1+3\times 2+4\times 3+5\times 5)mod5=1$

我們有遞推關系:
$f_n=f_{n?1}+f_{n?2}$
$S_n=S_{n?1}+f_n$
$T_n=T_{n?1}+n?f_n$
但是對于$T_n=T_{n?1}+n?f_n$，$f_n$的系數不為常數，所以無所用矩陣快速冪來優化。

令$P_n=n{S}_n?T_n$,那么有：
$P_n=(n?1)S_1+(n?2)S_2...+S_{n?1}$,
$P_{n+1}=n{S}_1+(n?1)S_2...+2S_{n?1}+S_n$,
$P_{n+1}?P_n=S_n$
于是，我們有以下三組遞推關系：
$f_n=f_{n?1}+f_{n?2}$
$S_n=S_{n?1}+f_n$
$P_n=P_{n?1}+S_{n?1}$
每一組的系數都為常數，我們可以使用矩陣快速冪來優化。
設$F_n=[f_n,f_{n+1},S_n,P_n]$，有$F_n\times A=F_{n+1}$，根據遞推關系求解矩陣$A$。
$[f_n,f_{n+1},S_n,P_n]\times \left[\begin{array}{cccc}{a}_{11}& a_{12}& a_{13}& a_{14}\\ a_{21}& a_{22}& a_{23}& a_{24}\\ a_{31}& a_{32}& a_{33}& a_{34}\\ a_{41}& a_{42}& a_{43}& a_{44}\end{array}\right]=[f_{n+1},f_{n+2},S_{n+1},P_{n+1}]$
根據遞推關系，解出
$A=\left[\begin{array}{cccc}0& 1& 0& 0\\ 1& 1& 1& 0\\ 0& 0& 1& 1\\ 0& 0& 0& 1\end{array}\right]$
$F_1=[1,1,1,0],$ $F_n=F_1\times A^{n?1}$
解出來$S_n$和$P_n$，最終答案$T_n=n{S}_n?P_n$。
時間復雜度為$O(logn?4^3)$。

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 4;
int n, m;
void mul(int a[][N], int b[][N], int c[][N])
{int temp[N][N] = {0};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)b[i][k] * c[k][j] % m) % m;memcpy(a, temp, sizeof temp);
}
int main()
{cin >> n >> m;int f[N][N] = {1, 1, 1, 0};int a[N][N] = {{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(f, f, a);mul(a, a, a);k >>= 1;}cout << ((ll)n * f[0][2]% m - f[0][3] + m) % m << endl;return 0;
}