3969 [Mz]平方和

時間限制: 1 s

空間限制: 64000 KB

題目等級 : 大師 Master

題解
查看運(yùn)行結(jié)果

題目描述Description

斐波那契數(shù)列：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

僅一行，一個正整數(shù)n

輸出描述Output Description

僅一行一個數(shù)，即所求的值，由于結(jié)果可能很大，需對1,000,000,007取模

樣例輸入Sample Input

3

樣例輸出Sample Output

6

數(shù)據(jù)范圍及提示Data Size & Hint

對于100‰的數(shù)據(jù)，n<=1,000,000=10^6

然而：

對于200‰的數(shù)據(jù)，n<=9,000,000,000,000,000,000=9*10^18

對于500‰的數(shù)據(jù)，n<=10^500

對于1000‰的數(shù)據(jù)，n<=10^50000

分類標(biāo)簽Tags點(diǎn)此展開

引理1：

　　平方求和

　　

關(guān)于模數(shù)，Seavot__提供。

#include<cstdio>
using namespace std;
typedef long long ll;ll n;
const ll mod=1000000007;
char s[50000];
struct matrix{ll s[2][2];}A,F;
ll mul(ll a,ll b){
    ll res=0;
    for(;b;b>>=1,a=(a+a)%mod) if(b&1) res=(res+a)%mod;
    return res;
}
matrix operator *(const matrix &a,const matrix &b){
    matrix c;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            c.s[i][j]=0;
            for(int k=0;k<2;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=0;i<2;i++) for(int j=0;j<2;j++) ans.s[i][j]=(i==j);
    for(;p;p>>=1,a=a*a) if(p&1) ans=ans*a;
    return ans;
}
void deal(){
    for(int i=0;s[i];i++){
        n=(n*10+s[i]-'0')%(mod+1);
    }
}
int main(){
    scanf("%s",s);deal();
    A.s[0][0]=A.s[0][1]=A.s[1][0]=1;A.s[1][1]=0;
    F.s[0][0]=1;F.s[0][1]=F.s[1][0]=F.s[1][1]=0;
    F=fpow(A,n)*F;
    ll ans=F.s[0][0]*F.s[1][0]%mod;
    printf("%lld
",ans);
    return 0;
}

暫無標(biāo)簽

總結(jié)

以上是生活随笔為你收集整理的3969 [Mz]平方和【斐波那契平方和】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。