首页 > 代码库 > ZOJ3774_Power of Fibonacci

ZOJ3774_Power of Fibonacci

2024-07-15 10:50:07   220人阅读

求fibonacci数列前N个数的K次方和。

通项公式：F[n]=((1+sqrt(5))/sqrt(5)-(1-sqrt(5))/sqrt(5))/sqrt(5)。

有点乱，不过由于可以保证最后的结果是一个整数，所有所有的根号都可以化为整数进行取模和逆元运算。

首先解二次同余方程,X^2=n (mod M)，显然，当n=5的时候，X就可以相当于5了。

后面的都可以替换掉。

然后就变成了 F[n]=(A^n+B^n)*C。

这里通过二项式展开，分别对每一项进行计算，同时又可以发现，每一项求和其实是一个等比数列，于是，就可以直接搞了。

 

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#define M 1000000009#define maxn 100100typedef long long ll;using namespace std;ll w,a,m,root,inv;ll A[maxn],B[maxn];ll n,k,ans,cur,now;ll AAA,BBB;int T;struct twice{    ll A,B;    twice() {}    twice(ll AA,ll BB) { A=AA,B=BB; }    void mul(twice T){        ll aa=A*T.A+(B*T.B)%M*w,bb=A*T.B+B*T.A;        A=aa%M,B=bb%M;    }};ll power(ll A,ll B,ll C){    ll tot=1;    while (B){        if (B&1) tot=tot*A%C;        A=A*A%C,B>>=1;    }    return tot;}twice power(twice T,ll y){    twice C(1,0);    while (y){        if (y&1) C.mul(T);        T.mul(T),y>>=1;    }    return C;}ll getroot(){    for (;;){        a=rand()%M;        w=(a*a-5+M)%M;        if (power(w,M/2,M)!=1) break;    }    return power(twice(a,1),(M+1)/2).A;}void _init(){    root=getroot();    A[0]=B[0]=1;    for (int i=1; i<maxn; i++){        A[i]=(A[i-1]*i)%M;        B[i]=power(A[i],M-2,M);    }    inv=B[2];    AAA=(1+root)*inv%M;    BBB=(M+1-root)*inv%M;}int main(){    _init();    scanf("%d",&T);    while (T--){        scanf("%lld%lld",&n,&k);        ans=0;        for (int i=0; i<=k; i++){            cur=A[k]*(B[i]*B[k-i]%M)%M;            if (i&1) cur=M-cur;            now=power(AAA,k-i,M)*power(BBB,i,M)%M;            if (now>1) now=((power(now,n+1,M)-now)*power(now-1,M-2,M)%M+M)%M;                else now=now*n%M;            (ans+=cur*now)%=M;        }        ans=ans*power(root,k*(M-2),M)%M;        printf("%d\n",(int)ans);    }    return 0;}

 


联系
我们