社区讨论

求助

jjackqhr01
P1962斐波那契数列参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo21ykss
此快照首次捕获于
2023/10/23 06:40
2 年前
此快照最后确认于
2023/11/03 07:02
2 年前
查看原帖
9AC+1WA
CPP
#include <bits/stdc++.h>
#define LL long long int
using namespace std;
const LL mod=1e9+7;
map<LL,LL> mp;
LL f(LL x){
    if(mp.count(x)){
        return mp[x];
    }
    LL s=0;
    if(x&1){
        s=(f((x-1)/2)*f((x-1)/2)%mod+f((x+1)/2)*f((x+1)/2)%mod)%mod;
    }
    else{
        s=f(x/2)*(2*f(x/2+1)%mod-f(x/2)%mod)%mod;
    }
    return mp[x]=s;
}
int main(){
    LL m;
    cin>>m;
    mp[0]=0,mp[1]=mp[2]=1;
    if(mp.count(m)) cout<<mp[m];
    else{
        cout<<(f(m)%mod);
    }
    return 0;
}

回复

共 1 条回复，欢迎继续交流。

正在加载回复...