题解 P5775 【[AHOI2006]斐波卡契的兔子】

Alarm5854 · 2019-12-08 13:31:44 · 题解

这道题目可以递推，只不过还要有高精度算法，不知道高精的人可以看高精度模板。

具体怎样递推呢，下面来看一下：

现在规律可以看出来了，规律是

初值 r_{0,1}=1
所以只要递推就可以了，但是，a 最大为 100，m 最大为 3000，最终答案可能会达到10^{6000}，最大空间开销为 4\times3\times3000\times6000=2.16\times10^8B，会爆空间，所以，要用到滚动数组的方法，减小空间的开销.

还有，高精除在除不尽的情况下答案要加1。

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
struct huge{//高精度部分可以看模板
    int a[7654];
    int& operator [](int n){
        return a[n];
    }
    bool operator <(huge b){
        if(a[0]<b[0]) return 1;
        if(a[0]>b[0]) return 0;
        for(int i=a[0];i;--i){
            if(a[i]<b[i]) return 1;
            if(a[i]>b[i]) return 0;
        }
        return 0;
    }
    huge(){
        memset(a,0,sizeof(a));
        a[0]=1;
    }
    huge(int x){//把低精转高精
        memset(a,0,sizeof(a));
        while(x){
            a[++a[0]]=x%10;
            x/=10;
        }
        if(!a[0]) a[0]=1;
    }
    huge(int *t){
        memcpy(a,t,sizeof(a));
    }
    huge operator *(int x){
        huge b=huge(a);
        for(int i=1;i<=b[0];++i)
            b[i]*=x;
        for(int i=1;i<=b[0];++i)
            b[i+1]+=b[i]/10,b[i]%=10;
        while(b[b[0]+1]) b[b[0]+1]+=b[b[0]]/10,b[b[0]]%=10,++b[0];
        while(!b[b[0]]&&b[0]>1) --b[0];
        return b;
    }
    huge operator +(huge b){
        huge c;
        c[0]=max(a[0],b[0]);
        for(int i=1;i<=c[0];++i)
            c[i]=a[i]+b[i];
        for(int i=1;i<=c[0];++i)
            c[i+1]+=c[i]/10,c[i]%=10;
        while(c[c[0]+1]) ++c[0];
        return c;
    }
    huge operator -(huge b){
        huge c=huge(a);
        for(int i=1;i<=c[0];++i){
            c[i]-=b[i];
            if(c[i]<0)
                --c[i+1],c[i]+=10;
        }
        while(!c[c[0]]&&c[0]>1) --c[0];
        return c;
    }
    huge operator /(huge b)
    {
        huge c,d=huge(a),t;
        c=huge();
        c[0]=a[0]-b[0]+1;
        if(c[0]<1)
        {
            c[0]=1;
            return c+huge(1);
        }
        for(int i=c[0];i>0;--i)
        {
            t=huge();
            for(int j=1;j<=b[0];++j)
                t[i+j-1]=b[j];
            t[0]=i+b[0]-1;
            while(!(d<t)) ++c[i],d=d-t;
        }
        while(!c[c[0]]&&c[0]>1) --c[0];
        if(huge(0)<d) c=c+huge(1);//注意如果余数不为0，答案要加1
        return c;
    }
};
istream& operator >>(istream& is,huge& a){
    string s;
    is>>s;
    if(s[0]=='-')
        a[-1]=-1,s.erase(s.begin());
    a[0]=s.length();
    for(int i=0;i<a[0];++i)
        a[a[0]-i]=s[i]-48;
    return is;
}
ostream& operator <<(ostream& os,huge a){
    if(!~a[-1]) os<<'-';
    for(int i=a[0];i;--i)
        os<<a[i];
    return os;
}
int a,b,c,m;
huge k,ans,d1,d2,d3,d4;//这里直接省略数组，所以在m为1或2时需要特判
int main(){
    cin>>a>>b>>c>>m>>k;//重载运算符后，高精数可以与普通的数字一起输入
    if(m==1){
        cout<<a+1<<endl;
        ans=k/huge(a+1);
        cout<<ans<<endl;
        return 0;
    }
    if(m==2){
        cout<<a*a+a+b+1<<endl;
        ans=k/huge(a*a+a+b+1);
        cout<<ans<<endl;
        return 0;
    }
    d1=huge(a*a+b),d2=huge(a),d3=huge(1);
    for(int i=3;i<=m;++i){
        d4=d1;
        d1=d1*a+d2*b+d3*c;
        d3=d3+d2,d2=d4;
    }
    d4=d1+d2+d3;
    cout<<d1+d2+d3<<endl;
    ans=k/d4;
    cout<<ans<<endl;
    return 0;
}

这段代码的时间复杂度为 O(m\log_{10}(a^m))，且常数较大，最慢的点跑了800ms，通过本题有点危险，可以优化一下。