P6361 [CEOI 2018] Fibonacci representations 題解

知識點

Fibonacci 數列，平衡樹，齊肯多夫定理，連續段 DP，矩陣優化 DP，動態 DP。

分析

定義

為方便，我們學習一下大佬的表示形式：

\[\begin{matrix} b_1 & b_2 & \ldots & b_{k-1} & b_k & b_{k+1} & \ldots \\ 1 & 2 & \ldots & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \]
表示：

\[p = \sum_{i} b_i \cdot F_{i} \\ \]
定義 \(F_{n+2}\) 的分裂：變為 \(F_{n} + F_{n+1}\)。

引入

我們從題目給定的條件考慮一下，很明顯，有一種逐個插入的意味，那么我們就可以從這個角度來思考。

分裂

既然是逐個插入，就必定有最簡單的只有一種的情況，我們先來看看這種：

\[\begin{matrix} 0 & 0 & \ldots & 0 & 1 & 0 & \ldots \\ 1 & 2 & \ldots & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \]

它在過程中一直符合題目要求的前提（沒有重復的斐波那契數）下可以如何分裂？

分裂一次：

\[\begin{matrix} 0 & 0 & \ldots & 1 & 1 & 0 & \ldots \\ 1 & 2 & \ldots & {k-2} & {k-1} & {k} & \ldots \\ \end{matrix} \]
似乎沒什么。
分裂兩次：

\[\begin{matrix} 0 & 0 & \ldots & 1 & 1 & 0 & 1 & \ldots \\ 1 & 2 & \ldots & {k-4} & {k-3} & {k-2} & {k-1} & \ldots \\ \end{matrix} \]
發現一個問題：如果我們把 \(k-1\) 對應的 \(1\) 去掉，就又變成了“分裂一次”的情況。
分裂 \(n\) 次……

所以我們可以得出結論：一個斐波那契數分裂過程中，在所有它分裂出來的數中，只有最小的那個可以再分裂。

那么這種情況的答案就很簡單，為 \(\lfloor \frac{k-1}{2} \rfloor + 1\)。

去重

我們緊接著再看下一步，插入第二個，我們可以粗略分成兩種：

插入的第二個與第一個不同：

\[\begin{matrix} 0 & 0 & \ldots & 0 & 1 & 0 & \ldots & 0 & 1 & 0 & \ldots \\ 1 & 2 & \ldots & {k-1} & k & {k+1} & \ldots & {m-1} & m & {m+1} & \ldots \\ \end{matrix} \]
感覺這種仍舊是沒什么……
插入的第二個與第一個相同：

\[\begin{matrix} 0 & 0 & \ldots & 0 & 2 & 0 & \ldots \\ 1 & 2 & \ldots & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \]
似乎兩個相同的不是很好，這樣分解起來不如上面舒暢。

這種有相同的就不便于分解，所以我們嘗試讓它分裂：

\[\ \begin{matrix} 0 & 0 & \ldots & 0 & 2 & 0 & \ldots \\ 1 & 2 & \ldots & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \\ \Downarrow \\ \begin{matrix} 0 & 0 & \ldots & 1 & 1 & 1 & 0 & \ldots \\ 1 & 2 & \ldots & {k-2} & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \\ \]

考慮上面的性質，我們可以聯想到：是不是對于任何正整數，都有一種把它表示成不同 Fibonacci 數的和方案呢？

答案是肯定的。

合并

分裂后發現還有兩個可以合并，我們再把它們合起來，最終得到：

\[\begin{matrix} 0 & 0 & \ldots & 1 & 0 & 0 & 1 & \ldots \\ 1 & 2 & \ldots & {k-2} & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \\ \]

從這個現象，以及上一步中我們得到的結論，又可以進一步猜想：是不是對于任何正整數，都有一種把它表示成不同且互不相鄰的斐波那契數的和的方案呢？

答案還是肯定的，這個就是齊肯多夫（Zeckendorf）定理的一部分，具體證明可以百度。

完整的齊肯多夫定理是：

任何正整數都可以表示成若干個不連續的斐波那契數（不包括第一個斐波那契數，即本題中不存在的那個 \(F_0\)）之和。這種和式稱為齊肯多夫表述法。

對于任何正整數，其齊肯多夫表述法都可以由貪心算法（即每次選出最大可能的斐波那契數）得到。

——齊肯多夫定理_百度百科 (baidu.com)。

DP 設計

發現對于 \(p\)，它的齊肯多夫表述法可以讓我們對它求出本題答案：

設 \(p\) 的齊肯多夫表述法按升序排序后為 \(\set{Z_i}\)，共有 \(m\) 項。
設 \(f_{i,0/1}\) 分別表示 \(Z_i\) 有沒有分裂時的方案數，\(0\) 代表沒有，\(1\) 代表有。
設 \(\Delta_i = Z_i-Z_{i-1}(i>1)\)，特別地，\(i=1\) 時 \(\Delta_1 = Z_1\)。

那么就有初態和方程：

\[f_{0,0} = 1,f_{0,1} = 0 \\ \begin{cases} f_{i,0} = f_{i-1,0} + f_{i-1,1} \\ f_{i,1} = \lfloor \frac{\Delta_i - 1}{2} \rfloor f_{i-1,0} + \lfloor \frac{\Delta_i}{2} \rfloor f_{i-1,1} \\ \end{cases} \]

最終答案即為 \(f_{m,0} + f_{m,1}\)。

我們可以用矩陣表示：

\[\begin{bmatrix} 1 & 1 \\ \lfloor \frac{\Delta_i - 1}{2} \rfloor& \lfloor \frac{\Delta_i}{2} \rfloor\\ \end{bmatrix} \begin{bmatrix} f_{i-1,0} \\ f_{i-1,1} \\ \end{bmatrix} = \begin{bmatrix} f_{i,0} \\ f_{i,1} \\ \end{bmatrix} \]

（我們直接把這個塞到平衡樹中就可以拿到子任務 3 和 5 的分數。）

動態維護

我們現在已經有了有靜態的齊肯多夫表述法集合，考慮維護支持插入的動態的齊肯多夫表述法集合。

假設現在要在原齊肯多夫表述法集合 \(Z\) 插入第 \(k\) 個斐波那契數。

原集合中不包含第 \(k-1,k,k+1\) 個斐波那契數。

\[\begin{matrix} b_{1} & b_{2} & \ldots & 0 & 0 & 0 & \ldots \\ 1 & 2 & \ldots & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \]
直接加入即可。
原集合中包含第 \(k+1\) 個斐波那契數。

\[\begin{matrix} b_{1} & b_{2} & \ldots & b_{k-1} & 0 & 1 & \ldots \\ 1 & 2 & \ldots & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \]
那么我們不斷往后合并 ~~，總有一天會合并完的~~。
原集合中不包含第 \(k+1\) 個斐波那契數，但是包含第 \(k-1\) 個。

\[\begin{matrix} b_{1} & b_{2} & \ldots & 1 & 0 & 0 & \ldots \\ 1 & 2 & \ldots & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \]
那么我們不斷往后合并 ~~，總有一天會合并完的~~。
原集合中包含第 \(k\) 個斐波那契數。

\[\begin{matrix} b_{1} & b_{2} & \ldots & 0 & 1 & 0 & \ldots \\ 1 & 2 & \ldots & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \]
這種情況有點特殊，想象一下我們把第 \(k\) 個分裂成 \(k-1\) 和 \(k-2\) 后，發現原本就有一個 \(k-2\) 存在，這該怎么辦？

設 \(q\) 滿足以下條件：
1. \(q \equiv k\pmod 2\)。
2. \(\forall i \in [1,\frac{k-q}{2}],(k-2i)\in Z\)。
3. \(q\) 是所有滿足條件 1 和 2 的值中最小的那個。
又分兩種情況：
- \(q>2\)：
  
  會變成：
  
  \[\begin{matrix} b_{1} & b_{2} & \ldots & 1 & 0 & 0 & 1 & \ldots & 1 & 0 & 1 & \ldots \\ 1 & 2 & \ldots & q-2 & q-1 & q & q+1 & \ldots & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \]
  但是這個并不能像上面一樣暴力地修改……
  
  考慮矩陣轉移，發現其只由該值和上一個值的差值 \(\Delta\) 決定，而整個序列改變差值的或插入的最多只有 \(3\) 個，即：
  1. 插入一個 \(q-2\)。
  2. \(q(\to q+1)\) 的差值可能改變。
  3. \(k+1\) 后面的差值會改變。
- \(q = 1\)：我們把插入的 \(k\) 不斷分裂，得到：
  
  \[\begin{matrix} 2 & 1 & 1 & \ldots & 1 & 1 & 0 & \ldots \\ 1 & 2 & 3 & \ldots & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \]
  再從后面逐個合并，又會得到：
  
  \[\begin{matrix} 0 & 1 & 0 & \ldots & 1 & 0 & 1 & \ldots \\ 1 & 2 & 3 & \ldots & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \]
  修改其實是一樣修改差值的思路：
  1. \(1(\to 2)\) 的差值會改變。
  2. \(k+1\) 后面的差值會改變。
- \(q = 2\)：同理可得：
  
  \[\begin{matrix} 1 & 0 & 1 & \ldots & 1 & 0 & 1 & \ldots \\ 1 & 2 & 3 & \ldots & {k-1} & k & {k+1} & \ldots \\ \end{matrix} \]
  修改：
  1. 插入一個 \(1\)。
  2. \(k+1\) 后面的差值會改變。
如果原本還存在 \(k+2\) 的話，只要在此基礎上再處理一下即可。

實現方式

用平衡樹中維護一些差值為 \(2\) 的連續段即可實現動態維護。

中間的一些情況處理完之后會變成其他情況，所以我們可以用遞歸的形式實現。

那么轉換成連續段后，每個轉移矩陣的值需要重新定義：假設一個連續段與上一個中間有 \(\Delta\) 個 \(0\)，共包含 \(c\) 個 \(1\)，則矩陣變為：

\[\ \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ \end{bmatrix}^{c-1} \begin{bmatrix} 1 & 1 \\ \lfloor \frac{\Delta}{2} \rfloor & \lfloor \frac{\Delta + 1}{2} \rfloor\\ \end{bmatrix} \\ = \begin{bmatrix} 1 & c-1 \\ 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 & 1 \\ \lfloor \frac{\Delta}{2} \rfloor & \lfloor \frac{\Delta + 1}{2} \rfloor\\ \end{bmatrix} \\ = \begin{bmatrix} (c-1)\lfloor \frac{\Delta}{2} \rfloor+1 & (c-1)\lfloor \frac{\Delta + 1}{2} \rfloor+1 \\ \lfloor \frac{\Delta}{2} \rfloor & \lfloor \frac{\Delta + 1}{2} \rfloor\\ \end{bmatrix} \]

或者按照實際意義也可推得。

復雜度

那么暴力合并的均攤次數也就是 \(O(n)\) 的，其他修改單次次數也較少，則復雜度為 \(O(nw^3\log_2{n})\)，其中 \(w=2\)。

代碼

//#define Plus_Cat "fib"
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define uint unsigned int
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(1e5+10);

namespace IOE {
	//Fast IO...
} using namespace IOE;

namespace Modular {
	//Modular
} using namespace Modular;

int n;
mt19937 rng(random_device {}());

struct Mat {
	int d[4];

	Mat(int val=0) { d[0]=d[3]=val,d[1]=d[2]=0; }

	Mat(int d0,int d1,int d2,int d3) { d[0]=d0,d[1]=d1,d[2]=d2,d[3]=d3; }

	Mat(int del,int cnt) {
		int a(del>>1),b((del+1)>>1);
		--cnt,d[0]=add(mul(cnt,a),1),d[1]=add(mul(cnt,b),1),d[2]=a,d[3]=b;
	}

	int &operator [](int i) { return d[i]; }

	int const &operator [](int i) const { return d[i]; }

	friend Mat operator *(const Mat &A,const Mat &B) {
		return Mat(
			(int)add(mul(A[0],B[0]),mul(A[1],B[2])),(int)add(mul(A[0],B[1]),mul(A[1],B[3])),
			(int)add(mul(A[2],B[0]),mul(A[3],B[2])),(int)add(mul(A[2],B[1]),mul(A[3],B[3]))
		);
	}
};

struct Treap {
	int rt,tot;
	struct node {
		int sta,cnt,lst;
		Mat sel,pro;
		int ls,rs;
		uint blc;
		node(int sta=0,int cnt=0,int lst=0,Mat sel=Mat(1),Mat pro=Mat(1),int ls=0,int rs=0,uint blc=rng()):
			sta(sta),cnt(cnt),lst(lst),sel(sel),pro(pro),ls(ls),rs(rs),blc(blc) {}
		void Update(int _lst) { lst=sta?sta-2+(cnt<<1):0,pro=sel=Mat(sta-_lst-1,cnt); }
	} tr[N];

	Treap():rt(0),tot(0) {}
#define ls(p) (tr[p].ls)
#define rs(p) (tr[p].rs)
	void Init() { tr[rt=tot=1]=node(0,1,0); }

	void Up(int p) {
		tr[p].lst=(rs(p)?tr[rs(p)].lst:(tr[p].sta?tr[p].sta-2+(tr[p].cnt<<1):0));
		tr[p].pro=tr[p].sel;
		if(ls(p))tr[p].pro=tr[p].pro*tr[ls(p)].pro;
		if(rs(p))tr[p].pro=tr[rs(p)].pro*tr[p].pro;
	}

	int Merge(int p,int q) {
		if(!p||!q)return p|q;
		if(tr[p].blc<=tr[q].blc)
			return tr[p].lst=tr[q].lst,tr[p].pro=tr[q].pro*tr[p].pro,rs(p)=Merge(rs(p),q),p;
		return tr[q].pro=tr[q].pro*tr[p].pro,ls(q)=Merge(p,ls(q)),q;
	}

	int Split(int &p,int key) { //[<=key] -> p,[>key] -> o
		if(!p)return 0;
		int o(0);
		if(key<tr[p].sta)return o=Split(ls(p),key),o^=ls(p)^=o^=ls(p),p^=o^=p^=o,Up(o),o;
		if(key==tr[p].sta)return o=rs(p),rs(p)=0,Up(p),o;
		return o=Split(rs(p),key),Up(p),o;
	}

	int Split_begin(int &p) {
		int o(0);
		if(ls(p))return o=Split_begin(ls(p)),Up(p),o;
		return o=p,p=rs(p),rs(o)=0,Up(o),o;
	}

	int Split_end(int &p) {
		int o(0);
		if(rs(p))return o=Split_end(rs(p)),Up(p),o;
		return o=p,p=ls(p),ls(o)=0,Up(o),o;
	}

	int Cal() { return add(tr[rt].pro[0],tr[rt].pro[2]); }

	void Link(int &p,int &q) {
		int o(q);
		q=Split(o,tr[p].sta+(tr[p].cnt<<1));
		if(o)tr[p].cnt+=tr[o].cnt;
		tr[p].Update(tr[rt].lst),rt=Merge(rt,p);
		if(q)tr[o=Split_begin(q)].Update(tr[rt].lst),rt=Merge(rt,Merge(o,q));
	}

	void Insert(int key) {
		int p(Split(rt,key)),q(Split(p,key+1));
		if(p)return tr[p].sta=tr[p].lst+1,tr[p].cnt=1,Link(p,q);
		if((rt==1&&!rs(rt))||key>tr[rt].lst+2)return tr[p=++tot].sta=key,tr[p].cnt=1,Link(p,q);
		if(tr[p=Split_end(rt)].lst+2==key)return ++tr[p].cnt,Link(p,q);
		if((key-tr[p].sta)&1) {
			if(key!=tr[p].lst+1)
				tr[p].cnt=(key+1-tr[p].sta)>>1,key=tr[p].lst+1,tr[p].Update(tr[rt].lst),rt=Merge(rt,p);
			else if(++key,tr[p].cnt>1)--tr[p].cnt,tr[p].Update(tr[rt].lst),rt=Merge(rt,p);
			return p=q,q=Split(p,key+1),(p?tr[p].sta=tr[p].lst+1:tr[p=++tot].sta=key),tr[p].cnt=1,Link(p,q);
		}
		if(key==tr[p].lst) {
			if(tr[p].sta>2)return key=tr[p].sta-2,++tr[p].sta,Link(p,q),Insert(key);
			if(tr[p].sta==1)return tr[p].sta=2,Link(p,q);
			return tr[p].sta=1,++tr[p].cnt,Link(p,q);
		}
		int o(++tot);
		tr[o].sta=tr[p].lst+1,tr[o].cnt=1,tr[p].cnt=(key-tr[p].sta)>>1;
		if(tr[p].sta>2) {
			key=tr[p].sta-2,++tr[p].sta;
			if(tr[p].cnt)tr[p].Update(tr[rt].lst),rt=Merge(rt,p);
			return Link(p=o,q),Insert(key);
		}
		if(tr[p].sta==2)return tr[p].sta=1,++tr[p].cnt,tr[p].Update(tr[rt].lst),rt=Merge(rt,p),Link(p=o,q);
		tr[p].sta=2;
		if(tr[p].cnt)return tr[p].Update(tr[rt].lst),rt=Merge(rt,p),Link(p=o,q);
		return Link(p=o,q);
	}
#undef ls
#undef rs
} trp;

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	I(n),trp.Init();
	while(n--) {
		int key;
		I(key),trp.Insert(key),O(trp.Cal(),'\n');
	}
	return 0;
}

posted @ 2025-05-30 22:13 Add_Catalyst 閱讀(9) 評論(0) 收藏舉報

刷新頁面返回頂部

珈貓的小窩

歡迎來到珈貓的小窩

P6361 [CEOI 2018] Fibonacci representations 題解

P6361 [CEOI 2018] Fibonacci representations 題解

知識點

分析

定義

引入

分裂

去重

合并

DP 設計

動態維護

實現方式

復雜度

代碼

公告