定义序列$a(n)$为n的二进制表示中11出现的次数。例如$a(5)=a(101_2)=0, a(6)=a(110_2)=1, a(7)=a(111_2)=2$。

Rudin-Shapiro序列即$b(n)= (-1)^{a(n)}$，记其部分和为$s(n)=\sum_{i=1}^nb(n)$。

这些序列的前几项分别是（n从0开始） \begin{align*} a(n): & 0, 0, 0, 1, 0, 0, 1, 2 \\ b(n): & 1, 1, 1, -1, 1, 1, -1, 1 \\ s(n): & 1, 2, 3, 2, 3, 4, 3, 4 \end{align*} 序列$s(n)$中每个正整数k恰好出现k次，这是其重要特性。

定义$g(t,c)$为t在$s(n)$中第c次出现时的下标，例如：$g(3,3)=6, g(4,2)=7, g(54321,12345)=1220847710$。

令$F(n)$为以$F(0)=F(1)=1$初值的斐波那契数列，并令$GF(t)=g(F(t),F(t-1))$。

求$\sum_{t=2}^{45}GF(t)$。

本题难度:

解答

不难看出$b(2n)=b(n)$以及$b(2n+1)=(-1)^nb(n)$，从而 $$b(4n)=b(4n+1)=b(n), \quad b(4n+2)=(-1)^nb(n), \quad b(4n+3)=(-1)^{n+1}b(n).$$ 由此可得关于s的递推式： $$s(4n)=2s(n)-b(4n), \quad s(4n+1)=s(4n+3)=2s(n), \quad s(4n+2)=2s(n)+(-1)^nb(n).$$ 递归计算即可得结果$3354706415856332783$。

def g(t,c):
  if t==1:
      return 0
  h=1<<(len(format(t,"b"))-1)
  d=t-h
  if d==0:
      return t*t//4+g(t//2,c) if c<=t//2 else t*t//2+g(t,c-t//2)
  elif c>h:
      return h*h+g(2*h-d,c-h)
  elif c>h-d:
      return h*h+g(d,c+d-h)
  elif c<=d:
      return h*h//2+g(d,c)
  else:
      return h*h//2+g(2*h-t,c)

F=[1,1]
for i in range(2,46):
  F.append(F[-2]+F[-1])

print sum(g(F[t],F[t-1]) for t in range(2,46))