<—点个赞吧QwQ

宣传一下算法提高课整理

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

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

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

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

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

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

现在佳佳告诉你了一个 $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) \bmod 5 = 1$

思路

提供一个不太一样的，但较为简单的思路。

化简式子，可得 $T(n)=nS_n-G{n-1}$，不懂看这里，这里就不写了。

要把 $f_n,f_{n-1},S_n,G_n$ 作为矩阵递推的东西，其中 $f$ 是斐波那契数列，$S_n=\displaystyle\sum_{i=1}^nf_i$，$G_n=\displaystyle\sum_{i=1}^nS_i$。

不难得到以下式子：
1. $f_n=f_{n-1}+f_{n-2}$
2. $S_n=S_{n-1}+f_i$
3. $G_n=G_{n-1}+S_i$

于是根据矩阵乘法的定义，若维护的东西顺序为 $f_n,f_{n-1},S_n,G_n$，那么转移矩阵为 $$\left[\begin{matrix}1&1&0&0\\1&0&0&0\\1&1&1&0\\1&1&1&1\\\end{matrix}\right]$$。

于是这题就做完了，有一些细节在代码中有体现。

#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cassert>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define desktop "C:\\Users\\MPC\\Desktop\\"
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> PII;
const int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};
template <typename T1,typename T2> bool tomax (T1 &x,T2 y) {
    if (y > x) return x = y,true;
    return false;
}
template <typename T1,typename T2> bool tomin (T1 &x,T2 y) {
    if (y < x) return x = y,true;
    return false;
}
LL power (LL a,LL b,LL p) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
LL n,m;
struct matrix {
    int n,m;
    LL a[5][5];
    matrix (int _n,int _m) {
        n = _n,m = _m;
        memset (a,0,sizeof (a));
    }
};
matrix operator * (matrix a,matrix b) {
    assert (a.m == b.n);
    matrix c (a.n,b.m);
    for (int i = 1;i <= a.n;i++) {
        for (int j = 1;j <= a.m;j++) {
            for (int k = 1;k <= b.m;k++) c.a[i][k] = (c.a[i][k] + a.a[i][j] * b.a[j][k] % m) % m;
        }
    }
    return c;
}
int main () {
    matrix tmp (4,4);
    tmp.a[1][1] = tmp.a[1][2] = tmp.a[2][1] = tmp.a[3][1] = tmp.a[3][2] = tmp.a[3][3] = tmp.a[4][1] = tmp.a[4][2] = tmp.a[4][3] = tmp.a[4][4] = 1;
    cin >> n >> m;
    matrix ans (4,1);
    ans.a[1][1] = ans.a[3][1] = ans.a[4][1] = 1;
    LL x = n - 1;
    while (x) {
        if (x & 1) ans = tmp * ans;
        tmp = tmp * tmp;
        x >>= 1;
    }
    LL s = ans.a[3][1],g = ans.a[4][1];
    g = (g - s + m) % m;
//  cout << s << ' ' << g << endl;
    cout << ((n * s % m - g) % m + m) % m << endl;
    return 0;
}