Project Euler 776

Project Euler 776

题目

Digit Sum Division

For a positive integer n, d(n) is defined to be the sum of the digits of n. For example, d(12345)=15.

Let F(N)=n=1Nnd(n).

You are given F(10)=19, F(123)1.187764610390e3 and F(12345)4.855801996238e6.

Find F(1234567890123456789). Write your answer in scientific notation rounded to twelve significant digits after the decimal point. Use a lowercase e to separate the mantissa and the exponent.

解决方案

不难发现,可以将 F 进行改写:

F(N)=n=1Nnd(n)=k=1+1k(nN,d(n)=kn)

改写后,相当于将 1N 以内的所有数按照数位和分类好,再将它们求和即可,考虑使用动态规划的方法进行。

N=1234567890123456789。考虑将 N 写成一个长度为 l 的十进制字符串 N=d1d2d3dl

由于 N 很小,因此总数位和不会很大。

中间状态 c1(i,j)(1il,0j9i) 分别表示如下含义:有多少个 i有前导 0 的数,其数位和为 j,并等于由字符串 d1d2di 表示的数。令状态 s1(i,j) 表示 c1(i,j) 中的所有数之和。

不难发现,如果 j=k=1idk,那么 c1(i,j)=1s1(i,j) 的值则为 d1d2di 这一个字符串的十进制数;否则 c1(i,j)=s1(i,j)=0

状态 c1 s1 的意义在于规定了答案严格在界限上的情况。而接下来定义的状态 c0,s0 则是严格不在界限上的情况。

令状态 c0(i,j) 表示有多少个 i有前导 0 的数,其数位和为 j,并严格小于由字符串 d1d2di 表示的数。令状态 s0(i,j) 表示 c0(i,j) 中的所有数之和。

那么可以先写出 c0 的状态转移方程:

c0(i,j)={1ifi=1j<d10else ifi=1k=0min(9,n)c0(i1,jk)+k=0min(9,n,di1)c1(i1,jk)else

方程最后一行的第一个求和项说明,如果之前的状态已经是严格小于 d1d2di1 的数,那么接下来无论在后面拼接哪一个数位,都是严格小于的;对于第二个求和项而言,如果之前取的值都是严格等于的,那么接下来最多只能取到 di1

那么基于 c0 的思想,同样不难写出 s0 的状态转移方程:

s0(i,j)={jifi=1j<d10else ifi=1k=0min(9,n)(10s0(i1,jk)+kc0(i1,jk))+k=0min(9,n,di1)(10s1(i1,jk)+kc1(i1,jk))else

计算完成后,那么就可以计算 F(N)

F(N)=k=19ls0(l,k)+s1(l,k)k

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
N = 1234567890123456789
d = list(map(int, list(str(N))))
l = len(d)
c = [[[0, 0] for _ in range((l + 1) * 9)] for _ in range(l)]
s = [[[0, 0] for _ in range((l + 1) * 9)] for _ in range(l)]
c[0][d[0]][1] = 1
s[0][d[0]][1] = d[0]
for j in range(d[0]):
c[0][j][0] = 1
s[0][j][0] = j
ds = d[0]
for i in range(1, l):
ds += d[i]
c[i][ds][1] = 1
s[i][ds][1] = s[i - 1][ds - d[i]][1] * 10 + d[i]
for j in range(l * 9):
for k in range(min(j, 9) + 1):
if k < d[i]:
c[i][j][0] += c[i - 1][j - k][1]
s[i][j][0] += s[i - 1][j - k][1] * 10 + c[i - 1][j - k][1] * k
c[i][j][0] += c[i - 1][j - k][0]
s[i][j][0] += s[i - 1][j - k][0] * 10 + c[i - 1][j - k][0] * k

ans = 0
for i in range(1, l * 9):
ans += sum(s[-1][i]) / i
ans = "{:.12e}".format(ans).replace("e+", "e").replace("e0", "e")
print(ans)