Nowcoder 105G 又见斐波那契 （矩阵快速幂）

题目描述

这是一个加强版的斐波那契数列，给定递推式

$$ F(i)= \begin{cases} F(i-1) + F(i-2) + i^3 + i^2 + i + 1 & & i>1 \\ 0 & & i=0 \\ 1 & & i=1 \end{cases} $$

求 $F(n)$ 的值，由于这个值可能太大，请对 $10^9+7$ 取模。

输入描述

第一行是一个整数 $T~(1 ≤ T ≤ 1000)$ ，表示样例的个数。

以后每个样例一行，是一个整数 $n~(1 ≤ n ≤ 10^{18})$ 。

输出描述

每个样例输出一行，一个整数，表示 $F(n)\ mod\ 1000000007$ 。

输入

4
1
2
3
100

输出

1
16
57
558616258

思路

这道题的关键在于构造矩阵，然后运用快速幂求解即可。

$$ \begin{bmatrix} F_i \\ F_{i-1} \\ (i+1)^3 \\ (i+1)^2 \\ i+1 \\ 1 \end{bmatrix} \Longleftarrow \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 3 & 3 & 1 \\ 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \times \begin{bmatrix} F_{i-1} \\ F_{i-2} \\ i^3 \\ i^2 \\ i \\ 1 \end{bmatrix} $$

注意对前两项进行特判。

AC 代码

#include <bits/stdc++.h>
#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const LL meix[6][6] = {{
                           1,
                           1,
                           1,
                           1,
                           1,
                           1,
                       },
                       {
                           1,
                           0,
                           0,
                           0,
                           0,
                           0,
                       },
                       {
                           0,
                           0,
                           1,
                           3,
                           3,
                           1,
                       },
                       {
                           0,
                           0,
                           0,
                           1,
                           2,
                           1,
                       },
                       {
                           0,
                           0,
                           0,
                           0,
                           1,
                           1,
                       },
                       {
                           0,
                           0,
                           0,
                           0,
                           0,
                           1,
                       }};

class marx {
public:
    marx() { memset(mp, 0, sizeof(mp)); }
    LL mp[6][6];
    static marx mult(const marx &x, const marx &y) {
        marx res = marx();
        for (LL i = 0; i < 6; i++)
            for (LL j = 0; j < 6; j++)
                for (LL k = 0; k < 6; k++)
                    res.mp[i][j] =
                        (res.mp[i][j] + x.mp[i][k] * y.mp[k][j]) % mod;
        return res;
    };
} init;

marx mult(const marx &x, LL k) {
    marx tmp = marx();
    marx tmpx = x;
    for (int i = 0; i < 6; i++) {
        tmp.mp[i][i] = 1;
    }
    while (k) {
        if (k & 1)
            tmp = init.mult(tmp, tmpx);
        tmpx = init.mult(tmpx, tmpx);
        k >>= 1;
    }
    return tmp;
}

int main() {
#ifdef LOCAL_IM0QIANQIAN
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    IO;
#endif // LOCAL_IM0QIANQIAN
    int T;
    cin >> T;
    marx res = marx();
    memcpy(res.mp, meix, sizeof(meix));

    while (T--) {
        LL n;
        cin >> n;
        if (n <= 1) {
            cout << n << endl;
            continue;
        }
        marx ans = mult(res, n - 1);
        cout << (ans.mp[0][0] + ans.mp[0][2] * 8 + ans.mp[0][3] * 4 +
                 ans.mp[0][4] * 2 + ans.mp[0][5]) %
                    mod
             << endl;
    }
    return 0;
}