0290 电子签名
* * * *
拉格朗日计划
* * * *
电子签名

有多少个小于$10^18$的非负整数n,其各位数字和恰等于$137n$的各位数字和?

本题难度:



解答

假设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))