Nowcoder 105G 又见斐波那契 （矩阵快速幂）
题目描述
这是一个加强版的斐波那契数列，给定递推式
F(i)=⎧⎩⎨F(i−1)+F(i−2)+i3+i2+i+101i>1i=0i=1
F
(
i
)
=
{
F
(
i
−
1
)
+
F
(
i
−
2
)
+
i
3
+
i
2
+
i
+
1
i
>
1
0
i
=
0
1
i
=
1
求 F(n)
F
(
n
)
的值，由于这个值可能太大，请对 109+7
10
9
+
7
输入描述
第一行是一个整数 T (1≤T≤1000)
T
(
1
≤
T
≤
1000
)
以后每个样例一行，是一个整数 n (1≤n≤1018)
n
(
1
≤
n
≤
10
18
)
输出描述
每个样例输出一行，一个整数，表示 F(n) mod 1000000007
F
(
n
)
m
o
d
1000000007
输入
4123100
输出
11657558616258
思路
这道题的关键在于构造矩阵，然后运用快速幂求解即可。
⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢FiFi−1(i+1)3(i+1)2i+11⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⟸⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢110000100000101000103100103210101111⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥×⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢Fi−1Fi−2i3i2i1⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥
[
F
i
F
i
−
1
(
i
+
1
)
3
(
i
+
1
)
2
i
+
1
1
]
⟸
[
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
]
×
[
F
i
−
1
F
i
−
2
i
3
i
2
i
1
]
注意对前两项进行特判。
AC 代码
#include #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;}
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
