Project Euler 305

题目

Reflexive Position

Let’s call \(S\) the (infinite) string that is made by concatenating the consecutive positive integers (starting from \(1\)) written down in base \(10\).

Thus, \(S = 1234567891011121314151617181920212223242\dots\)

It’s easy to see that any number will show up an infinite number of times in \(S\).

Let’s call \(f(n)\) the starting position of the \(n^\text{th}\) occurrence of \(n\) in \(S\).

For example, \(f(1)=1, f(5)=81, f(12)=271\) and \(f(7780)=111111365\).

Find \(\sum f(3^k)\) for \(1\le k\le13\).

解决方案

令\(T(N)="123\cdots N"\)的拼接，也就是 \(S\) 的前缀。对给定正整数 \(n\)，记模式串\(P=\mathrm{str}(n),m=|P|.\)

因此题目定义 \(f(n)\) 为 \(P\) 在 \(S\) 中第 \(n\) 次出现的起始位置（从 1 开始）。

定义\(D(N)=|T(N)|\)，即写下 \(1,2,\dots,N\) 一共用了多少位字符。若 \(N\) 有 \(L\) 位，则

\[ D(N)=\sum_{d=1}^{L-1} 9\cdot 10^{d-1}\cdot d + (N-10^{L-1}+1)\cdot L=\dfrac{1+10^{L-1}(9L-10)}{9}+ (N-10^{L-1}+1)\cdot L. \]

因此整数 \(x\) 在 \(S\) 中的起始位置为\(\mathrm{pos}(x)=D(x-1)+1.\)其中\(\text{pos}(x)=1\)。

定义\(\mathrm{Occ}(N)\)表示模式\(P\)在\(T(N)\)中出现的总次数（允许重叠）。如果能快速算 \(\mathrm{Occ}(N)\)，就可以二分找最小 \(y\) 使得$ (y)n$。再从最后一段把第 \(n\) 次出现的精确起点定位出来。

从 \(T(y-1)\) 扩展到 \(T(y)\)，新增字符只来自 \(\mathrm{str}(y)\)。当 \(y\) 的位数 \(d\ge m\) 时，长度为 \(m\) 的匹配窗口：

• 要么完全落在 \(\mathrm{str}(y)\) 内部（内部出现），计入\(\mathrm{Occ}_{i}(N)\)；
• 要么跨越唯一边界 \(\mathrm{str}(y-1) || \mathrm{str}(y)\)（边界出现），计入\(\mathrm{Occ}_{b}(N)\)；

因为窗口长度是 \(m\le d\)，不可能同时跨过两条以上边界。对于更加困难的“跨三数或更多”的情况只会在右端数字位数 小于 模式长度时出现。这里 \(n=3^k\le 3^{13}=1594323\)，所以 \(m\le 7\)，我们只需把有限前缀\(y<10^{m-1}\)这部分用暴力预处理即可。这部分计入\(\mathrm{Occ}_{s}(N)\)。

于是\(\mathrm{Occ}(N)=\mathrm{Occ}_{s}(N)+\mathrm{Occ}_{i}(N)+\mathrm{Occ}_{b}(N).\)

现在计算\(\mathrm{Occ}_{i}(N)\)的值。

固定当前处理的位数档为 \(d\ge m\)。模式 \(P\) 可以放在偏移 \(i\)（从左起 0-index）处：\(0\le i\le d-m.\) 令后缀自由段长度为$ =d-i-m\(，因此自由后缀\)R.$

• 若 \(i=0\)，满足条件的最高位就从 \(P\) 开始，结构为\(x=P\cdot 10^{d-m}+R.\)共 \(10^{\ell}\) 个。
• 若 \(i>0\)：\(x\) 由三段拼起来：左前缀 \(L\)（\(i\) 位，首位非零）、中间固定段 \(P\)、右后缀 \(R\)（\(\ell\) 位，可含前导零）：\(x=L\cdot 10^{d-i}+P\cdot 10^{\ell}+R,\)其中\(L\in[10^{i-1},10^i-1], R\in[0,10^\ell-1].\)

因此对 \(d>m\)，总贡献为\(10^{d-m}+(d-m)\cdot 9\cdot 10^{d-m-1}.\)若 \(d=m\)，只有 \(x=n\) 贡献 1 次。

那么对于 \(d<\mathrm{len}(N)\)，所有\(d\)位数都要计算。对于\(d=\mathrm{len}(N)\)位数，只计算不超过\(N\)的那一部分。

现在讨论\(d=\mathrm{len}(N)\)的情况。

把 \(N\) 按照同样的切点拆开：\(N = H\cdot 10^{d-i}+T,\)

其中

• \(H=\left\lfloor \dfrac{N}{10^{d-i}}\right\rfloor\) 是 \(N\) 的前 \(i\) 位（当 \(i=0\) 时就是 \(H=0\)）；
• \(T=N\bmod 10^{d-i}\) 是剩下的尾部（长度 \(d-i\)）。

对于某个特定的 \(L\)，所有候选 \(x\) 的最高 \(i\) 位都等于 \(L\)。因此：

• 若 \(L < H\)，则整个块都满足 \(x\le N\)，贡献 整块 \(10^\ell\) 个；
• 若 \(L > H\)，则整个块都 \(>N\)，贡献 0；
• 只有当 \(L=H\) 时，才需要精细比较尾部：此时\(x \le N\iff P\cdot 10^\ell + R \le T\iff R \le T - P\cdot 10^\ell.\)于是这时 \(L=H\) 时的贡献为\(T-P\cdot 10^\ell+1.\)

因此有

\[\mathrm{Occ}_{i}(N)=\sum_{d=m}^{\text{len}(N)-1}10^{d-m}+(d-m)\cdot 9\cdot 10^{d-m-1}+\sum_{i=0}^{d-m} \max(0,\min(10^{d-i-m},N\bmod 10^{d-i}-P\cdot 10^{d-i-m}+1)).\]

现在计算\(\mathrm{Occ}_{b}(N)\)的值。

边界出现指 \(P\) 跨越 \((y-1)||y\)。令\(P=A||B, |A|=a\ge 1, |B|=b=m-a\ge 1.\)

边界出现条件是：

• \((y-1)\) 的后 \(a\) 位等于 \(A\)；
• \(y\) 的前 \(b\) 位等于 \(B\)；
• 且 \(B\) 不能以 \(0\) 开头（否则 \(y\) 的最高位会是 \(0\)，不可能是合法 \(d\) 位数）。

由于 \(y\) 的后 \(a\) 位 = \(((y-1)\) 的后 \(a\) 位 \(+1)\bmod 10^a\)。因此如果 \((y-1)\) 的后 \(a\) 位是 \(A\)，那么 \(y\) 的后 \(a\) 位必为\(S \equiv (A+1)\bmod 10^a, 0\le S<10^a.\)

于是边界条件等价于对 \(y\) 本身的约束：

• 前 \(b\) 位固定为 \(B\)；
• 后 \(a\) 位固定为 \(S\)。

注意，这一步没有遗漏“进位”问题：模 \(10^a\) 正是把跨过第 \(a\) 位之外的进位全部抹去，而“后 \(a\) 位”本来就只关心模 \(10^a\) 的结果。

固定当前处理的位数档为 \(d\ge m\)。设中间自由段长度为\(t=d-b-a=d-m.\)则 \(y\) 具有结构\(y = B\cdot 10^{d-b} + M\cdot 10^{a} + S, M\in[0,10^t-1].\)

因此在完整的 \(d\) 位范围内，每个合法切分 \((a,b)\) 都有恰好\(10^{d-m}\)个 \(y\)。

同样那么对于 \(d<\mathrm{len}(N)\)，所有\(d\)位数都要计算。对于\(d=\mathrm{len}(N)\)位数，只计算不超过\(N\)的那一部分。

现在讨论\(d=\mathrm{len}(N)\)的情况。把 \(N\) 按“前 \(b\) 位 / 其余”拆开：\(N = H\cdot 10^{d-b} + R\)

其中

• \(H=\left\lfloor \dfrac{N}{10^{d-b}}\right\rfloor\) 是 \(N\) 的前 \(b\) 位；
• \(R=N\bmod 10^{d-b}\) 是后面剩余的 \(d-b\) 位。

而候选 \(y\) 的结构是

\[ y = B\cdot 10^{d-b} + (M\cdot 10^a + S). \]

于是比较分三种情况：

1. 若 \(B<H\)：候选 \(y\) 的前 \(b\) 位更小，必然 \(y\le N\)，所以贡献整块\(10^{d-m}\).

2. 若 \(B>H\)：候选前缀更大，必然 \(y>N\)，贡献 \(0\)。

3. 若 \(B=H\)：需要比较尾部，要求\(M\cdot 10^a + S \le R.\)

   • 若 \(R<S\)，无解，贡献 \(0\)；
   • 否则\(M \le \left\lfloor \dfrac{R-S}{10^a}\right\rfloor\)，所以贡献为\(\min\left(10^{d-m},\left\lfloor \dfrac{R-S}{10^a}\right\rfloor +1\right).\)

因此，通过倍增和二分，我们可以找到最小的\(y\) 使得 \(\mathrm{Occ}(y)\ge n\)。

当找出\(y\)后，我们通过模拟计算出出现在\((y-1)||y\)的那一次位置，然后再逐步模拟计算出具体位置即可。

代码

# ----------------------------
# 1) digits count: |"123...N"|
# ----------------------------
# 预先准备 10 的幂：POW10[k] = 10^k
# 这里开到 10^39 足够覆盖本题中所有会出现的位数运算（N <= 1e18）
K = 13
pow10 = [1]
for _ in range(40):
    pow10.append(pow10[-1] * 10)
MAX_BRUTE = 10**6 - 1  # 999999：构建到 10^6 级别，长度约 5.9e6，内存可接受

# 预先一次性构建暴力前缀
S_BRUTE = "".join(str(x) for x in range(1,MAX_BRUTE))

def digit_count_upto(N: int) -> int:
    """
    D(N) = 串 "123...N" 的总长度（字符数）。

    例如：
      N=9   -> "123456789" 长度 9
      N=10  -> "12345678910" 长度 11

    计算方法：
      将 1..N 按位数分组：
        1 位数：1..9   共 9 个，每个贡献 1 位
        2 位数：10..99 共 90 个，每个贡献 2 位
        ...
      对于最后一组（位数为 d），只取到 N 为止。
    """
    if N <= 0:
        return 0
    s = 0          # 累计长度
    d = 1          # 当前位数
    start = 1      # 当前位数段的起点：1,10,100,...
    # 完整累加所有“满段”：[start, start*10 - 1]
    while start * 10 <= N:
        # 该段有 9*start 个数，每个 d 位
        s += 9 * start * d
        start *= 10
        d += 1
    # 最后一段：从 start 到 N，一共 (N - start + 1) 个数
    s += (N - start + 1) * d
    return s


# -----------------------------------------
# 2) brute prefix for the finite "small" part
#    (covers multi-number overlaps)
# -----------------------------------------
# 为了处理“跨越 >=3 个相邻整数”的匹配（多边界），我们在前面一小段用暴力。
# 典型的“跨多边界”发生在像 "89101112" 这种模式里，它可以跨越 8|9|10|11|12。
# 这类情况如果只靠“跨一个边界”的计数容易漏，需要额外处理。
#
# 本实现做法：把足够长的前缀 S_BRUTE = "123...MAX_BRUTE" 直接构建出来，
# 并且对所有 “右端整数 <= small_limit” 的情况直接用暴力 find 计数，避免复杂边界分类。



def count_in_prefix_string(pat: str, upto: int) -> int:
    """
    暴力统计 pat 在 '123...upto' 中出现次数（允许重叠）。

    实现方式：
      先通过 digit_count_upto(upto) 计算出 "123...upto" 的精确长度 L，
      再在 S_BRUTE 的前 L 个字符上做 find 循环。

    注意：
      这里 i = j+1，从而允许重叠出现（如 '11' 在 '111' 中出现两次）。
    """
    if upto <= 0:
        return 0
    L = digit_count_upto(upto)
    return S_BRUTE[:L].count(pat)


# -----------------------------------------
# 3) Fast counter for occurrences up to N
# -----------------------------------------
class PatternCounter:
    """
    针对固定模式串 pat = str(n)，提供 occ_end(N)：
      occ_end(N) = pat 在 "123...N" 中出现次数（允许重叠）

    整体策略：
      - 对于比较小的 N（<= small_limit），直接在暴力前缀中数（准确且简单）。
      - 对于大的 N，把计数拆成两部分：
          1) internal：pat 完全落在某个整数 y 的十进制表示内部（不跨边界）
          2) boundary：pat 跨越边界 (y-1)|y（跨 1 个边界）
        同时把所有 “右端整数 <= small_limit” 的部分统一用 base_count 预先暴力计算，
        这样能覆盖跨越 >=2 个边界的情况（这些情况只会发生在比较小的整数附近）。
    """

    def __init__(self, n: int):
        self.n = n
        self.pat_str = str(n)   # 模式串 P
        self.m = len(self.pat_str)  # 模式串长度 m
        self.pat_int = n        # 模式串作为整数，用于内部计数的比较

        # small_limit 的含义：
        #   当右端整数 y < 10^(m-1) 时，y 的位数 < m，
        #   pat 只能通过跨多个整数拼接才能出现（可能跨 >=2 边界），分类会变得麻烦。
        #   因此我们把 y <= 10^(m-1)-1 的这部分统一用暴力精确算完。
        self.small_limit = pow10[self.m - 1] - 1 if self.m > 1 else 0

        # base_count：模式串在 "123...small_limit" 中的出现次数（暴力）
        # 之后 occ_end(N) 若 N > small_limit，则结果 = base_count + 大数部分计数
        self.base_count = (
            count_in_prefix_string(self.pat_str, self.small_limit)
            if self.small_limit > 0 else 0
        )

        # valid_splits：用于跨一个边界 (y-1)|y 的计数
        #
        # 设模式串 P 长度 m，考虑切分：
        #     P = A | B
        # 其中 A 非空、B 非空。
        #
        # 若 P 跨越边界 (y-1)|y，且 y 为右端整数：
        #   - B 必须是 y 的前缀（所以 B 不能以 '0' 开头，否则 y 会出现前导零）
        #   - A 必须是 (y-1) 的后缀
        #
        # 关键变换（等价写法）：
        #   让 y 的前缀为 B，
        #   且 y 的后缀（长度 |A|）等于 (A + 1) mod 10^{|A|}
        # 这样通过“固定前缀 + 固定后缀”的计数，就能统计跨边界出现次数。
        #
        # 存储形式：(prefix_len=b, prefix_val=int(B), suffix_len=a, suffix_val=(int(A)+1) mod 10^a)
        self.valid_splits = []
        for a in range(1, self.m):
            A = self.pat_str[:a]
            B = self.pat_str[a:]
            # B 是 y 的前缀，必须保证 B 的首位不是 0（否则 y 作为十进制数会有前导零）
            if B[0] == '0':
                continue
            b = self.m - a
            prefix_val = int(B)
            suffix_len = a
            suffix_val = (int(A) + 1) % pow10[a]
            self.valid_splits.append((b, prefix_val, suffix_len, suffix_val))
        self.s_count = len(self.valid_splits)  # 可用切分的数量

    # -------- internal: full blocks --------
    def count_internal_full_block(self, d: int) -> int:
        """
        统计：所有 d 位数 y（范围 [10^{d-1}, 10^d-1]），模式串 P 完全落在 y 内部的出现总数。

        若 d < m：不可能
        若 d == m：每个 y 只有一个窗口，且 y==P 时贡献 1，所以总数为 1
        若 d > m：有两类窗口：
            - 从开头对齐（i=0）：形如 y = P * 10^{d-m} + suffix，共 10^{d-m} 个
            - 中间对齐（i>0）：需要枚举前缀长度 i (1..d-m)，每个 i 对应
                  前缀有 9*10^{i-1} 种（首位不能为 0）
                  后缀有 10^{d-i-m} 种
              总数为 sum_{i=1..d-m} 9*10^{i-1} * 10^{d-i-m}
                     = (d-m)*9*10^{d-m-1}
        所以总数：
          10^{d-m} + (d-m)*9*10^{d-m-1}
        """
        dm = d - self.m
        if dm == 0:
            return 1
        return pow10[dm] + dm * 9 * pow10[dm - 1]

    # -------- internal: <= limit for fixed length d and position i --------
    def count_internal_pos_leq(self, limit: int, d: int, i: int) -> int:
        """
        在所有 d 位数 y 且 y <= limit 的范围内，统计：
          模式串 P 作为 y 的子串，且子串起点在 y 的第 i 位（0-index）时的出现次数。

        记：
          y = (prefix of length i) + P + (suffix of length (d-i-m))

        特殊处理：
          i==0：prefix 为空，此时 y = P*10^{d-m} + suffix，suffix 取 0..10^{d-m}-1
          i>0：prefix 首位不能为 0（保证 y 是 d 位数），suffix 任意

        计数方法：
          通过把 limit 拆成 prefix_limit 与 rest，
          精确计算 prefix < prefix_limit 的全量贡献 + prefix == prefix_limit 的边界贡献。
        """
        m = self.m
        # limit 不足以达到 d 位数
        if limit < pow10[d - 1]:
            return 0

        # i == 0：y = P*10^{d-m} + suffix
        if i == 0:
            base = self.pat_int * pow10[d - m]
            if base > limit:
                return 0
            # suffix 的可取数量受 limit 限制
            return min(pow10[d - m], limit - base + 1)

        # i > 0：prefix(长度 i, 首位不为0) + P + suffix
        suffix_len = d - i - m
        suffix_pow = pow10[suffix_len]  # suffix 取值范围大小

        # prefix_limit：limit 的前 i 位；rest：剩余 (d-i) 位
        prefix_limit = limit // pow10[d - i]
        rest = limit % pow10[d - i]

        # 合法 prefix 范围：[10^{i-1}, 10^i-1]
        pre_min = pow10[i - 1]
        pre_max = pow10[i] - 1

        # prefix_limit 小于最小合法 prefix => 没有贡献
        if prefix_limit < pre_min:
            return 0
        # prefix_limit 大于最大合法 prefix => 全部 prefix 都可取
        if prefix_limit > pre_max:
            return (pre_max - pre_min + 1) * suffix_pow

        # prefix < prefix_limit：每个 prefix 都可以搭配任意 suffix
        count = (prefix_limit - pre_min) * suffix_pow

        # prefix == prefix_limit：需要 rest >= P*suffix_pow 才能放下 P
        need = self.pat_int * suffix_pow
        if rest >= need:
            count += min(suffix_pow, rest - need + 1)
        return count

    def count_internal_large(self, N: int) -> int:
        """
        统计 internal 部分（P 完全落在某个 y 内部）在 y <= N 的出现次数，
        仅对 y >= 10^{m-1} 的“长整数部分”计数（短整数部分由 base_count 暴力覆盖）。

        做法：
          - 对所有位数 d < D（D = len(N)），整段使用 count_internal_full_block(d)
          - 对位数 d = D，只统计 y <= N 的部分，需对每个起点 i 使用 count_internal_pos_leq(N,D,i)
        """
        if N < pow10[self.m - 1]:
            return 0
        D = len(str(N))
        total = 0

        # 完整位数段：d = m..D-1
        for d in range(self.m, D):
            total += self.count_internal_full_block(d)

        # 边界位数段：d = D，只能统计 <= N 的那部分
        for i in range(0, D - self.m + 1):
            total += self.count_internal_pos_leq(N, D, i)
        return total

    # -------- boundary: count y <= limit with fixed prefix/suffix --------
    def count_affix_leq(self, limit: int, d: int, prefix_len: int, prefix_val: int,
                        suffix_len: int, suffix_val: int) -> int:
        """
        统计：在所有 d 位数 y 且 y <= limit 的范围内，满足：
          y 的前 prefix_len 位 == prefix_val
          y 的后 suffix_len 位 == suffix_val
        的 y 的数量。

        对应跨边界匹配：
          y 的前缀固定为 B（prefix_len=b）
          y 的后缀固定为 (A+1) mod 10^a（suffix_len=a）

        设中间长度：
          mid_len = d - prefix_len - suffix_len
        那么 y 结构为：
          y = prefix_val * 10^{d-prefix_len} + mid * 10^{suffix_len} + suffix_val
          mid 的范围：[0, 10^{mid_len}-1]
        所以问题变成：求满足上述形式且 y <= limit 的 mid 的数量。
        """
        if limit < pow10[d - 1]:
            return 0
        mid_len = d - prefix_len - suffix_len
        if mid_len < 0:
            return 0

        # prefix_limit：limit 的前 prefix_len 位
        prefix_pow = pow10[d - prefix_len]
        prefix_limit = limit // prefix_pow
        rest = limit % prefix_pow  # limit 的后 d-prefix_len 位

        # prefix_val 与 prefix_limit 比较决定是否整段全取/全不取/边界取
        if prefix_val < prefix_limit:
            return pow10[mid_len]
        if prefix_val > prefix_limit:
            return 0

        # prefix 相等：需要 mid*10^{suffix_len} + suffix_val <= rest
        if rest < suffix_val:
            return 0
        max_mid = (rest - suffix_val) // pow10[suffix_len]
        if max_mid >= pow10[mid_len]:
            return pow10[mid_len]
        return max_mid + 1

    def count_boundary_full_block(self, d: int) -> int:
        """
        对所有 d 位数 y（整段）统计跨边界出现次数：

        对每一种合法切分 (A|B)，固定前缀 B 和固定后缀 (A+1 mod 10^a)，
        在所有 d 位数 y 中，满足“前缀+后缀”的 y 数量为 10^{d-m}（中间自由位数 d-m）。
        合法切分共有 s_count 种，因此整段总数：
          s_count * 10^{d-m}
        """
        return self.s_count * pow10[d - self.m]

    def count_boundary_large(self, N: int) -> int:
        """
        统计 boundary 部分（跨 (y-1)|y 的出现）在 y <= N 的出现次数，
        同样只对 y >= 10^{m-1} 的“长整数部分”计数（短整数部分由 base_count 暴力覆盖）。
        """
        if N < pow10[self.m - 1]:
            return 0
        D = len(str(N))
        total = 0

        # 完整位数段：d = m..D-1
        for d in range(self.m, D):
            total += self.count_boundary_full_block(d)

        # 位数段 d=D：对每个 split 用 count_affix_leq 处理 <=N 的边界
        for (b, prefix_val, a, suffix_val) in self.valid_splits:
            total += self.count_affix_leq(N, D, b, prefix_val, a, suffix_val)
        return total

    def occ(self, N: int) -> int:
        """
        Occ(N) = 模式串 P 在 "123...N" 中出现次数。

        若 N <= small_limit：直接暴力（保证涵盖所有跨多边界的特殊情况）。
        否则：
          Occ(N) = base_count + internal_large(N) + boundary_large(N)
        """
        if N <= self.small_limit:
            return count_in_prefix_string(self.pat_str, N)
        return self.base_count + self.count_internal_large(N) + self.count_boundary_large(N)


# -----------------------------------------
# 4) find f(n): the start position of n-th occurrence of n in S
# -----------------------------------------
def find_f(n: int) -> int:
    """
    求题目定义的 f(n)：n 在无限串 S 中第 n 次出现的起始位置（1-indexed）。

    做法：
      1) 用 PatternCounter 提供的 occ_end(N) 对 N 二分：
           找到最小 y，使得 Occ(y) >= n
         那么第 n 次出现一定“新发生在 y 的加入过程中”
         即发生在串 "...(y-1)(y)" 的某个窗口中，并且该窗口必须使用到 y 的数字。

      2) 令 before = Occ(y-1)，则在加入 y 这一段里新增的出现次数为：
           k = n - before
         我们只需在 W = str(y-1)+str(y) 中找出所有“跨到 y 一侧”的匹配起点，
         取第 k 个。

      3) 将该起点换算到全局位置：
           全局起点 = len("123...(y-2)") + (窗口起点 p) + 1
         其中 len("123...(y-2)") = digit_count_upto(y-2)
    """
    pc = PatternCounter(n)

    # --------------- 二分找 y ---------------
    # 找到最小 y，使得 Occ(y) >= n
    l, r = 1, 1
    while pc.occ(r) < n:
        r *= 2
    while l < r:
        mid = (l + r) // 2
        if pc.occ(mid) >= n:
            r = mid
        else:
            l = mid + 1
    y = l

    # before = Occ(y-1)，k 表示在“新增部分（加入 y）”里是第 k 个新增匹配
    before = pc.occ(y - 1) if y > 1 else 0
    k = n - before

    # --------------- 在 str(y-1)+str(y) 里定位第 k 个新增匹配 ---------------
    P = pc.pat_str
    m = pc.m

    left = str(y - 1) if y > 1 else ""
    right = str(y)
    W = left + right
    L = len(left)  # y-1 的长度，用于判断匹配是否“使用到了 y 的数字”

    # 收集所有匹配起点 p，且必须满足 p+m > L：
    #   - 若 p+m <= L，则匹配完全落在 left（y-1）内部，这不是“新增匹配”，应排除
    starts = []
    for p in range(0, len(W) - m + 1):
        if W[p:p + m] == P and p + m > L:
            starts.append(p)

    # 第 k 个新增匹配起点（0-index）
    p = starts[k - 1]

    # --------------- 还原到全局起始位置（1-indexed）---------------
    # digit_count_upto(y-2) 是 "123...(y-2)" 的长度
    # 再加上窗口起点 p，最后 +1 转为 1-indexed
    return digit_count_upto(y - 2) + p + 1


# -----------------------------------------
# 5) solve Project Euler 305
# -----------------------------------------
def solve():
    """
    题目要求：计算
      sum_{k=1..13} f(3^k)

    逐个求 f(3^k) 并累加即可。
    """
    total = 0
    x = 3
    for _ in range(K):
        total += find_f(x)
        x *= 3
    return total


if __name__ == "__main__":
    print(solve())