Project Euler 377

发表于 更新于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

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
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
30
31
32
33
P = 13
N = 17
mod = 10 ** 9


def mul(a: list, b: list):
    return [[sum(a[i][k] * b[k][j] for k in range(len(b))) % mod for j in range(len(b[0]))] for i in range(len(a))]


def f(n):
    M = 18
    # s[i-9],s[i-8],s[i-7],...,s[i-1],c[i-9],c[i-8],c[i-7],...,c[i-1]
    a = [[0, 1, 13, 147, 1625, 17891, 196833, 2165227, 23817625, 1, 1, 2, 4, 8, 16, 32, 64, 128]]
    b = [[0 for _ in range(M)] for _ in range(M)]
    for i in range(9):
        b[i][8] = 10
        b[i + 9][8] = 9 - i

        b[i + 9][8 + 9] = 1
    for i in range(8):
        b[i + 1][i] = b[i + 1 + 9][i + 9] = 1
    while n:
        if n & 1:
            a = mul(a, b)
        b = mul(b, b)
        n >>= 1
    ans = a[0][0]
    return ans


ans = sum(f(P ** i) for i in range(1, N + 1)) % mod
print(ans)