令$g(n)$为不含零且各位数字之和等于n的数的个数，则有初值$g(1)=1$以及
$$g(n)=\sum_{d=1}^{\min(9,n)}g(n-d).$$
也就是在一个数的最后添加一位d，其数字和增加d。由此可得
$$f(n)=\sum_{d=1}^{\min(9,n)}10f(n-d)+dg(n-d).$$
即添加一位数字d后，原来的数左移一位，因此乘10，共添加了g(n-d)个d。
用矩阵快速幂递推计算即得结果$732385277$。
mod=10**9
mul=lambda x,y:[[sum(x[i][k]*y[k][j] for k in range(len(y)))%mod for j in range(len(y[0]))] for i in range(len(x))]
def f(n):
a=[[0, 1, 13, 147, 1625, 17891, 196833, 2165227, 23817625, 1, 1, 2, 4, 8, 16, 32, 64, 128]]
b=[[0 for j in range(18)] for i in range(18)]
for i in range(9):
b[i][8] = 10
b[i+9][8]=9-i
b[i+9][17]=1
for i in range(8):
b[i+1][i]=b[i+1+9][i+9]=1
while n:
if n & 1:
a=mul(a,b)
b=mul(b,b)
n>>=1
return a[0][0]
print sum(f(13**i) for i in range(1,18))%mod
|
