假设n有k位,$137n$超过k位的部分为i,$137n$与n后k位之差为s,将这样的数的总数记作$f(k,i,s)$。
在n的最高位前添加一个数字d,得到新的数字n',那么n'有$k+1$位,$137n'$的第$k+1$位是$(i+137d) \bmod 10$,其超过$k+1$位的部分为$\lfloor(i+137d)/10\rfloor$,$137n'$与n'后$k+1$位之差为$s-d+((i+137d) \bmod 10)$。
$k=0$时的初值为$f(0,0,0)=1$,其他全为0,递推即得结果$20444710234716473$。
B=162
f=[[[0]*(2*B+1) for i in range(137)] for i in range(19)]
f[0][0][B] = 1
for k in range(18):
for i in range(137):
for s in range(2*B+1):
if f[k][i][s]!=0:
for d in range(10):
f[k+1][(i+137*d)//10][s-d+((i+137*d)%10)]+=f[k][i][s]
print sum(f[18][i][B-sum(int(c) for c in str(i))] for i in range(137))
|