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;
}