python/TangDou/AcWing_TiGao/T5/JuZhengChengFa/1304.md

##AcWing 1304. 佳佳的斐波那契

一、题目描述

佳佳对数学，尤其对数列十分感兴趣。

在研究完 Fibonacci 数列后，她创造出许多稀奇古怪的数列。

例如用 S(n) 表示 Fibonacci 前 n 项和 mod\ m 的值，即 $S(n)=(F_1+F_2+…+F_n)\ mod\ m$，其中 $F_1=F_2=1,F_i=F_{i−1}+F_{i−2}$。

可这对佳佳来说还是小菜一碟。

终于，她找到了一个自己解决不了的问题。

用 T(n)=(F_1+2F_2+3F_3+…+nF_n)\ mod\ m 表示 Fibonacci 数列前 n 项变形后的和 mod\ m 的值。

现在佳佳告诉你了一个 n 和 $m$，请求出 T(n) 的值。

输入格式 共一行，包含两个整数 n 和 $m$。

输出格式 共一行，输出 T(n) 的值。

数据范围 1≤n,m≤2^{31}−1

输入样例： 5 5

输出样例： 1

样例解释 T(5)=(1+2×1+3×2+4×3+5×5)\ mod\ 5=1

二、推导过程

$$\because S_n=F_1+F_2+⋯+F_n=\sum_{i=1}^{n}F_i \ T_n=F_1+2*F_2+...+nF_n=\sum_{i=1}^{n}iF_i$$

我们需要利用$T_n$构造新的数列，从而消去变量$i$，最后再反解出$T_n$：

\therefore nS_n-T_n=(n-1)F_1+(n-2)F_2+...+F_{n-1}

令C_n=nS_n-T_n

\therefore C_n=(n-1)F_1+(n-2)F_2+...+F_{n-1} \ ① C_{n+1}=nF_1+(n-1)F_2+...+F_{n} \ ②

② 式 - ① 式

C_{n+1}-C_n=F_1+F_2+F_3+...+F_n=S_n

于是我们只需维护如下矩阵即可

\begin{pmatrix}
 f_{n+1} &  f_n  & s_n & c_n 
\end{pmatrix} 

有如下等式:

\begin{pmatrix}
 f_{n+1} &  f_n  & s_n & c_n 
\end{pmatrix} \times
\begin{pmatrix}
 1 &  1  & 1 & 0 \\
 1 &  0  & 0 & 0 \\
 0 &  0  & 1 & 1 \\
 0 &  0  & 0 & 1 
\end{pmatrix}=
\begin{pmatrix}
 f_{n+2} &  f_{n+1}  & s_{n+1} & c_{n+1} 
\end{pmatrix} 

然后直接使用矩阵快速幂便可以求解

初始矩阵 $$\begin{pmatrix} f_{2} & f_{1} & s_{1} & c_{1} \ \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 & 0 \end{pmatrix}

 

**递推式**
$$\begin{pmatrix}
 f_{n+1} &  f_{n}  & s_{n} & c_{n}  \\
\end{pmatrix} =\begin{pmatrix}
 f_{2} &  f_{1}  & s_{1} & c_{1}  \\
\end{pmatrix} \times
\begin{pmatrix}
 1 &  1  & 1 & 0 \\
 1 &  0  & 0 & 0 \\
 0 &  0  & 1 & 1 \\
 0 &  0  & 0 & 1 
\end{pmatrix}^{n-1}

答案 T_n=nS_n-C_n =n\times b[0][2]-b[0][3]

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

const int N = 4;
int n, mod;

// 矩阵乘法
void mul(int a[][N], int b[][N], int c[][N]) {
    int t[N][N] = {0};
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                t[i][j] = (t[i][j] + (a[i][k] * b[k][j]) % mod) % mod;
    }
    memcpy(c, t, sizeof t);
}
int main() {
    int b[N][N] = {1, 1, 1, 0};
    int m[N][N] = {
        {1, 1, 1, 0},
        {1, 0, 0, 0},
        {0, 0, 1, 1},
        {0, 0, 0, 1}};

    cin >> n >> mod;
    for (int i = n - 1; i; i >>= 1) {
        if (i & 1) mul(b, m, b);
        mul(m, m, m);
    }

    int t = (n * b[0][2]) - b[0][3];
    t = (t % mod + mod) % mod;
    printf("%lld\n", t);
    return 0;
}