定义函数$f:\mathbb N\to\mathbb N$如下： \begin{align*} f(1)&=1 \\ f(3)&=3 \\ f(2n)&=f(n) \\ f(4n+1)&=2f(2n+1)−f(n) \\ f(4n+3)&=3f(2n+1)−2f(n) \\ \end{align*} 令$S(n)=\sum_{i=1}^nf(n)$，可以验证$S(8)=22, S(100)=3604$。

求$S(337)$的最后9位数字。

本题难度:

解答

$f(n)$是OEIS A030101，即将n的二进制表示逆转后所得的数。$f(n)$是OEIS A239447，根据页面上的递推公式很容易得结果$808981553$。

注：因使用cache装饰器作记忆化搜索，以下代码为Python 3。

from functools import *

@cache
def S(n):
    if n<=2:
        return n
    q,r=divmod(n,4)
    if r==0:
        res=6*S(2*q)-5*S(q)-3*S(q-1)-1
    elif r==1:
        res=2*S(2*q+1)+4*S(2*q)-6*S(q)-2*S(q-1)-1
    elif r==2:
        res=3*S(2*q+1)+3*S(2*q)-6*S(q)-2*S(q-1)-1
    else:
        res=6*S(q*2+1)-8*S(q)-1
    return res%(10**9)

print(S(pow(3,37)))