题解 P1962 【斐波那契数列】

NaCly_Fish

2019-04-24 23:16:06

Solution

## 扩域大法好! 一看这题的题解,清一色的都是矩阵快速幂。 我来一篇扩域的题解吧! 首先,我们都知道$\text{fibonacci}$数列通项公式是这个: $$\large \text{F}_n=\frac{1}{\sqrt 5}((\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n)$$ 然后我们发现$5$在模$10^9+7$意义下是没有二次剩余的。。 那这怎么办?我们要引入一种黑科技:**扩域** 何谓扩域?我们先回想一下复数。 复数一般表示为$a+bi$的形式。 其中$a$为实部,$b$为虚部,$i^2=-1$ 谁说虚数单位一定要是$i$了? 我们自创一种复数,它的虚数单位为$\sqrt5$。(然而它实际上还是实数) 于是,我们把实数都可以表示为$a+b\sqrt 5$的形式。 如此一来,我们就可以在模$10^9+7$意义下算这个东西了! 关于这种数的具体运算法则,和普通的复数差不多。 例如乘法是这样的: $$\large (a+b\sqrt 5)(c+d\sqrt 5)=ac+5bd+(ad+bc)\sqrt 5$$ 你会发现最后还有个除$\sqrt 5$,好像不太好搞。 不过别慌,我们可以证明最后算出的结果,实部必为$0$。 所以答案就是虚部的系数啦! Code: ```cpp #include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<queue> #define reg register #define N 200003 #define inf 0x3f3f3f3f #define int long long #define p 1000000007 #define inv2 500000004 using namespace std; struct complex{ //我们自定义的复数,表示为a+b*sqrt(5) int a,b; complex(int a=0,int b=0):a(a),b(b){} complex operator + (const complex& x) const{ complex res; res.a = (a+x.a)%p; res.b = (b+x.b)%p; return res; } complex operator - (const complex& x) const{ complex res; res.a = (a-x.a+p)%p; res.b = (b-x.b+p)%p; return res; } complex operator * (const complex& x) const{ complex res; res.a = (a*x.a+5*b*x.b)%p; res.b = (a*x.b+x.a*b)%p; return res; } }; inline complex power(complex a,int t){ complex res = complex(1,0); //直接快速幂 while(t){ if(t&1) res = res*a; a = a*a; t >>= 1; } return res; } int n,ans; complex x,y,res; signed main(){ scanf("%lld",&n); x = complex(inv2,inv2); y = complex(inv2,p-inv2); x = power(x,n); y = power(y,n); res = x-y; ans = res.b; printf("%lld",ans); return 0; } ```