提供一个不超纲的$O(\log n)$做法。

构造方程$a^{2}=a+1$，则有：

$a^{3}=a^{2}+a=2a+1$

$a^{4}=a^{3}+a^{2}=3a+2$

$a^{5}=a^{4}+a^{3}=5a+3$

$a^{6}=a^{5}+a^{4}=8a+5$

……

故$a^{n}=f(n)a+f(n-1)$（这部分想要严谨证明可以使用数学归纳法）

所以我们只需要构造$a^{n}=pa+q$，即可求出$f(n)=p$。

由$a^{n}$的性质，显然有：

$a^{2n}=(a^{n})^{2}=(f(n)a+f(n-1))^{2}=f(n)^{2}a^{2}+2f(n)f(n-1)a+f(n-1)^{2}=(f(n)^{2}+2f(n)f(n-1))a+f(n)^{2}+f(n-1)^{2}$

因此我们可以由$a^{n}$$O(1)$求出$a^{2n}$（以及$a^{2n+1}$）。

所以我们便能使用快速幂递归求解，时间复杂度$O(\log n)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, p;
struct node
{
	int a, b;
};
node operator*(node x, node y)
{
	int p1 = x.a * y.a, p2 = x.a * y.b + x.b * y.a, p3 = x.b * y.b;
	return node{(p2 + p1) % p, (p3 + p1) % p};
}
node f(int x)
{
	if (x == 1)
	{
		return node{1, 0};
	}
	node c = f(x >> 1);
	if (x & 1)
	{
		return c * c * f(1);
	}
	return c * c;
}
signed main()
{
	cin >> n >> p;
	cout << f(n).a << endl;
}

快速幂和多项式乘法应该不算超纲吧。
赛后发现很多人都用的矩阵快速幂，但是我不会呀。