3969 [Mz]平方和【斐波那契平方和】

3969 [Mz]平方和

 时间限制: 1 s

 空间限制: 64000 KB

 题目等级 : 大师 Master

题解

 查看运行结果

 

 

题目描述 Description

斐波那契数列：f[0]=0,f[1]=1,f[i]=f[i-1]+f[i-2](i>1)

求f[1]*f[1]+f[2]*f[2]+...+f[n]*f[n]的值

输入描述 Input Description

仅一行，一个正整数n

输出描述 Output Description

仅一行一个数，即所求的值，由于结果可能很大，需对1,000,000,007取模

样例输入 Sample Input

3

样例输出 Sample Output

6

数据范围及提示 Data Size & Hint

对于100‰的数据，n<=1,000,000=10^6

然而：

对于200‰的数据，n<=9,000,000,000,000,000,000=9*10^18

对于500‰的数据，n<=10^500

对于1000‰的数据，n<=10^50000

分类标签 Tags 点此展开

引理1：

　　平方求和

　　

 

关于模数，Seavot__提供。

#include<cstdio>

using namespace std;

typedef long long ll;ll n;

const ll mod=;

char s[];

struct matrix{ll s[][];}A,F;

ll mul(ll a,ll b){

    ll res=;

    for(;b;b>>=,a=(a+a)%mod) if(b&) res=(res+a)%mod;

    return res;

}

matrix operator *(const matrix &a,const matrix &b){

    matrix c;

    for(int i=;i<;i++){

        for(int j=;j<;j++){

            c.s[i][j]=;

            for(int k=;k<;k++){

                c.s[i][j]+=mul(a.s[i][k],b.s[k][j]);

                c.s[i][j]%=mod;

            }

        }

    }

    return c;

}

matrix fpow(matrix a,ll p){

    matrix ans;

    for(int i=;i<;i++) for(int j=;j<;j++) ans.s[i][j]=(i==j);

    for(;p;p>>=,a=a*a) if(p&) ans=ans*a;

    return ans;

}

void deal(){

    for(int i=;s[i];i++){

        n=(n*+s[i]-'')%(mod+);

    }

}

int main(){

    scanf("%s",s);deal();

    A.s[][]=A.s[][]=A.s[][]=;A.s[][]=;

    F.s[][]=;F.s[][]=F.s[][]=F.s[][]=;

    F=fpow(A,n)*F;

    ll ans=F.s[][]*F.s[][]%mod;

    printf("%lld\n",ans);

    return ;

}

 

暂无标签