Project Euler 776
题目
Digit Sum Division
For a positive integer , is defined to be the sum of the
digits of . For example, .
Let .
You are given , and .
Find .
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.
解决方案
不难发现,可以将 进行改写:
改写后,相当于将 以内的所有数按照数位和分类好,再将它们求和即可,考虑使用动态规划的方法进行。
令 。考虑将 写成一个长度为 的十进制字符串 。
由于 很小,因此总数位和不会很大。
令中间 状态 分别表示如下含义:有多少个 位有前导 0 的数,其数位和为 ,并等于 由字符串 表示的数。令状态 表示 中的所有数之和。
不难发现,如果 ,那么 , 的值则为 这一个字符串的十进制数;否则 。
状态 和 的意义在于规定了答案严格在界限上的情况。而接下来定义的状态 则是严格不在界限上的情况。
令状态 表示有多少个 位有前导 0 的数,其数位和为 ,并严格小于 由字符串 表示的数。令状态 表示 中的所有数之和。
那么可以先写出 的状态转移方程:
方程最后一行的第一个求和项说明,如果之前的状态已经是严格小于 的数,那么接下来无论在后面拼接哪一个数位,都是严格小于的;对于第二个求和项而言,如果之前取的值都是严格等于的,那么接下来最多只能取到 。
那么基于 的思想,同样不难写出 的状态转移方程:
计算完成后,那么就可以计算 :
代码
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)