有界序列

设有长度为n的递增序列$x_1, x_2,\ldots, x_n$满足$x_1=2$以及$x_i^j<(x_j +1)^i$对任意$1\le i,j\le n$都成立。

$n=2$时这样的序列只有5个：$\{2,4\}, \{2,5\}, \{2,6\}, \{2,7\}, \{2,8\}$。

$n=5$时这样的序列共有293个，这是其中三个例子：$\{2,5,11,25,55\}, \{2,6,14,36,88\}, \{2,8,22,64,181\}$。

设长度为n时这样的序列共有$t(n)$个，可以验证$t(10)=86195$以及$t(20)=5227991891$。

求$t(10^{10})\bmod 10^9$。

本题难度:

解答

本题没有太好的方法，经过简单尝试即可归纳出 $$\sum_{k=1}^nt(\lfloor\frac{n}{k}\rfloor)=\frac{3^{n+1}-1}{2}-2^{n+1}+1,$$ 即 $$t(n)=\frac{3^{n+1}-1}{2}-2^{n+1}+1-\sum_{k=2}^nt(\lfloor\frac{n}{k}\rfloor).$$ 直接汇总计算即可得结果$268457129$。

import math
def f(n):
    m=int(math.sqrt(n))
    return [i for i in range(1,m+(m*m < n))]+[n/i for i in range(m,0,-1)]

a={}
tick=2000

for i,j in enumerate(f(10**10)):
    c=f(j)
    a[j]=(pow(3,j+1,10**10)/2-pow(2,j+1,10**10)+1-sum(((c[-u-1]-c[-u-2])*a[c[u]])%(10**9) for u in range(len(c)-1)))%(10**9)
    if i%tick==0:print i/tick,"percent completed"
    
print a[10**10]%(10**9)