斐波那契数列似乎有一个规律：

A
B
AB 1 + 1 (A count + B count)
BAB 1 + 2
ABBAB 2 + 3
BABABBAB 3 + 5
ABBABBABABBAB 5 + 8
      ^ k = 7
     BABABBAB 3 + 5
      ^ k = 2 (result = 3)
     BAB 1 + 2
      ^ k = 2 (result = 4)
     AB 1 + 1
     ^ k = 1 = A (result = 4)

设g(l, r, k)表示Fib[n] = l + r的前k个位置中B s的计数，则：

g(l, r, k):
  if (1, 1) == (l, r):
    return 1 if k == 2 else 0
  if (1, 2) == (l, r):
    return 1 if k < 3 else 2
  ll, rl = getFibSummands(l)
  lr, rr = getFibSummands(r)
  if k > l:
    return rl + g(lr, rr, k - l)
  return g(ll, rl, k)

上面的答案可能误解了串联的起始顺序，它可能应该是BA，在这种情况下，我们需要颠倒l, r。
一个二个一个一个

为清楚起见，将Fib(n)定义为斐波那契数列，其中Fib(0) = Fib(1) = 1和Fib(n+2) = Fib(n+1) + Fib(n)。
注意，F[n]有Fib(n)个字符，其中Fib(n-1)是B s。
令C(n, k)为F[n]的前k个字符中的B的数目。
基本情况是显而易见的

C(0, k) = 0
C(n, k) = 0 if k<=0
C(1, 1) = 1
C(2, k) = 1

一般而言：

C(n, k) = C(n-1, k)                         if k <= Fib(n-1)
        = Fib(n-2) + C(n-1, k - Fib(n-1))   otherwise

这是观察到F[n] = F[n-1] + F[n-2]和k位于第一部分或第二部分中，第一部分具有Fib(n-1)字符，其中Fib(n-2)是B的字符。
如果你预先计算了从0到n的斐波那契数列，那么你可以用O（n）的算术运算来计算C(n, k)。
你标记了java，但这里有一个包含测试用例的python解决方案：

def C(n, k):
    if n == 0: return 0
    total = 0
    fib = [1, 1]
    while len(fib) <= n and fib[-1] <= k:
        fib.append(fib[-1] + fib[-2])
    n = min(n, len(fib) - 1)
    while True:
        if n <= 2:
            return total + 1
        elif k <= fib[n-1]:
            n -= 1
        else:
            total += fib[n-2]
            k -= fib[n-1]
            n -= 1

tcs = [
    ([0, 1], 0),
    ([1, 1], 1),
    ([3, 2], 1),
    ([7, 7], 4)
]

for (n, k), want in tcs:
    got = C(n, k)
    if got != want:
        print('C(%d, %d) = %d, want %d' % (n, k, got, want))

这包括减少n的优化，使得最初k > Fib(n-1)。这使得代码的算术运算为O（min(n, log(k))）。