SinzoL--题解 2540: 信息学奥赛一本通T1644-佳佳的 Fibonacci

好像还没有人发这题的题解，那我就捷足先登了，我用的不是矩阵

这题是2539的升级版，qwq

由F(n)=F(n-1)+F(n-2),

且F(n-1)=F(n-2)+F(n-3),

且F(n-2)=F(n-3)+F(n-4),

………

且F(3)=F(2)+F(1),以上式子叠加，化简得到F(n)前n项和Sn=F(n+2)-F(1),即为2539答案;

对于这题，T(n)=F(1)+2×F(2)+3×F(3)+…+n×F(n)

由阿贝尔变换易得：令An=(1到n)∑F(n),则T(n)=An×n-(1到n-1)∑Ai×1;

再化简得Tn=n*F(n+2)-F(n+3)+F(1)+F(2);

下面是代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,p;
map<ll,ll> mp;
ll calc(ll n){
    if (mp[n]) {
        return mp[n];
    }
    ll tmp=n;
    n=n>>1;
    if (tmp%2) return mp[tmp]=calc(n)*calc(n)%p+calc(n+1)*calc(n+1)%p;
    else return mp[tmp]=(2*calc(n-1)+calc(n))*calc(n)%p;
}//这是别人的方法，复杂度也是logn我借用了一下
int main(){
    cin>>n>>p;
    mp[1]=mp[2]=1;
    long long ans_1=calc(n+2)%p;//
    long long ans_2=calc(n+3)%p;//
    long long ans=n*ans_1-ans_2+2;//推导结果的体现
    ans%=p;
    ans+=ans<0?p:0;//防止得到负数
    cout<<ans<<endl;
    return 0;
}

想学快速求第n项方法的，传送门
新手写题解，欢迎吐槽