Project Euler 377
Project Euler 377
题目
Sum of digits - experience \(\#13\)
There are \(16\) positive integers that do not have a zero in their digits and that have a digital sum equal to \(5\), namely:
\(5, 14, 23, 32, 41, 113, 122, 131, 212, 221, 311, 1112, 1121, 1211, 2111\) and \(11111\).
Their sum is \(17891\).
Let \(f(n)\) be the sum of all positive integers that do not have a zero in their digits and have a digital sum equal to \(n\).
Find \(\displaystyle \sum_{i=1}^{17} f(13^i)\).
Give the last \(9\) digits as your answer.
解决方案
注意这里需要求的是所有数之和。我们可以每次将一个数位拼接在一个数的后面,从而形成一个新的数。
令状态\(c(i)(i\ge 0)\)表示没有数位\(0\)且数位和为\(i\)的数的个数,那么不难写出如下状态转移方程:
\[ c(i)= \left \{\begin{aligned} &1 & & \text{if}\quad i=0 \\ &\sum_{d=1}^{\min(9,i)} c(i-d) & & \text{else} \end{aligned}\right. \]
将状态\(c(i-d)\)中的每一个数后面都添加一个数位\(d\),那么就成为了\(c(i)\)中的数。
得到\(c(i)\)后,令状态\(s(i)(i\ge 0)\)表示没有数位\(0\)且数位和为\(i\)的数之和,那么不难写出如下状态转移方程:
\[ s(i)= \left \{\begin{aligned} &0 & & \text{if}\quad i=0 \\ &\sum_{d=1}^{\min(9,i)} 10s(i-d)+d\cdot c(i-d) & & \text{else} \end{aligned}\right. \]
拼接一个新的数位\(d\)后,状态\(s(i-d)\)中的所有数都需要左移一位,都乘\(10\)。这些数一共有\(c(i-d)\)个,故综合还需要添加\(d\cdot c(i-d)\)。
最终,\(s(N)\)可以以\(O(N)\)的时间复杂度计算出来。不过,对于题目要求的时间复杂度仍然不高,需要使用矩阵快速幂进行优化。
无论是\(c\)还是\(s\),后面都有\(9\)项,因此这个矩阵的大小为\(18\)。这是一个比较大的矩阵,因此系数矩阵在此不展示,详见代码。
代码
1 | P = 13 |