令$c(i,j)$为i位数中各数字的平方和为j的数的总数，令$s(i,j)$为这些数的和。i不超过20，因此j不超过$9^2\times 20=1620$。
显然
$$c(1,j)=\begin{cases}1 & j=1,4,9,16,25,36,49,64,81 \\ 0 & \text{else}\end{cases}$$
对$i>1$，考虑将数字k添加到一个i-1位数的末尾，则有
$$c(i,j)=\sum_kc(i-1,j-k^2),$$
其中k从0开始且$j-k^2$需为正数。
类似地，
$$s(1,j)=\begin{cases}j & j=1,4,9,16,25,36,49,64,81 \\ 0 & \text{else}\end{cases}$$
对$i>1$，同样考虑将数字k添加到一个i-1位数的末尾，则有
$$s(i,j)=\sum_k10\times s(i-1,j-k^2)+k\times c(i-1,j-k^2),$$
其中k从0开始且$j-k^2$需为正数。
最后，递推即可得结果$142989277$。
c=[[0 for j in range(1621)] for i in range(0,21)]
for j in range(1,10):
c[1][j*j]=1
for i in range(2,21):
for j in range(1,81*i+1):
c[i][j]=sum(c[i-1][j-k*k] for k in range(10) if j>k*k)
s=[[0 for j in range(1621)] for i in range(0,21)]
for j in range(1,10):
s[1][j*j]=j
for i in range(2,21):
for j in range(1,81*i+1):
s[i][j]=sum(10*s[i-1][j-k*k]+k*c[i-1][j-k*k] for k in range(10) if j>k*k)
print sum(s[i][j*j] for i in range(1,21) for j in range(1,41))%(10**9)
|
