#include<bits/stdc++.h> using namespace std; using ll = long long; const ll N = 2; long long n, p; struct Matrix { long long m[N][N]; Matrix() { memset(m, 0, sizeof m); }//矩阵初始化为0的操作 Matrix operator*(const Matrix &b) const//定义矩阵乘法运算 { Matrix c; for (ll i = 0; i < N; i++) for (ll j = 0; j < N; j++) for (ll k = 0; k < N; k++) { c.m[i][j] = (c.m[i][j] + m[i][k] * b.m[k][j]) % p; } return c; } }; ll t; Matrix fun(Matrix a, long long b) { Matrix res; for (ll i = 0; i < N; i++) res.m[i][i] = 1;//构造单位矩阵res while (b) { if (b & 1) res = res * a; // 对于奇数次幂，把矩阵a乘到res上 a = a * a; b >>= 1; } return res; } int main() { cin >> T; while (T--) { cin >> n >> p; Matrix M; M.m[0][0] = 1; M.m[0][1] = 1; M.m[1][0] = 1;//构造矩阵M Matrix res = fun(M, n - 1); cout << res.m[0][0] % p << endl; } return 0; }

这段代码是一个矩阵快速幂的实现，用于计算斐波那契数列的第n项，其中p是一个取模数。矩阵快速幂是一个优化的算法，可以用于高效地计算矩阵的幂，而不需要进行重复的计算。在这个算法中，通过将矩阵的幂以二进制的形式表达，可以将幂的计算复杂度降低到O(log n)。具体地，通过将矩阵M的n-1次幂与单位矩阵相乘，可以得到斐波那契数列的第n项。