在模意义下,使用通项公式没有了精度误差,就变的可以使用了 斐波那契数列的通项公式是:\(F(n)=\frac{\frac{\sqrt{5}+1}{2}^{n}-\frac{-\sqrt{5}+1}{2}^{n}}{\sqrt{5}}\)
而 \(\sqrt{5}\) 在不同的模数下,不一定存在,否则枚举一下或者二次剩余定理弄一下就可以求出来
在通项公式中是实际上可以把两项分开算 \(\frac{\sqrt{5}+1}{2}^{n}\),\(\frac{-\sqrt{5}+1}{2}^{n}\)
但是在分母中还是有一个 \(\sqrt{5}\) 要除,那么我们观察式子,分子的不带 \(\sqrt{5}\) 的项都是相同的,并且指数都是 \(n\),所以最后求出来的结果是一样的,最后相减就抵消了,所以我们只需要关心 \(\sqrt{5}\) 的系数就行了,最关键的是:分母还有一个 \(\sqrt{5}\) 那么不就和分子中的 \(\sqrt{5}\) 抵消掉了,我们根本不用关心\(\sqrt{5}\) 的值了,最后答案就是 \(\sqrt{5}\) 的系数了
不妨把一个数表示成 \(a*\sqrt{5}+b\) 的形式,那么乘法之后还是一个关于 \(\sqrt{5}\) 的表达式 我们定义一个类,重载一下运算就可以了
关于这个东西求逆,列个方程算一下发现逆元就是 \(\frac{-\sqrt{5}*a}{b^2-5*a^2}+\frac{b}{b^2-5*a^2}\),相乘得到 \((0,1)\)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1100,mod=998244353,inv2=499122177; ll f[N]; inline int qpow(int x,int k){ int sum=1; while(k){ if(k&1)sum=1ll*sum*x%mod; x=1ll*x*x%mod;k>>=1; } return sum; } struct Num{ int a,b;//a*sqrt(5)+b Num(){a=0;b=0;} Num(int _a,int _b){a=_a;b=_b;} Num operator *(const Num &p){ return Num((1ll*b*p.a+1ll*a*p.b)%mod,(1ll*a*p.a*5+1ll*b*p.b)%mod); } Num operator -(const Num &p){ return Num((a-p.a+mod)%mod,(b-p.b+mod)%mod); } Num inv(){ int t=qpow(((1ll*b*b-1ll*5*a*a)%mod+mod)%mod,mod-2); return Num(1ll*(mod-a)*t%mod,1ll*b*t%mod); } }Z=Num(inv2,inv2),F=Num(mod-inv2,inv2); inline Num qm(Num x,int k){ Num S=Num(0,1); while(k){ if(k&1)S=S*x; x=x*x;k>>=1; } return S; } int main(){ freopen("pp.in","r",stdin); freopen("pp.out","w",stdout); f[1]=1; int n=999; for(int i=2;i<=n;i++)f[i]=(f[i-1]+f[i-2])%mod; Num S=qm(Z,n),T=qm(F,n); S=S-T; cout<<S.a<<endl<<f[n]<<endl; return 0; }转载于:https://www.cnblogs.com/Yuzao/p/8807629.html
