526互联

佳佳的 Fibonacci

发布时间 2023-06-14 17:26:04作者: User-Unauthorized

题面

佳佳对数学，尤其对数列十分感兴趣。在研究完 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\)，请求出 \(\displaystyle T(n)\) 的值。

一句话题意

设 \(F_n\) 为 Fibonacci 数列，\(\displaystyle S(n) = \sum_{i = 1}^n{F_i}\)，求 \(\displaystyle T(n) = \sum_{i = 1}^n{i \cdot F_i}\)。

一句话题解

令 \(\displaystyle G(n) = (nF_1+(n - 1)F_2+(n - 2)F_3+...+F_n) = \sum_{i = 1}^n{S(n)}\)，则 \(\displaystyle T(n) = (n + 1)\times S(n) - G(n)\)。可以发现\(G(n)\) 是 \(S(n)\) 的前缀和，而 \(S(n)\) 又是 \(F_n\) 的前缀和，我们可以考虑在矩阵加速递推的时候一起处理出来这些值。

令 \(ans\) 矩阵为

\[\begin{bmatrix} F_{n} & F_{n - 1} & S(n-1) & G(n - 1) \\ \end{bmatrix}\]

考虑到 \(S(n) = S(n - 1) + F_n\)，\(G(n) = G(n - 1) + S(n) = G(n - 1) + S(n - 1) + F_n\)，可以得出 \(base\) 矩阵为

\[\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix}\]

令 \(ans = ans \times base ^ {N - 1}\)，可以得到 \(S(n)\) 和 \(G(n)\)，即可代入求解。

Code

#include<bits/stdc++.h>

long long MOD_;
long long const &MOD = MOD_;

class Matrix {
public:
    typedef long long valueType;
    typedef size_t sizeType;
    typedef std::vector<valueType> Row;
    typedef std::vector<Row> Container;

public:
    sizeType row, column;
    Container data;

public:
    Matrix(sizeType _row_, sizeType _column_) : row(_row_), column(_column_), data(row + 1) {
        for (sizeType i = 1; i <= row; ++i)
            data[i].resize(column + 1, 0);
    };

    Matrix operator*(const Matrix &T) const {
        Matrix result(this->row, T.column);

        for (sizeType i = 1; i <= this->row; ++i) {
            for (sizeType k = 1; k <= this->column; ++k) {
                valueType r = this->data[i][k];

                for (sizeType j = 1; j <= T.column; ++j)
                    result.data[i][j] = (result.data[i][j] + T.data[k][j] * r) % MOD;
            }
        }

        return result;
    }

    friend std::ostream &operator<<(std::ostream &os, const Matrix &T) {
        for (sizeType i = 1; i <= T.row; ++i)
            for (sizeType j = 1; j <= T.column; ++j)
                os << T.data[i][j] << " \n"[j == T.column];

        return os;
    }

    friend std::istream &operator>>(std::istream &os, Matrix &T) {
        for (sizeType i = 1; i <= T.row; ++i)
            for (sizeType j = 1; j <= T.column; ++j)
                os >> T.data[i][j];

        return os;
    }
};

int main() {
    int N;

    std::cin >> N >> MOD_;

    Matrix ans(1, 4), base(4, 4);

    ans.data[1][1] = ans.data[1][2] = ans.data[1][3] = ans.data[1][4] = 1;
    base.data[1][1] = base.data[1][2] = base.data[1][3] = base.data[1][4] =
    base.data[2][1] = base.data[3][3] = base.data[3][4] = base.data[4][4] = 1;

    int M = N - 1;

    while (M) {
        if (M & 1) ans = ans * base;

        base = base * base;

        M = M >> 1;
    }

    long long result = (((N + 1) % MOD) * ans.data[1][3]) % MOD - ans.data[1][4];

    std::cout << (result % MOD + MOD) % MOD << std::flush;

    return 0;
}