啊这,猛推了一波公式,发现没必要用四阶矩阵
为了方便刚原式,我们提出一个公式(也是斐波那契数列的性质)
$$
f_1+f_2+\cdots+f_n=f_{n+2}-1
$$
公式的证明直接用斐波那契数列的定义与错位相加即可
然后就拿着这个公式硬刚上阵
数学是信息的王炸(by lls
注意多开$long long$,不然会卡在奇怪的地方
这样写会比用四阶矩阵快一倍
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll p, m;
void mul(ll f[2], ll a[2][2]) {
ll c[2] = {0};
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
c[j] = (c[j] + 1ll * f[k] * a[k][j]) % m;
memcpy(f, c, sizeof(c));
}
void mul(ll a[2][2]) {
ll c[2][2] = {0};
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
c[i][j] = (c[i][j] + 1ll * a[i][k] * a[k][j]) % m;
memcpy(a, c, sizeof(c));
}
ll fibo(ll p) {
ll f[2] = {0, 1};
ll a[2][2] = {{0, 1}, {1, 1}};
while (p) {
if (p & 1) mul(f, a);
mul(a);
p >>= 1;
}
return f[0];
}
int main() {
cin >> p >> m;
ll ans = 1ll * (p + 1) * fibo(p + 2) - fibo(p + 4) + 2;
cout << (ans % m + m) % m << endl;
return 0;
}