Untitled
unknown
c_cpp
a year ago
1.5 kB
9
Indexable
#include <iostream> #include <cmath> #include <cstdio> #include <string> #include <cstring> #include <algorithm> using std::string; using namespace std; // 矩阵乘法,并对结果进行模运算 void multiply(long long a[2][2], long long b[2][2], long long mod) { long long res[2][2]; res[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % mod; res[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % mod; res[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % mod; res[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % mod; // 将结果复制回 a a[0][0] = res[0][0]; a[0][1] = res[0][1]; a[1][0] = res[1][0]; a[1][1] = res[1][1]; } // 矩阵快速幂,并对结果进行模运算 void power(long long base[2][2], long long exp, long long mod) { long long res[2][2] = {{1, 0}, {0, 1}}; // 单位矩阵 while (exp > 0) { if (exp % 2 == 1) { multiply(res, base, mod); } multiply(base, base, mod); exp /= 2; } // 将结果复制回 base base[0][0] = res[0][0]; base[0][1] = res[0][1]; base[1][0] = res[1][0]; base[1][1] = res[1][1]; } // 计算费氏数列的第 n 项,并对结果进行模运算 long long fibonacci(long long n, long long mod) { if (n == 0) return 0; long long T[2][2] = {{1, 1}, {1, 0}}; power(T, n - 1, mod); return T[0][0]; } int main() { long long n; long long r; cin >> n >> r; cout << fibonacci(n, r) << endl; return 0; }
Editor is loading...
Leave a Comment