题解 P3938 【斐波那契】

· · 题解

用此篇题解纪念我已经被忘却的关于这个题目的一篇题解

甚至也被洛谷遗忘在回收站里了

首先我们要看到大佬的题解

所有大佬（包括管理员大大发的题解）都点出了一个重点：
—— 父亲和儿子的标号都相差一个斐波那契数

看起来这是一个不知道原因的规律，实际上这是可以被证明的（不想看证明的可跳过）

首先显而易见的是，前几轮的兔子中每一轮有F_{N+1}只兔子，要生F_N只兔子，也符合“父亲和儿子的标号都相差一个斐波那契数”这一条件

然后如果第N轮的兔子符合条件，那么此时会有F_{N+1}只兔子，还要生F_N只兔子

由于每一轮的兔子编号是按父亲的编号大小编的，所以1号兔子会多一个F_{N+1}+1号的儿子，2号兔子会多一个F_{N+1}+2号的儿子……F_{N+1}号兔子会多一个F_{N+1}+F_N号兔子，其中父亲与儿子的编号都相差F_N

而此时，原来F_{N+1}只兔子都已经“长大成兔”了，就可以再生F_{N+1}只兔子，兔子总数也由F_{N+1}只兔子变为了F_{N+1}+F_N=F_{N+2}只兔子，也符合前提，因此，第N+1轮时条件也成立

通过数学归纳法，我们证明了这个规律

然后介绍一下“斐波那契编码”（我更喜欢叫做“斐波那契进制”）

百度百科：斐波那契编码——百度百科

好，结束了 捕捉极其不想打字的蒟蒻一枚

最后来看一下我的蒂花之秀的解法

首先我们要记住一个方法：对带编号的数论问题，把编号改成由0起始对结果可能有意想不到的惊喜和AK比赛的更大的惊喜

我们来试试这个方法：

是不是发现了什么？好像每一个父亲都是儿子的后缀？

其实这很好解释

每一只兔子都和他的父亲相差一个斐波那契数，在出生轮数也会相差至少两轮，这就相当于说每一只兔子的编号都是它的父亲的编号+一个不会产生进位的斐波那契数，在编号上就表现为父亲编号是儿子编号的前缀

所以说，我们只要知道一个数的编号，就可以知道它的所有祖先的信息，最后只要暴力匹配就可以了，编程难度瞬间减小但思维难度比原来更高了

最后附代码： 

#include<bits/stdc++.h>
using namespace std;
template<typename type>
type get(type &out){
    type sign=1,num=0;
    char input='\0';
    bool over=false,finds=false;
    while((input=getchar())<=32);
    do{
        switch(input){
            case '+':sign=-sign;
            case '-':sign=-sign;
                        if(!finds)
                            finds=true;
                        else
                            over=true;
                break;
            case '0':case '1':case '2':case '3':case '4':
            case '5':case '6':case '7':case '8':case '9':
                        num=num*10+(input^48);
                break;
            default:
                over=true;
                break;
        }
    }while((input=getchar())>32&&!over);
    return out=sign*num;
}//并没有什么卵用的快读
template<typename type>
type put(const type &in){
    type sign=1;
    if(in<0)sign=-sign,putchar('-');
    if(in*sign>=10)put(in*sign/10);
    putchar((in*sign%10)^48);
    return in;
}//比快读更没卵用的快输
const long long MAXN=300000;
long long FBNQ[70]={0,1,2};
long long A[70],B[70];
int main(){
    for(int i=3;i<60;++i)
        FBNQ[i]=FBNQ[i-1]+FBNQ[i-2];
    //将斐波那契数初始化
    int n=0;
    get(n);
    while(n--){
        long long a=0,b=0,ans=1;
        get(a),get(b);
        //输入数据
        --a,--b;
        //将编号改成从0开始
        for(int i=59;i>0;--i)
            A[i]=a/FBNQ[i],a%=FBNQ[i];
        for(int i=59;i>0;--i)
            B[i]=b/FBNQ[i],b%=FBNQ[i];
        //将编号化成斐波那契进制
        for(int i=0;i<60;++i,ans+=FBNQ[i]*A[i])
            if(A[i+1]!=B[i+1])
                break;
        //强行匹配
        put(ans);putchar('\n');
        //输出答案
    }
    return 0;
}

时间复杂度O(Mlog_\Phi N)
空间复杂度O(log_\Phi N)

效果近似于LCA的解法，但是代码难度小，常数也小一些

最后的闲言

实际上我当时一开始想的也是LCA，但是我太蒟了，不会这些解法，于是发现了数论解法

所以说，蒟蒻也是有春天的（滑稽）