1 条题解

  • 0
    @ 2025-8-24 22:20:03

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar warzone
    梦违科学世纪

    搬运于2025-08-24 22:20:03，当前版本为作者最后更新于2022-03-08 20:42:57，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    为行文方便，用如下形式

    $$\begin{matrix} 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$ 。

    首先对于单个斐波那契数 FkF_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}$$

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

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

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

    $$\begin{matrix} \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} $$

    若我们将 FkF_k 展开，为保证没有重复，其展开会被 FiF_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} $$

    接下来我们将 FiF_i 展开，但由展开形式得知，它是会留下 ⋯101010\cdots101010 的轨迹，
    因此 FkF_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) $$

    FaiF_{a_i} 展开的方案数只与 Fai−1F_{a_{i-1}} 是否展开 有关。

    于是设 fif_i 为 FaiF_{a_i} 不展开时表示 Fa1+Fa2+⋯+FaiF_{a_1}+F_{a_2}+\cdots+F_{a_i} 的总方案数，
    gig_i 为 FaiF_{a_i} 展开时表示 Fa1+Fa2+⋯+FaiF_{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 。

    最后考虑存在相同或相邻的斐波那契数的情形。

    根据斐波那契编码，我们总有办法把 pk=∑i=1kFak\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} $$

    的连续段。

    考虑插入 FaiF_{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} $$

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

    $$\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} $$

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

    $$\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} $$

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

    特别的，连续段的末尾为 F1F_1 或 F2F_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;
}
    • 1

    [CEOI 2018] Fibonacci representations

    信息

    ID
    5381
    时间
    2000ms
    内存
    250MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 24ms