主題
題目連結：
題目大意：
定義一個類似費氏數列（Fibonacci Sequence）的二元費氏字串（Binary Fibonacci String，BFS）為以下：
BFS(0) = "0" （非數字值，是一個數字字串）
BFS(1) = "1" （同上）
BFS(n) = BFS(n-2) + BFS(n-1) ，對於 n > 1 ，其中「+」代表左右兩字串連接在一起。
因此 BFS 的前五項為
"0" 、 "1" 、 "01" 、 "101" 、 "01101"
輸入第一列給定一正整數 T （T ≦ 100），代表有 T 筆測試資料，每筆佔一列。每列給定三整數 N 、 L 、 R （0 ≦ N 、 L 、 R < 2 ^ 31，且 L ≦ R < BFS(n) 之長度），代表要求 BFS(n) 第 L（含）～ 第 R（含）個字元（索引值從 0 開始）之內容為何？
範例輸入：
3
3 1 2
1 0 0
9 5 12
範例輸出：
01
1
10101101
解題思維：
觀察 BST 的前八項：
0 1
01 101
01101 10101101
0110110101101 101011010110110101101
而每個字串的長度為
1 1
2 3
5 8
13 21
為典型的費氏數列。
此時我們替換 BST 的每一項：
X0 Y0
X0Y0 Y0X0Y0
X1Y1 Y1X1Y1
X2Y2 Y2X2Y2
其中 Xi = Xi-1Yi-1 、 Yi = Yi-1Xi-1Yi-1 ，而 X0 = 0 、 Y0 = 1。
可以看到其自我相似的架構（遞迴之本質）。並且我們可以觀察出來：Xi 必為 Xi+1 之前綴 、 Yi 必為 Yi+1 之前綴，再加上 L 、 R 之範圍，n = 47 時之 |BST(n)| 就會超過 2 ^ 31。因此當 n = k > 47 時，其實跟求 n = 46 + (k % 2) 是一樣的（「%」代表取餘數）。
所以我們可以先得知給定的第 N 項屬於上面的哪一層（i 值為多少）、以及屬於哪個系列（X 或是 Y），假設現在要求第 K 個字元。因此我們就依序一層一層拆分下去求解。
例如當 N = 7 而我們要求第 8 個字元（索引值從 0 開始）時：
可以看到 N 屬於 Y3 ，因為 7 除以 2 得商數為 3（i 值）、 餘數為 1（即 Y ， 0 則代表 X）。
而 Y3 = Y2X2Y2 ，而 Y2 之長度為 8 個字元並沒有涵蓋到第 8 個字元（0 ～ 8 有九個字元），因此我們可以看到第 8 個字元應位於 X2 ，且為 X2 的第 8 - 8 = 0 個字元。
接著看到 X2 = X1Y1 ， X1 即涵蓋了第 0 個字元，所以直接降階成 X1 。
最後便降階成為 X0 ，即 "0" 。因此所求為「0」。
類似地，若要求 N = 7 的第 9 個字元之過程會是以下：
Y3 的第 9 個字元 → X2 的第 1 個字元 →
X1 的第 1 個字元 → Y0
因此為「1」。
而各個 X 、 Y 的長度就只是一般的費氏數列（不過 X0 、 Y0 對應的項次為 1 、 1，而不是 0 、 1 （因為是「長度」）），求值參見這題。
因此推廣到第 N 項的第 L ～ R 個字元，就將每個要求的字元按照以上流程去跑即可得到所求字元區段（N > 47 時，記得將 N 變為 46 + (N % 2)）。
不過因為 UVa 原題 N 、 L 、 R 之值有些有超出給定的範圍，因此對於有整數型態之程式語言，最好使用可以容納 2 ^ 31 以上之值的型態（例如像 C++ 的 unsigned int 等等）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
