题解：SP24689 POWFIB - Fibo and non fibo

qianyuzhe · 2024-04-11 14:01:59 · 题解

题意简述

设 a 是第 n 个不是斐波那契数的数，b 是第 n 个斐波那契数模 10^9+7，求 a^b\bmod(10^9+7) 的值。

分析

首先，我们可以简单地使用矩阵快速幂求出斐波那契数列的第 n 项，因此本题转化为求出第 n 个不是斐波那契数的数。

我们注意到，在正整数中斐波那契数是极稀疏的，因此我们可以遍历斐波那契数列的每一项直到找到最小的 i 使 f_i-i+1\ge n，则有 a=n+i-2。

求 a^b\bmod(10^9+7) 的步骤可用快速幂求解，时间复杂度 O(t\log n)，空间复杂度 O(1)。

代码

#include<bits/stdc++.h>
using namespace std;
long long t,n,x,y,r,i,j,k,f[55],a[3][3],b[3][3],c[3][3],d[3][3]={{0,0,0},{0,1,1},{0,1,0}};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        f[1]=f[2]=1;
        for(i=3;;i++){
            f[i]=f[i-2]+f[i-1];
            if(f[i]-i+1>=n){
                x=n+i-2;
                break;
            }
        }//求a 
        if(n<3)y=1;
        else{
            n-=2;
            for(i=1;i<3;i++)for(j=1;j<3;j++)a[i][j]=d[i][j];
            memset(b,0,sizeof(b));
            memset(c,0,sizeof(c));
            b[1][1]=b[2][2]=1;
            while(n){
                if(n&1){
                    for(i=1;i<3;i++)for(j=1;j<=n;j++)c[i][j]=b[i][j];
                    memset(b,0,sizeof(b));
                    for(i=1;i<3;i++){
                        for(j=1;j<3;j++){
                            for(k=1;k<3;k++){
                                b[i][j]+=a[i][k]%1000000007ll*c[k][j]%1000000007ll;
                                b[i][j]%=1000000007ll;
                            }
                        }
                    }
                }
                n>>=1;
                for(i=1;i<3;i++)for(j=1;j<3;j++)c[i][j]=a[i][j];
                memset(a,0,sizeof(a));
                for(i=1;i<3;i++){
                    for(j=1;j<3;j++){
                        for(k=1;k<3;k++){
                            a[i][j]+=c[i][k]%1000000007ll*c[k][j]%1000000007ll;
                            a[i][j]%=1000000007ll;
                        }
                    }
                }
            }
            y=(b[1][1]+b[2][1])%1000000007ll;//求b 
        }
        r=1;
        while(y){//快速幂求a的b次方 
            if(y&1)r=r*x%1000000007ll;
            y>>=1;
            x=x*x%1000000007ll;
        }
        cout<<r<<'\n';
    }
}