就是上面这个矩阵算式。我也不知道怎么想到的。
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
// const int MOD = 10000;
typedef pair<int, int> PII;
LL x, MOD;
const int N = 32;
vector<vector<LL>> f = {{0, 1, 0}};
vector<vector<LL>> A = {{0, 1, 0}, {1, 1, 1}, {0, 0, 1}};
vector<vector<LL>> mul(vector<vector<LL>> a, vector<vector<LL>> b) {
int n = a.size(), m = b[0].size(), p = a[0].size();
vector<vector<LL>> c(n, vector<LL>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < p; k++) {
c[i][j] = (c[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
}
}
}
return c;
}
vector<vector<LL>> qmi(vector<vector<LL>> & a, int x) {
vector<vector<LL>> res = {{0, 1, 0}};
vector<vector<LL>> base = a;
for (int i = 0; i < N; i++) {
if (x & (1 << i)) {
res = mul(res, base);
}
base = mul(base, base);
}
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin >> x >> MOD;
if (x == 1) {
cout << 1;
return 0;
}
auto res = qmi(A, x);
cout << res[0][2];
return 0;
}