P1349 广义斐波那契数列(矩阵乘法)
程序员文章站
2023-02-02 08:47:44
题目 "P1349 广义斐波那契数列" 解析 把普通的矩阵乘法求斐波那契数列改一改,随便一推就出来了 $$\begin{bmatrix}f_2\\f_1 \end{bmatrix}\begin{bmatrix} p&q\\ 1&0\\ \end{bmatrix}^{n 2}=\begin{bmatr ......
题目
解析
把普通的矩阵乘法求斐波那契数列改一改,随便一推就出来了
\[\begin{bmatrix}f_2\\f_1
\end{bmatrix}\begin{bmatrix}
p&q\\
1&0\\
\end{bmatrix}^{n-2}=\begin{bmatrix}f_n\\f_{n-1}
\end{bmatrix}\]
水题
代码
#include <bits/stdc++.h> #define int long long using namespace std; const int n = 100; int n, m, a1, a2, p, q; struct matrix { int a[n][n]; matrix() { memset(a, 0, sizeof a); } void initmatrix() { a[1][1] = p, a[1][2] = q; a[2][1] = 1; } matrix operator * (const matrix &oth) const { matrix ans; for (int k = 1; k <= 2; ++k) for (int i = 1; i <= 2; ++i) for (int j = 1; j <= 2; ++j) ans.a[i][j] = (ans.a[i][j] + (a[i][k] * oth.a[k][j]) % m) % m; return ans; } } init; matrix qpow(matrix a, int b) { matrix ans = init; while (b) { if (b & 1) ans = ans * a; b >>= 1, a = a * a; } return ans; } template<class t>inline void read(t &x) { x = 0; int f = 0; char ch = getchar(); for ( ; !isdigit(ch); ch = getchar()) f |= (ch == '-'); for ( ; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0'; x = f ? -x : x; return; } signed main() { read(p), read(q), read(a1), read(a2), read(n), read(m); if (n <= 2) { printf("%lld", n == 1 ? a1 : a2); return 0; } init.initmatrix(); init = qpow(init, n - 3); printf("%lld\n", (a2 * init.a[1][1] + a1 * init.a[1][2]) % m); return 0; }
上一篇: C语言双层链表
下一篇: Java实现单链表反转操作