Project Euler 442

发表于 分类于 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 3 分钟

Project Euler 442

题目

Eleven-free integers

An integer is called eleven-free if its decimal expansion does not contain any substring representing a power of \(11\) except \(1\).

For example, \(2404\) and \(13431\) are eleven-free, while \(911\) and \(4121331\) are not.

Let \(E(n)\) be the \(n\text{th}\) positive eleven-free integer. For example, \(E(3) = 3\), \(E(200) = 213\) and \(E(500000) = 531563\).

Find \(E(10^{18})\).

解决方案

令\(N=10^{18}\)。定义计数函数\(F(N)\)表示不超过\(N\)的eleven-free数。则 \(E(n)\) 是满足\(F(E(n))\ge n\)的最小正整数，即\(E(n)=\min\{N\in\mathbb Z_{\ge1}\mid F(N)\ge n\}.\)

注意到 \(F(N)\) 随 \(N\) 单调不减，因此一旦能够高效计算 \(F(N)\)，就可以通过二分查找求出 \(E(N)\)。

令十进制数字集为 \(\Sigma=\{0,1,2,\dots,9\}\)。观察到：任意 \(11^k(k\ge1)\) 的十进制表示都包含字符 1，因此 若一个正整数的十进制表示中完全不出现 1，它必然 eleven-free。

考虑 \(d\) 位正整数（最高位非 \(0\)）且不含 1 的个数：首位可取 \(\{2,3,\dots,9\}\) 共 \(8\) 种；后 \(d-1\) 位可取 \(\Sigma\setminus\{1\}\) 共 \(9\) 种。

因此\(d\)位不含\(1\)的数的个数为\(8\cdot 9^{d-1}.\)对 \(1\le k\le d\) 求和得到不含 1 且位数不超过 \(d\) 的正整数个数：\(\displaystyle{\sum_{k=1}^{d}8\cdot 9^{k-1}=8\cdot\frac{9^d-1}{9-1}=9^d-1.}\)

因此为找到最小的\(d\)使得\(9^d-1\ge N\)，那么\(d\)至少为\(d=\left\lceil\dfrac{\log(N+1)}{\log9}\right\rceil\)。这里我们得到了\(d=19\)。也就是说在所有不超过 \(d\) 位的正整数中，已经至少存在 \(N\) 个 eleven-free 数。于是必有\(E(N)\ge 10^{d}.\)

从而我们只需考虑长度 \(\le d\) 的 forbidden 子串，也即只需要枚举满足\(|\mathrm{str}(11^k)|\le 19\)的那些 \(k\)。其中\(\mathrm{str}\)表示将数字解释为十进制字符串。

令 forbidden 集合为\(\mathcal P=\{\mathrm{str}(11^k)\mid k\ge1,|\mathrm{str}(11^k)|\le d\}.\)我们先约定：\(p\sqsubseteq w\) 表示\(p\) 是 \(w\)的子串。则在 \(\Sigma\) 上考虑语言\(\mathcal L=\{w\in\Sigma^*\mid \forall p\in\mathcal P,p\not\sqsubseteq w\}.\)

显然，eleven-free 的判定就是判断一个数字串是否属于 \(\mathcal L\)（并且我们允许出现 1，只是不允许出现完整的 \(11^k\) 子串）。

为了在线检测子串出现与否，我们可以构造AC自动机来完成，把 \(\mathcal P\) 中所有字符串插入并构建，得到确定性自动机 \(\mathcal A\)，其状态集合 \(S\)，字母表为 \(\Sigma\)，转移函数为\(\delta:S\times\Sigma\to S.\)

令 \(B\subseteq S\) 为“坏状态集合”，即所有对应“至少匹配到某个完整 forbidden 模式”的状态，再加上它们在 fail 链上的传播闭包。形式上可理解为：若存在 \(p\in\mathcal P\) 为当前读取串的某个后缀，则该状态属于 \(B\)。

于是对任意数字串 \(w\)，从初态 \(s_0\) 逐字符应用 \(\delta\)，若过程中到达某个 \(b\in B\)，则 \(w\notin\mathcal L\)；否则 \(w\in\mathcal L\)。由于 \(|\mathcal P|\) 很小（长度 \(\le d\) 的 \(11^k\) 数量级是\(O(d)\)），完全可行。

令 \(N\) 的十进制表示为\(N=\overline{D_0D_1\dots D_{L-1}}, D_i\in\Sigma,L\)是位数。我们要计算 \([0,N]\) 中属于 \(\mathcal L\) 的数字串数量，再减去 \(0\)。

用数位 DP，\(i\)表示当前位置（\(0\le i\le L\)），\(s\in S\)表示当前到达的 AC 自动机状态，\(a\in\{0,1\}\)表示是否出现过首个非零位，\(t\in\{0,1\}\)：是否仍受上界约束，定义\(f(i,s,a,t)\)表示补全后缀\(D_i\dots D_{L-1}\)的方法数，使整体仍 eleven-free。

边界条件：\(f(L,\cdot,\cdot,\cdot)=1,\)表示已经构造完成一个合法数（此时并不区分是否为 \(0\)，稍后统一减去）。

若 \(t=1\)，本位可选数字为 \(d\in[0,D_i]\)；若 \(t=0\)，则 \(d\in[0,9]\)。记上界为\(U_i=\begin{cases}D_i,&t=1\\9,&t=0.\end{cases}\)

若 \(a=0\) 且 \(d=0\)：仍未开始，自动机保持在初态 \(s_0\)；否则：视为把数字 \(d\) 喂给自动机，从状态 \(s\) 转移到 \(\delta(s,d)\)（若此前未开始，则等价于从 \(s_0\) 读入 \(d\)）。并且如果到达坏状态 \(B\)，则此分支无效。

因此

\[ f(i,s,a,t) =\sum_{d=0}^{U_i} \mathbf 1\bigl(\delta(s,d)\not\in B)\cdot f(i+1,s',a',t'), \]

其中\(t' = 1\) 当且仅当 \(t=1\) 且 \(d=U_i\)，\(a' = a\lor(d\ne 0)\)，\(s'\) 为更新后的自动机状态（未开始时保持 \(s_0\)，否则 \(s'=\delta(s,d)\)）。

最终得到包含\(0\)的eleven-free数的个数为\(f(0,s_0,0,1)\)。而题目所需的是正整数，所以\(F(N)=f(0,s_0,0,1)-1.\)

我们要求最小 \(x\) 使得 \(F(x)\ge 10^{N}\)，由于 \(F\) 单调不减，可以在区间 \([0,10^{d})\) 上二分即可。

代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
from functools import lru_cache
from collections import deque
from math import log10, ceil

N = 10 ** 18
def build_automaton(max_len: int):
    patterns = []
    k = 1
    while True:
        s = str(11 ** k)
        if len(s) > max_len:
            break
        patterns.append(list(map(int,s)))
        k += 1

    trans = [[-1] * 10]
    link = [0]
    bad = [False]

    for pat in patterns:
        v = 0
        for d in pat:
            if trans[v][d] == -1:
                trans[v][d] = len(trans)
                trans.append([-1] * 10)
                link.append(0)
                bad.append(False)
            v = trans[v][d]
        bad[v] = True

    q = deque()
    for d in range(10):
        if trans[0][d] != -1:
            v = trans[0][d]
            link[v] = 0
            q.append(v)
        else:
            trans[0][d] = 0

    while q:
        v = q.popleft()
        bad[v] |= bad[link[v]]
        for d in range(10):
            u = trans[v][d]
            if u != -1:
                link[u] = trans[link[v]][d]
                q.append(u)
            else:
                trans[v][d] = trans[link[v]][d]

    return trans, bad


def count_eleven_free_upto(n: int, trans, bad) -> int:
    digits = list(map(int, str(n)))
    L = len(digits)

    @lru_cache(maxsize=None)
    def dp(pos: int, state: int, started: int, tight: int) -> int:
        if pos == L:
            return 1
        lim = digits[pos] if tight else 9
        res = 0
        for d in range(lim + 1):
            ntight = 1 if (tight and d == lim) else 0
            if started == 0 and d == 0:
                res += dp(pos + 1, 0, 0, ntight)
            else:
                ns = trans[state][d] if started else trans[0][d]
                if bad[ns]:
                    continue
                res += dp(pos + 1, ns, 1, ntight)
        return res

    return dp(0, 0, 0, 1) - 1


def nth_eleven_free(k: int) -> int:
    max_digits = ceil(log10(k + 1) / log10(9))
    trans, bad = build_automaton(max_digits)

    l = 0
    r = 10 ** max_digits - 1

    while l < r:
        mid = (l + r) // 2
        if count_eleven_free_upto(mid, trans, bad) >= k:
            r = mid
        else:
            l = mid + 1
    return r


if __name__ == "__main__":
    print(nth_eleven_free(N))