字符串哈希与等比数列求和技巧解析：牛客周赛 Round120 F 题穷无尽的数

在处理从无限循环字符串中截取子串的数字和问题时，一种高效的方法是结合字符串哈希预处理与等比数列求和公式。本文以牛客周赛 Round120 的 F 题 “穷无尽的数” 为例，详细拆解这一经典解题思路与C++实现。

问题分析与核心思路

题目核心是：给定一个长度为 n 的数字串 s，它被无限次重复拼接，形成一个无限长的数字串。需要快速计算该无限串中指定区间 [l, r]（下标从0开始）所构成的大整数的值，并对 998244353 取模。

核心思路

对于区间 [l, r]，我们可以将其在无限串中所覆盖的部分划分为三块：

1. 前缀 (L)：起始块（第 bl1 块）中从 l 到该块末尾的部分。
2. 中间完整块 (Mid)：从第 bl1+1 块到第 bl2-1 块的所有完整 s 串。
3. 后缀 (R)：结束块（第 bl2 块）中从块起始位置到 r 的部分。

整个区间的数值可以看作是：(L部分的值) + (Mid部分的值) + (R部分的值)，并需要考虑各部分因拼接产生的位数左移（即乘以10的幂次）。

具体实现拆解

• R部分：可直接利用预处理好的字符串哈希值获取。
• Mid部分：这部分由 k 个完整的 s 串拼接而成。它们在数值上构成一个等比数列。例如，字符串 “123” 重复3次，数值上等于 123 * 10^(6) + 123 * 10^(3) + 123。这正是一个首项为 hash(s)，公比为 10^n 的等比数列的前 k 项和。
• L部分：它是起始块的一个后缀，其哈希值可以直接计算。但在最终求和时，它需要左移 (Mid部分长度 + R部分长度) 位。

通过等比数列求和公式，我们可以 O(log MOD) 的时间复杂度求出 Mid 部分的值，避免了 O(k) 的线性计算。这是算法竞赛中处理此类周期性重复问题的关键技巧之一。

C++代码实现与注释

以下为完整的C++解决方案，结合了字符串哈希与快速幂模运算。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int inf = 0x3f3f3f;
const int mod = 998244353;

// 快速幂取模函数
int qsm(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, l, r;
    cin >> n >> l >> r;
    l--; r--; // 转换为从0开始的索引
    string s;
    cin >> s;

    // 预处理字符串哈希：p为幂次，h为前缀哈希值
    vector<int> p(n + 5), h(n + 5);
    p[0] = 1;
    for (int i = 0; i < n; i++) {
        p[i + 1] = p[i] * 10 % mod;
        h[i + 1] = (h[i] * 10 + (s[i] - '0')) % mod;
    }

    // 获取子串哈希值的函数（左闭右闭区间）
    auto get = [&](int l, int r) -> int {
        return (h[r + 1] - (h[l] * p[r - l + 1] % mod) + mod) % mod;
    };

    // 计算l和r所在的块编号(从1开始)以及在块内的偏移量
    int bl1 = l / n + 1;
    int bl2 = r / n + 1;
    int L = l % n;
    int R = r % n;

    // 情况1：l和r在同一块内
    if (bl1 == bl2) {
        cout << get(L, R) << endl;
        return 0;
    }

    // 情况2：l和r在不同块内
    int k = bl2 - bl1 - 1; // 完整块的数量
    int ans = 0;

    // 1. 计算后缀 R 部分的值
    ans = get(0, R);

    // 2. 计算前缀 L 部分的值，并左移 (k*n + R+1) 位
    int L_hash = get(L, n - 1);
    int left_shift_L = (n * k + R + 1) % (mod - 1);
    ans = (ans + L_hash * qsm(10, left_shift_L) % mod) % mod;

    // 3. 计算中间完整 Mid 部分（等比数列求和）
    if (k > 0) {
        int q = qsm(10, n); // 公比：10^n
        int a1 = h[n];      // 首项：整个串s的哈希值

        // 等比数列前k项和公式：a1 * (q^k - 1) / (q - 1)
        int q_pow_k = qsm(q, k);
        int numerator = a1 * ((q_pow_k - 1 + mod) % mod) % mod;
        int denominator_inv = qsm((q - 1 + mod) % mod, mod - 2); // 分母的乘法逆元
        int mid_sum = numerator * denominator_inv % mod;

        // Mid部分整体需要左移 (R+1) 位
        mid_sum = mid_sum * qsm(10, R + 1) % mod;
        ans = (ans + mid_sum) % mod;
    }

    cout << ans << endl;
    return 0;
}

关键点总结

1. 字符串哈希：用于 O(1) 时间获取原串任意子串的数值（取模后）。这是处理子串问题的基础数据结构。
2. 等比数列求和：将重复的完整串视为等比数列求和，将计算复杂度从 O(k) 降至 O(log k)，是本题的核心优化。
3. 模运算：全程注意模运算的规则，尤其是减法和除法（需用乘法逆元转为乘法）。在计算幂次 qsm(10, power) 时，指数 power 可以根据费马小定理对 (mod-1) 取模以进一步优化。
4. 偏移处理：仔细计算 L、Mid、R 三部分在最终拼接时的位数偏移，即需要乘以 10 的多少次方。

下图形象化地展示了区间 [l, r] 在无限循环串中的划分方式，其中不同颜色代表不同的计算部分：

通过这种“分块+哈希+等比求和”的组合方法，我们能够高效解决此类涉及无限循环字符串的数值计算问题。掌握其中的模运算和数学变换技巧，对于提升算法解题能力大有裨益。