题解 P1962 【斐波那契数列】
NaCly_Fish
2019-04-24 23:16:06
## 扩域大法好!
一看这题的题解,清一色的都是矩阵快速幂。
我来一篇扩域的题解吧!
首先,我们都知道$\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;
}
```