题解 P6361 [CEOI2018]Fibonacci representations

· · 题解

为行文方便，用如下形式

b_1&b_2&\cdots&b_{k-1}&b_k&b_{k+1}&\cdots\\ 1&2&\cdots&k-1&k&k+1&\cdots \end{matrix}

表示 p=b_1F_1+b_2F_2+\cdots+b_{k-1}F_{k-1}+b_kF_k+b_{k+1}F_{k+1}+\cdots 。

首先对于单个斐波那契数 F_k，显然它可以被自己表示：

\begin{matrix} \cdots&0&0&0&0&1&0&\cdots\\ \cdots&k-4&k-3&k-2&k-1&k&k+1&\cdots \end{matrix}

我们将 F_k 展开为 F_{k-1}+F_{k-2}，便得到一个另一个表示它的方案：

\cdots&0&0&1&1&0&0&\cdots\\ \cdots&k-4&k-3&k-2&k-1&k&k+1&\cdots \end{matrix}

下一个方案是什么？因为题目要求用不同的斐波那契数表示，即没有重复，
我们只能将 F_{k-2} 展开为 F_{k-3}+F_{k-4}，因此下一个方案只能是

\cdots&1&1&0&1&0&0&\cdots\\ \cdots&k-4&k-3&k-2&k-1&k&k+1&\cdots \end{matrix}

以此类推，我们发现所有方案都一定满足

\begin{matrix} \cdots&1&1&0&1&0&\cdots&1&0&1&0&0&\cdots\\ \cdots&i&i+1&i+2&i+3&i+4&\cdots&k-3&k-2&k-1&k&k+1&\cdots \end{matrix}

的形式。

接下来考虑多个不相邻且不相同的斐波那契数的情形：

\begin{matrix} \cdots&0&1&0&\cdots&0&1&0&\cdots\\ \cdots&i-1&i&i+1&\cdots&k-1&k&k+1&\cdots \end{matrix}

若我们将 F_k 展开，为保证没有重复，其展开会被 F_i “堵住”：

\begin{matrix} \cdots&0&1&0&1&1&0&1&\cdots&0&1&0&\cdots\\ \cdots&i-1&i&i+1&i+2&i+3&i+4&i+5&\cdots&k-2&k-1&k&\cdots \end{matrix}

接下来我们将 F_i 展开，但由展开形式得知，它是会留下 \cdots101010 的轨迹，
因此 F_k 受到的堵塞最多有一个单位距离的缓解：

\begin{matrix} \cdots&0&1&0&1&0&0&1&1&0&1&\cdots\\ \cdots&i-4&i-3&i-2&i-1&i&i+1&i+2&i+3&i+4&i+5&\cdots \end{matrix}

因此，对于多个不相邻且不相同的斐波那契数

p=F_{a_1}+F_{a_2}+\cdots+F_{a_n}\quad(\forall i\in[1,n)\cap\mathrm{N},a_{i+1}-a_i\ge 2) 于是设 $f_i$ 为 $F_{a_i}$ 不展开时表示 $F_{a_1}+F_{a_2}+\cdots+F_{a_i}$ 的总方案数， $g_i$ 为 $F_{a_i}$ 展开时表示 $F_{a_1}+F_{a_2}+\cdots+F_{a_i}$ 的总方案数，则 $$ \begin{cases} f_i=f_{i-1}+g_{i-1}\\ g_i=\left\lfloor\dfrac{a_i-a_{i-1}-1}{2}\right\rfloor f_{i-1}+\left\lfloor\dfrac{a_i-a_{i-1}}{2}\right\rfloor g_{i-1} \end{cases} $$ 显然转移可以表示为矩阵 $$ \begin{bmatrix} 1&1\\\left\lfloor\dfrac{a_i-a_{i-1}-1}{2}\right\rfloor &\left\lfloor\dfrac{a_i-a_{i-1}}{2}\right\rfloor \end{bmatrix}{f_{i-1}\brack g_{i-1}}={f_i\brack g_i} $$ 直接用平衡树维护转移矩阵即可通过子任务 3、5 。 -------------------------------- 最后考虑存在相同或相邻的斐波那契数的情形。 根据[斐波那契编码](https://oi-wiki.org/math/fibonacci/#_9)，我们总有办法把 $\displaystyle p_k=\sum_{i=1}^kF_{a_k}

唯一表示成不相同且不相邻的斐波那契数。

类似 [NOI2021] 密码箱， 用平衡树维护形如

\begin{matrix} \cdots&1&0&1&0&1&0&1&\cdots\\ \cdots&i&i+1&i+2&i+3&i+4&i+5&i+6&\cdots \end{matrix}

的连续段。

考虑插入 F_{a_i}，如果其破坏了不相邻的性质：

\begin{matrix} \cdots&1&1&1&0&1&0&1&0&0&\cdots\\ \cdots&a_i-1&a_i&a_i+1&a_i+2&a_i+3&a_i+4&a_i+5&a_i+6&a_i+7&\cdots \end{matrix}

显然它可以和后面的不断合并，直到连续段的末尾：

\begin{matrix} \cdots&1&0&0&0&0&0&0&1&0&\cdots\\ \cdots&a_i-1&a_i&a_i+1&a_i+2&a_i+3&a_i+4&a_i+5&a_i+6&a_i+7&\cdots \end{matrix}

如果其破坏了不相同的性质：

\begin{matrix} \cdots&0&0&1&0&1&0&1&0&2&0&\cdots\\ \cdots&a_i-8&a_i-7&a_i-6&a_i-5&a_i-4&a_i-3&a_i-2&a_i-1&a_i&a_i+1&\cdots \end{matrix}

我们将 F_{a_i} 一直展开到连续段的开头，展开方案就会刚好覆盖路径上所有的 0：

\begin{matrix} \cdots&1&1&1&1&1&1&1&1&1&0&\cdots\\ \cdots&a_i-8&a_i-7&a_i-6&a_i-5&a_i-4&a_i-3&a_i-2&a_i-1&a_i&a_i+1&\cdots \end{matrix}

接下来从后往前合并这些 1：

\begin{matrix} \cdots&1&0&0&1&0&1&0&1&0&1&\cdots\\ \cdots&a_i-8&a_i-7&a_i-6&a_i-5&a_i-4&a_i-3&a_i-2&a_i-1&a_i&a_i+1&\cdots \end{matrix}

相比于插入前，相当于 F_{a_i} 前面的往后走一个单位距离，并在最前面留下一个 1。

特别的，连续段的末尾为 F_1 或 F_2 的情况要特别处理，这里留给读者自行思考。

处理完这些情况后，还要处理连续段与前趋后继的合并，所以代码实现要亿点分类讨论。

Code

#include<stdio.h>
#include<string.h>
#include<random>
typedef unsigned int word;
const word mod=1e9+7;
struct matrix{//矩阵
    word num[4];
    inline matrix(){}
    inline matrix(word a,word b,word c,word d){
        num[0]=a,num[1]=b,num[2]=c,num[3]=d;}
    #define mul(a,b) (1ull*num[a]*p.num[b])
    #define plus(a,b,c,d) (mul(a,b)+mul(c,d))%mod
    inline matrix operator()(const matrix &p)const{
        return matrix(
            plus(0,0,1,2),plus(0,1,1,3),
            plus(2,0,3,2),plus(2,1,3,3));}
    #undef mul
    #undef plus
}const I(1,0,0,1);
struct READ{//快读快写
    char c;
    inline READ(){c=getchar();}
    template<typename type>
    inline READ& operator >>(type &num){
        while('0'>c||c>'9') c=getchar();
        for(num=0;'0'<=c&&c<='9';c=getchar())
            num=num*10+(c-'0');
        return *this;
    }
}cin;
std::mt19937 RAND(std::random_device{}());
struct treap{
    treap *l,*r;
    word f,cnt,end,blc;
    //f 第一个 1 的位置
    //cnt 1 的个数
    //end 最后一个 1 的位置
    matrix val,sum;
    //val 当前连续段的转移矩阵之积
    //sum 整棵平衡树的转移矩阵之积
    inline treap(){blc=RAND();}
    inline void calc(const word d){//计算转移矩阵 (a_i-a_{i-1}=d)
        end=f? f+((cnt-1)<<1):0;
        sum=val=matrix(
            (1ull*(cnt-1)*((d-1)/2)+1)%mod,
            (1ull*(cnt-1)*(d/2)+1)%mod,
            (d-1)/2,d/2);
    }
    inline void pushup(){
        sum=val;
        if(l) sum=sum(l->sum);
        if(r) sum=r->sum(sum),end=r->end;
        else end=f? f+((cnt-1)<<1):0;
    }
}p[1u<<17];
inline treap* merge(treap *l,treap *r){
    if(l==0) return r;
    if(r==0) return l;
    if(l->blc<=r->blc){
        l->sum=r->sum(l->sum);
        l->end=r->end;
        return l->r=merge(l->r,r),l;
    }
    r->sum=r->sum(l->sum);
    return r->l=merge(l,r->l),r;
}
inline treap* split(treap *&rt,word size){
    //分离 f>size 的连续段
    if(rt==0) return 0;
    treap *out=0;
    if(size<rt->f){
        out=split(rt->l,size);
        treap *swap=rt->l;
        rt->l=out,out=swap;
        swap=rt,rt=out,out=swap;
        return out->pushup(),out;
    }
    if(size==rt->f) out=rt->r,rt->r=0;
    else out=split(rt->r,size);
    return rt->pushup(),out;
}
inline treap* splitend(treap *&rt){
    if(rt->r){
        treap *out=splitend(rt->r);
        return rt->pushup(),out;
    }
    treap *out=rt;
    rt=rt->l,out->l=0;
    return out->pushup(),out;
}
inline treap* splitbegin(treap *&rt){
    if(rt->l){
        treap *out=splitbegin(rt->l);
        return rt->pushup(),out;
    }
    treap *out=rt;
    rt=rt->r,out->r=0;
    return out->pushup(),out;
}
word n,psiz;
treap *rt=p,*mid,*right;
inline void getend(){//讨论 mid 与后继的拼接情况
    treap *mid_=right;
    right=split(mid_,mid->f+(mid->cnt<<1));
    if(mid_) mid->cnt+=mid_->cnt;
    mid->calc(mid->f-rt->end);
    if(right){
        treap *nxt=splitbegin(right);
        nxt->calc(nxt->f-mid->end);
        mid=merge(mid,nxt);
    }
    rt=merge(merge(rt,mid),right);
}
inline void insert(word val){
    mid=split(rt,val);
    right=split(mid,val+1);
    if(mid) mid->f=mid->end+1,mid->cnt=1;//在连续段的最前面
    else if((rt==p&&rt->r==0)||val>rt->end+2)//没有插入到已有的连续段中
        mid=p+(++psiz),mid->f=val,mid->cnt=1;
    else if(mid=splitend(rt),val==mid->end+2) ++mid->cnt;
        //拼接到连续段的末尾
    else if((val-mid->f)&1){//破坏了不相邻的性质
        if(val!=mid->end+1){//在连续段中间
            mid->cnt=(val+1-mid->f)/2;
            val=mid->end+1;
            mid->calc(mid->f-rt->end);
            rt=merge(rt,mid);
        }else if(++val,mid->cnt!=1){//在连续段末尾
            --mid->cnt,mid->calc(mid->f-rt->end);
            rt=merge(rt,mid);
        }
        mid=right,right=split(mid,val+1);
        if(mid) mid->f=mid->end+1;
        else mid=p+(++psiz),mid->f=val;
        mid->cnt=1;
    }else if(val==mid->end){//破坏了不相接的性质（在连续段末尾）
        if(mid->f!=1&&mid->f!=2)
            return val=mid->f-2,++mid->f,getend(),insert(val);
        //开头不为 1 或 2 的情况
        if(mid->f==1) ++mid->f;
        else --mid->f,++mid->cnt;
        //开头为 1 或 2 的情况
    }else{//破坏了不相接的性质（在连续段中间）
        treap *nxt=p+(++psiz);
        nxt->f=mid->end+1,nxt->cnt=1;
        mid->cnt=(val-mid->f)/2;
        if(mid->f!=1&&mid->f!=2){
            if(val=mid->f-2,++mid->f,mid->cnt){
                mid->calc(mid->f-rt->end);
                rt=merge(rt,mid);
            }
            return mid=nxt,getend(),insert(val);
        }
        //开头不为 1 或 2 的情况
        if(mid->f==2){
            --mid->f,++mid->cnt;
            mid->calc(mid->f-rt->end);
            rt=merge(rt,mid);
        }else if(++mid->f,mid->cnt){
            mid->calc(mid->f-rt->end);
            rt=merge(rt,mid);
        }
        mid=nxt;
        //开头为 1 或 2 的情况
    }
    getend();
}
int main(){
    cin>>n;
    rt->f=0,rt->cnt=1,rt->end=0;
    rt->val=rt->sum=I;
    for(word val;n;--n){
        cin>>val,insert(val);
        printf("%u\n",(rt->sum.num[0]+rt->sum.num[2])%mod);
    }
    return 0;
}