记$c(i,j)$为由0到9的数字组成的、长度为i，且各位之和为j的有序数字串的数量。
记$s(i,j)$为由0到9的数字组成的、长度为i，且各位之和为j的有序数字串之和（视作带前导0的十进制数）。
则对每个固定的i，j都可以从0取到9i，且有初值
$$c(1,j)=1, \quad s(1,j)=j.$$
考虑在$i-1$位数后添加一位数k的情况，又得
$$c(i,j)=\sum_{k=0}^{\min(j,9)}c(i-1,j-k), \quad s(i,j)=\sum_{k=0}^{\min(j,9)}10\cdot s(i-1,j-k)+k\cdot c(i-1,j-k).$$
再记$c^*(i,j)$为由0到9的数字组成的、长度为i，不以0开头，且各位之和为j的有序数字串的数量。
以及$s^*(i,j)$为由0到9的数字组成的、长度为i，不以0开头，且各位之和为j的有序数字串之和。
则有
$$c^*(i,j)=c(i,j)-c(i-1,j), \quad s^*(i,j)=s(i,j)-s(i-1,j).$$
记$T^*(n)$为长度恰好为n的平衡数之和。
若$n=2m$是偶数，则每一个长度为m、不含前导0、和为j的数串都可以作为前m位，它可以分别拼接$c(m,j)$个长度为m、含前导0、和为j的数串得到平衡数。
同理，每一个长度为m、含前导0、和为j的数串都可以作为后m位，在它之前可以分别拼接$c^*(m,j)$个长度为m、不含前导0、和为j的数串得到平衡数。
因此
$$T^*(n)=\sum_{j=1}^{9m}10^m\cdot s^*(m,j)\cdot c(m,j)+s(m,j)\cdot c^*(m,j),$$
类似地，若$n=2m+1$是奇数，则组合前m位、后m位和中间一位得
$$T^*(n)=\sum_{j=1}^{9m}10^{m+2}\cdot s^*(m,j)\cdot c(m,j)+10\cdot s(m,j)\cdot c^*(m,j)+45\cdot10^m\cdot c^*(m,j)\cdot c(m,j).$$
递推计算即得结果$6273134$。
c=[[0]*208 for i in range(24)]
s=[[0]*208 for i in range(24)]
c2=[[0]*208 for i in range(24)]
s2=[[0]*208 for i in range(24)]
for j in range(10):
c[1][j]=c2[1][j]=1
s[1][j]=s2[1][j]=j
for i in range(2,24):
for j in range(9*i+1):
c[i][j]=sum(c[i-1][j-k] for k in range(min(10,j+1)))
s[i][j]=sum(10*s[i-1][j-k]+k*c[i-1][j-k] for k in range(min(10,j+1)))
c2[i][j]=c[i][j]-c[i-1][j]
s2[i][j]=s[i][j]-s[i-1][j]
z=3**15
r=45
for n in range(2,48):
m=n/2
x=pow(10,m,z)
if n%2==0:
r+=sum((x*s2[m][j]*c[m][j]+s[m][j]*c2[m][j])%z for j in range(1,9*m+1))%z
else:
r+=sum((100*x*s2[m][j]*c[m][j]+10*s[m][j]*c2[m][j]+45*x*c[m][j]*c2[m][j])%z for j in range(1,9*m+1))%z
print r%z
|
