分析

• 题目已经给出S(n)和T(n)的表达式，我们可以构造P(n)：

$$ P(n) = n \times S(n) - T(n) = (n - 1) \times f_1 + (n - 2) \times f_2 + … + f_{n-1} $$

则有：
$$ P(n+1) - P(n) = S(n) $$
因此如果我们可以求出P(n)和S(n)，则就可以求出T(n)，其表达是为：$T(n) = n \times S(n) - P(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$和题目中的不同，$f_n$和题目中的$F_n$相同），则有：

$$ [f_n, f_{n+1}, S_n, P_n] \left[ \begin{matrix} 0 & 1 & 0 & 0 \\\\ 1 & 1 & 1 & 0 \\\\ 0 & 0 & 1 & 1 \\\\ 0 & 0 & 0 & 1 \end{matrix} \right] = [f_{n+1}, f_{n+2}, S_{n+1}, P_{n+1}] $$

• 因此有如下递推式：

$$ F_n = F_1 \left[ \begin{matrix} 0 & 1 & 0 & 0 \\\\ 1 & 1 & 1 & 0 \\\\ 0 & 0 & 1 & 1 \\\\ 0 & 0 & 0 & 1 \end{matrix} \right] ^ {n - 1} \quad \quad F_1 = [1, 1, 1, 0] $$

• 假如设A表示那个变换矩阵，则我们对$A^{n-1}$进行快速幂求解即可。

代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 4;

int n, m;

// c = a * b
void mul(int c[][N], int a[][N], int b[][N]) {

    static int t[N][N];
    memset(t, 0, sizeof t);

    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] + (LL)a[i][k] * b[k][j]) % m;

    memcpy(c, t, sizeof t);
}

int main() {

    cin >> n >> m;

    int f1[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(f1, f1, a);  // f1 = f1 * a
        mul(a, a, a);
        k >>= 1;
    }

    cout << (((LL)n * f1[0][2] - f1[0][3]) % m + m) % m << endl;

    return 0;
}