令$f(n,a,b)$为$n$位数中满足要求且最后两位数字分别是a和b的数的总数，则显然有
$$f(n,a,b)=\sum_{k=0}^{9-a-b}f(n-1,k,a).$$
生成$n=3$时的初值后递推计算可得结果$378158756814587$。
f=[[[0 for b in range(10)] for a in range(10)] for n in range(21)]
for m in range(100,1000):
c,a,b=m/100,(m/10)%10,m%10
if a+b+c<=9:
f[3][a][b]+=1
for n in range(4,21):
for a in range(10):
for b in range(10):
f[n][a][b]=sum(f[n-1][k][a] for k in range(10-a-b))
print sum(f[20][a][b] for a in range(10) for b in range(10))
|
