题解 P1962 【斐波那契数列】

NaCly_Fish · 2019-04-24 23:16:06 · 题解

扩域大法好！

一看这题的题解，清一色的都是矩阵快速幂。
我来一篇扩域的题解吧！

首先，我们都知道\text{fibonacci}数列通项公式是这个：

然后我们发现5在模10^9+7意义下是没有二次剩余的。。
那这怎么办？我们要引入一种黑科技：扩域

何谓扩域？我们先回想一下复数。
复数一般表示为a+bi的形式。
其中a为实部，b为虚部，i^2=-1

谁说虚数单位一定要是i了？
我们自创一种复数，它的虚数单位为\sqrt5。(然而它实际上还是实数)
于是，我们把实数都可以表示为a+b\sqrt 5的形式。

如此一来，我们就可以在模10^9+7意义下算这个东西了！
关于这种数的具体运算法则，和普通的复数差不多。
例如乘法是这样的：

你会发现最后还有个除\sqrt 5，好像不太好搞。
不过别慌，我们可以证明最后算出的结果，实部必为0。
所以答案就是虚部的系数啦！

Code：

#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;
}