因為費式進位制的進位動作會同時動到高位跟低位，所以這題大部分人的作法每次都要檢查全部的位數是否符合規則，總時間複雜度會是 O(n^2)；

但是！！！就在今天，被我搜到一篇 CMU CS 系的碩士論文，http://reports-archive.adm.cs.cmu.edu/anon/2020/CMU-CS-20-118.pdf#page=19

它在這一頁 Algorithm 3 很巧妙的提出了如何從高位 (MSB) 到低位 (LSB) 依序把超過 1 的數字清掉，使得最後只剩下 0 跟 1 的 digit；(論文的方法)

再從低位 (LSB) 到高位 (MSB) 每次抓一段連續的 1，並從該段的高位到低位依序把兩個連續的 1 轉成不連續的 1，最後就得到合法的進位制。(我想到的方法)

證明的精華在於為什麼論文能順利地清除所有超過 1 的數字，非常漂亮，自己想的話很難想到。

------------------------------------------------------------------------------------------------------------------------------------------------------------

另外這題有開啟嚴格比對，測資間要輸出一空行，但最後一筆的結尾不要有空行，否則會有 OLE。

怕網頁失效來補個標題：

Linear Time Addition of Fibonacci Encodings,

Maoyuan (Raymond) Song,

CMU-CS-20-118,

May 2020