。。好高欣。。今晚解决掉了一个 Daizhenyang 问题。。。>_< ）
Brief description:
求第 n 个 Fibnacci Word 的 [l, r] 位置的字符分别是多少。
( .. n, l, r <= 2^31 - 1 .. .)
Analysis:
。。前几天翻箱的时候读到了这个东西，貌似是用来给一些字符串算法构造专杀数据用的 >_<。 （就如同 Fibnacci 数对于欧几里得算法时一样.. ） 所以昨天夜里 DIY 有人问这个问题的时候，我也特别留意了一下... 还是从递归和分型的角度着手，Key Observation is ... Fibnacci 数列本身会呈指数增长，所以过大的 n 对于这个问题没有意义。 [cpp] const int N = 48; LL F[N]; void gao(int n, LL l, LL r){ if (r < l) return; if (n == 0) printf("0"); else if (n == 1) printf("1"); else { if (l < F[n-2]){ gao(n-2, l, min(r, F[n-2] - 1)); gao(n-1, 0, r - F[n-2]); } else { gao(n-1, l - F[n-2], r - F[n-2]); } } } int n, l, r; int main(){ F[0] = 1, F[1] = 1; FOR(i, 2, N) F[i] = F[i-1] + F[i-2]; Rush{ RD(n, l, r); if (n >= N) n = N - (n & 1); gao(n, l, r); puts(""); } } [/cpp] (.. 貌似数据稍微有些爆 int .. )
External link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242&page=show_problem&problem=3192
POJ 1322. Chocolate
