佳佳的 Fibonacci

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1365 字

设S=F_1+...+F_n，T=F_1+2

一本通
例

正文

/*
原题：T1644「一本通 6.5 例 4」佳佳的 Fibonacci
题意：设 S(n)=F_1+...+F_n，T(n)=F_1+2F_2+...+nF_n，求 T(n) mod m。
思路：直接维护带系数 k 的和不方便，改用恒等式 T(n)=n·F_{n+2}−F_{n+3}+2（已用小规模验证）。
于是只需用 [[1,1],[1,0]] 的矩阵快速幂求出 F_{n+2} 与 F_{n+3} 再代入即可。
复杂度：时间 O(log n)，空间 O(1)
易错点：1) 代入前先把 n 对 m 取模，避免 n·F_{n+2} 溢出；
2) 减 F_{n+3} 后可能为负，要先加 m 再取模，不能直接用 %；
3) 恒等式对 n=0 也成立：0·F_2−F_3+2=−2+2=0。
*/
#include <bits/stdc++.h>
using namespace std;
struct Mat{
    long long v[2][2];
};
Mat mul(const Mat& x,const Mat& y,long long mod){
    Mat r;
    memset(r.v,0,sizeof(r.v));
    for(int i=0;i<2;i++){
        for(int k=0;k<2;k++){
            for(int j=0;j<2;j++){
                r.v[i][j]=(r.v[i][j]+x.v[i][k]*y.v[k][j])%mod;
            }
        }
    }
    return r;
}
Mat mpow(Mat a,long long n,long long mod){
    Mat r;
    memset(r.v,0,sizeof(r.v));
    r.v[0][0]=1;
    r.v[1][1]=1;
    while(n>0){
        if(n&1){
            r=mul(r,a,mod);
        }
        a=mul(a,a,mod);
        n>>=1;
    }
    return r;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long n,m;
    cin>>n>>m;
    Mat base;
    base.v[0][0]=1;
    base.v[0][1]=1;
    base.v[1][0]=1;
    base.v[1][1]=0;
    Mat r=mpow(base,n+2,m);
    long long fn2=r.v[0][1];
    long long fn3=r.v[0][0];
    long long ans=((n%m)*fn2-fn3+2)%m;
    if(ans<0){
        ans+=m;
    }
    cout<<ans<<"\n";
    return 0;
}

佳佳的 Fibonacci

正文

一本通·提高篇的其它内容