题目描述

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

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

例如用 $S(n)$ 表示 Fibonacci 前 $n$ 项和 $\mod m$ 的值，即 $S(n) = (F_1 + F_2 + \cdots + 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 + \cdots + nF_n)\mod m$ 表示 Fibonacci 数列前 $n$ 项变形后的和 $\mod m$ 的值。

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

输入格式

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

输出格式

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

数据范围

$1 \leq n, m \leq 2 ^ {31} − 1$

输入样例：

5 5

输出样例：

1

样例解释

$T(5) = (1 + 2 \times 1 + 3 \times 2 + 4 \times 3 + 5 \times 5)\mod 5 = 1$

算法1

首先推公式

设
$S _ n = F _ 1 + F _ 2 + \cdots + F _ n,$
$G _ n = S _ 1 + S _ 2 + \cdots + S _ n$

那么 $T(n) = F _ 1 + 2 F _ 2 + 3 F _ 3 + \cdots + n F _ n = [n F _ 1 - (n - 1) F _ 1] + [n F _ 2 - (n - 2) F _ 2] + \cdots + [n F _ {n - 1} - F _ {n - 1}] + [n F _ n]$
$= (n F _ 1 + n F _ 2 + \cdots + n F _ n) - [(n - 1) F _ 1 + (n - 2) F _ 2 + \cdots + 2 F _ {n - 2} + F _ {n - 1}]$
$= n(F _ 1 + F _ 2 + \cdots + F _ n) - [(F _ 1 + F _ 2 + \cdots + F _ {n - 1}) + (F _ 1 + F _ 2 + \cdots + F _ {n - 2}) + \cdots + (F _ 1 + F _ 2) + (F _ 1)]$
$= n S _ n - [S _ {n - 1} + S _ {n - 2} + \cdots + S _ 2 + S _ 1]$
$= n S _ n - G _ {n - 1}$

那么只要快速求出 $S _ n$ 和 $G _ {n - 1}$ 就好了。
关于快速求 $S _ n$ 的方法，可以参考 AcWing 1303. 斐波那契前 $n$ 项和。
那 $G _ n$ 怎么求呢？

先推下公式，
由斐波那契前 $n$ 项和中所推公式 $S _ n = 2 S _ {n - 1} - S _ {n - 3}$
可得 $G _ n - G _ {n - 1} = 2 (G _ {n - 1} - G _ {n - 2}) - (G _ {n - 3} - G _ {n - 4})$
整理得 $G _ n = 3 G _ {n - 1} - 2 G _ {n - 2} - G _ {n - 3} + G _ {n - 4}$
那么只要构造矩阵 $A = \left[\begin{matrix} 3 & -2 & -1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{matrix}\right], G = \left[\begin{matrix} G _ 3 \\ G _ 2 \\ G _ 1 \\ G _ 0 \\ \end{matrix}\right] = \left[\begin{matrix} S _ 0 + S _ 1 + S _ 2 + S _ 3 \\ S _ 0 + S _ 1 + S _ 2 \\ S _ 0 + S _ 1 \\ S _ 0 \\ \end{matrix}\right] = \left[\begin{matrix} 3 F _ 1 + 2 F _ 2 + F _ 3 \\ 2 F _ 1 + F _ 2 \\ F _ 1 \\ 0 \\ \end{matrix}\right] = \left[\begin{matrix} 7 \\ 3 \\ 1 \\ 0 \\ \end{matrix}\right]$

然后用矩阵快速幂即可解决

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

常数巨大，但能过

$C ++$ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

int n, m;

void multi_3(ll A[][3], ll B[][3]) // 求出 3 × 3 的方阵 A 和 B 的乘积，并把结果储存在 A 中
{
    ll ans[3][3] = {0};
    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            for (int k = 0; k < 3; k ++ )
                ans[i][j] += A[i][k] * B[k][j] % m;
    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            A[i][j] = ans[i][j] % m;
}

void _multi_3(ll A[], ll B[][3])   // 求出 1 × 3 的矩阵 A 与 3 × 3 的方阵 B 的乘积，并把结果储存在 A 中
{
    ll ans[3] = {0};
    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            ans[i] += A[j] * B[i][j] % m;
    for (int i = 0; i < 3; i ++ )
        A[i] = ans[i] % m;
}

void multi_4(ll A[][4], ll B[][4]) // 求出 4 × 4 的矩阵 A 和 B 的乘积，并把结果储存在 A 中
{
    ll ans[4][4] = {0};
    for (int i = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ )
            for (int k = 0; k < 4; k ++ )
                ans[i][j] += A[i][k] * B[k][j] % m;
    for (int i = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ )
            A[i][j] = ans[i][j] % m;
}

void _multi_4(ll A[], ll B[][4])   // 求出 1 × 4 的矩阵 A 乘 4 × 4 的矩阵 B 的乘积，并把结果储存在 A 中
{
    ll ans[4] = {0};
    for (int i = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ )
            ans[i] += A[j] * B[i][j];
    for (int i = 0; i < 4; i ++ )
        A[i] = ans[i] % m;
}

ll get_S(int n)                    // 求出 S[n]
{
    ll S[3] = {2, 1, 0};
    ll A[3][3] =
    {
        {2, 0, -1},
        {1, 0, 0},
        {0, 1, 0}
    };
    while (n)
    {
        if (n & 1) _multi_3(S, A);
        multi_3(A, A);
        n >>= 1;
    }
    return S[2];
}

ll get_G(int n)                    // 求出 G[n]
{
    ll G[4] = {7, 3, 1, 0};
    ll A[4][4] =
    {
        {3, -2, -1, 1},
        {1, 0, 0, 0},
        {0, 1, 0, 0},
        {0, 0, 1, 0}
    };
    while (n)
    {
        if (n & 1) _multi_4(G, A);
        multi_4(A, A);
        n >>= 1;
    }
    return G[3];
}

int main()
{
    scanf("%d %d", &n, &m);
    ll S = get_S(n), G = get_G(n - 1);
    printf("%lld\n", ((n * S - G) % m + m) % m);
    return 0;
}

算法2

上面的代码虽然能过，但是代码长度的确非常长，不好写。

上机考试的时候不光要考虑代码的时间复杂度、空间复杂度，还要考虑代码复杂度——yxc

那么有没有什么写起来更简单的算法呢？

看上述算法，是将 $S _ n$ 和 $G _ {n - 1}$ 分开来算，相当于是写了两遍矩阵快速幂，所以代码写起来就非常复杂。
我们在算的时候，其实可以用一个矩阵，直接将 $S _ n$ 和 $G _ {n - 1}$ 存在一起，然后一起算出来。
这时候就要换一个构造矩阵的方法了。

我们先构造一个矩阵 $X _ n = \left\[\begin{matrix} F _ {n - 1} & F _ n & S _ n & G _ {n - 1} \\\ \end{matrix}\right\]$
然后想一下，如何将 $X _ n$ 转移到 $X _ {n + 1}$ 呢？
不妨设 $X _ n \times A = X _ {n + 1}$
其中 $A = \left\[\begin{matrix} 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{matrix}\right\]$

所以有 $\left\[\begin{matrix} F _ {n - 1} & F _ n & S _ n & G _ {n - 1} \\\ \end{matrix}\right\] \left\[\begin{matrix} 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{matrix}\right\] = \left\[\begin{matrix} F _ n & F _ {n + 1} & S _ {n + 1} & G _ n \\\ \end{matrix}\right\] = \left\[\begin{matrix} F _ n & F _ n + F _ {n - 1} & S _ n + F _ n + F _ {n - 1} & G _ {n - 1} + S _ n \\\ \end{matrix}\right\]$

所以 $\left\[\begin{matrix} a _ {11} F _ {n - 1} + a _ {21} F _ n + a _ {31} S _ n + a _ {41} G _ {n - 1} & a _ {12} F _ {n - 1} + a _ {22} F _ n + a _ {32} S _ n + a _ {42} G _ {n - 1} & a _ {13} F _ {n - 1} + a _ {23} F _ n + a _ {33} S _ n + a _ {43} G _ {n - 1} & a _ {14} F _ {n - 1} + a _ {24} F _ n + a _ {34} S _ n + a _ {44} G _ {n - 1}\\\ \end{matrix}\right\] = \left\[\begin{matrix} F _ n & F _ n + F _ {n - 1} & S _ n + F _ n + F _ {n - 1} & G _ {n - 1} + S _ n \\\ \end{matrix}\right\]$

太乱了，整理下
$\left\\{\begin{aligned} a _ {11} F _ {n - 1} + a _ {21} F _ n + a _ {31} S _ n + a _ {41} G _ {n - 1} & = F _ n \\\ a _ {12} F _ {n - 1} + a _ {22} F _ n + a _ {32} S _ n + a _ {42} G _ {n - 1} & = F _ n + F _ {n - 1} \\\ a _ {13} F _ {n - 1} + a _ {23} F _ n + a _ {33} S _ n + a _ {43} G _ {n - 1} & = S _ n + F _ n + F _ {n - 1} \\\ a _ {14} F _ {n - 1} + a _ {24} F _ n + a _ {34} S _ n + a _ {44} G _ {n - 1} & = G _ {n - 1} + S _ n \\\ \end{aligned}\right.$

可以推出
$\left\\{\begin{aligned} a _ {21} = &\ 1 \\\ a _ {12} = &\ a _ {22} = 1 \\\ a _ {13} = &\ a _ {23} = a _ {33} = 1 \\\ a _ {34} = &\ a _ {44} = 1 \\\ \end{aligned}\right.$
（非唯一解）

所以 $A = \left\[\begin{matrix} 0 & 1 & 1 & 0 \\\ 1 & 1 & 1 & 0 \\\ 0 & 0 & 1 & 1 \\\ 0 & 0 & 0 & 1 \\\ \end{matrix}\right\]$

因为 $X _ {n - 1} A = X _ n$
所以 $X _ n = X _ 1 A ^ {n - 1}$

根据定义，$X _ 1 = \left\[\begin{matrix} F _ 0 & F _ 1 & S _ 1 & G _ 0 \\\ \end{matrix}\right\] = \left\[\begin{matrix} 0 & 1 & 1 & 0 \\\ \end{matrix}\right\]$

所以我们只需要用矩阵快速幂求出 $A ^ {n - 1}$，再左乘矩阵 $\left\[\begin{matrix} 0 & 1 & 1 & 0 \\\ \end{matrix}\right\]$ 即可。

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

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

int n, m;
ll A[4][4] = {                   // 上述矩阵 A
    {0, 1, 1, 0},
    {1, 1, 1, 0},
    {0, 0, 1, 1},
    {0, 0, 0, 1}
};
ll X[4] = {0, 1, 1, 0};          // 上述矩阵 X

void multi(ll A[][4], ll B[][4]) // 求出 4 × 4 的方阵 A 与 B 的乘积，并储存在 A 中
{
    ll ans[4][4] = {0};
    for (int i = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ )
            for (int k = 0; k < 4; k ++ )
                ans[i][j] += A[i][k] * B[k][j] % m;
    for (int i = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ )
            A[i][j] = ans[i][j] % m;
}

void _multi(ll A[], ll B[][4])   // 求出 1 × 4 的矩阵 A 与 4 × 4 的矩阵 B 的乘积，并储存在 A 中
{
    ll ans[4] = {0};
    for (int i = 0; i < 4; i ++ )
        for (int j = 0; j < 4; j ++ )
            ans[i] += A[j] * B[j][i] % m;
    for (int i = 0; i < 4; i ++ )
        A[i] = ans[i] % m;
}

void get(int n)                  // 求出 X[n]
{
    while (n)
    {
        if (n & 1) _multi(X, A);
        multi(A, A);
        n >>= 1;
    }
}

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

    get(n - 1);                  // 求出 X[n - 1]

    printf("%lld\n", ((n * X[2] - X[3]) % m + m) % m);

    return 0;
}