大厂真题 / 携程

携程 2026-9-6 笔试真题 - 技术岗

证据边界：本文依据公开题解材料整理。原文中的部分数学公式在网页抽取时以 SVG 形式保存，文本版无法可靠恢复的变量、约束或表达式不擅自补写。

本文整理这场考试的题面、思路与参考实现。

本场考试概述

考试时间 ：2026-9-6 考试岗位 ：技术岗 难度评级 ：中等 考点分析 ： 第一题：栈（简单） 第二题：调和级数分块 + 前缀和（困难） 建议策略 ： 只有两道题，第一题必须稳拿。它的题面把配对规则写得很长，但”左边最近的、尚未配对的左括号”就是栈顶，看出这一点后一趟扫描即可，注意内部长度为 的相邻括号在任何 下都要计入。 第二题是本场的分水岭。按定义逐个算是 次运算，必须先把 拆成 ，再利用 在整段上取值相同的性质配前缀和分块。总段数是调和级数量级，这个套路在数论与计数题里复用度很高，值得专门练。

第1题：括号配对计数

题目描述

拿到了一个长度为 的括号序列 ，它只由字符 ( 和 ) 组成，并且保证是合法的：从左往右扫描它的任意一个前缀时，( 出现的次数都不少于 ) 出现的次数；扫描完整个序列后，两种字符出现的次数相等。 在合法序列中，每个 ) 都与它左边最近的、尚未被配对的 ( 组成一对。设某一对括号所在的位置分别是 和 ，把它们之间的字符个数称为这对括号的内部长度，即 ，也就是位置 上的字符数量。 给定一个正整数 ，想知道内部长度能被 整除的括号对有多少个。注意 能被任意正整数整除。

输入描述

第一行输入两个整数 ，分别表示括号序列的长度和整除的模数，保证 是偶数。 第二行输入一个长度为 的字符串 ，只由字符 ( 和 ) 组成，保证是合法的括号序列。

输出描述

输出一个整数，表示内部长度能被 整除的括号对数量。

样例1

输入

2 1
()

输出

1

样例解释 唯一的一对括号位于位置 和 ，内部长度为 。 能被 整除，因此答案为 。

样例2

输入

6 3
(()())

输出

2

样例解释 三对括号的内部长度依次为：位置 与 配对，内部长度 ；位置 与 配对，内部长度 ；位置 与 配对，内部长度 。其中 能被 整除而 不能，因此答案为 。

样例3

输入

8 5
((()()))

输出

2

样例解释 四对括号的内部长度依次为 。只有两个 能被 整除， 和 都不能，因此答案为 。

题解：栈

题目问题拆解

给定一个合法括号串，每个 ) 与左边最近的、尚未配对的 ( 配成一对，位置 与 的这一对内部长度为 ，求内部长度能被 整除的对数。 这是一道配对规则直接决定数据结构的题：计数本身只是一次取模判断，难点在于看出”左边最近的、尚未配对的”这句话说的就是栈顶。

算法实现

先看最直白的想法。对每个 ) 从它的位置往左找配对的 (，途中还要跳过已经配好对的那些，最坏每个右括号都要回扫大半个串，总量 ， 取到 时约 次比较，远超时限。 问题在于左括号的信息被反复重扫，其实可以边走边攒。配对规则里的”最近”与”尚未配对”合起来说的是：左括号一旦被配走就永久出局，且总是最晚出现的那个未配对左括号最先被配走。后进先出，这正是栈。 于是扫描只需一趟。遇到 ( 就把它的下标压栈，遇到 ) 就弹出栈顶下标 ，当前下标即 ，两者当场配成一对，判一次 成立就把答案加一。题面保证串合法，所以每次遇到 ) 时栈一定非空，不必额外判空。 最容易漏的输入是内部长度为 的那些对。相邻的 () 有 ，而 能被任何正整数整除，所以它们在任何 下都要计入；串 ()()() 全由这类对组成，答案恒为 ，这也是本题答案的上界。

时空复杂度分析

时间复杂度 ：。每个字符只被访问一次，至多入栈、出栈各一次，取模是常数操作。读入串本身就要 ，这个量级已经到底。 空间复杂度 ：。栈中存放未配对左括号的下标，全嵌套串 ((())) 时栈深达到 。 Python

# 括号配对计数 - 栈


# 扫描一遍括号串，统计内部长度能被 m 整除的括号对个数
def count_pairs(t, m):
    # 栈里存放尚未被配对的 '(' 的下标，栈顶就是"左边最近的未配对左括号"
    stack = []
    ans = 0
    for r, ch in enumerate(t):
        if ch == '(':
            # 左括号先入栈等待，将来由某个右括号来认领
            stack.append(r)
        else:
            # 合法串保证栈非空，栈顶下标 l 与当前 r 恰好配成一对
            l = stack.pop()
            # 内部长度就是两端之间的字符个数 r - l - 1，注意 0 能被任意 m 整除
            if (r - l - 1) % m == 0:
                ans += 1
    return ans


# 第一行读 n 和 m，n 只用来描述长度，判定只需要 m
n, m = map(int, input().split())
t = input().strip()
print(count_pairs(t, m))

第2题：余数加权和

题目描述

有一个长度为 的数组 ，下标从 开始编号，依次为 。 对于一个正整数 ，定义这个数组在模数 下的加权和 为：把每个下标 对 取余得到的结果乘上 ，再把所有乘积相加，即 请依次求出 的值。由于结果可能很大，请把每个值都对 取模后输出。

输入描述

第一行输入一个整数 ，表示数组的长度。 第二行输入 个整数 ，表示数组中的元素。

输出描述

输出一行 个整数，依次表示 对 取模后的结果，相邻两个整数之间用一个空格分隔。

样例1

输入

4
3 1 4 2

输出

0 3 9 15

样例解释 中任何下标对 取余都是 ，总和为 。。。。

样例2

输入

1
8

输出

0

样例解释 数组中只有下标为 的一个元素，。

样例3

输入

6
2 0 5 1 0 3

输出

0 4 16 16 13 28

样例解释 仍然是 。 对应的余数序列是 ，加权和为 。 对应的余数序列是 ，加权和为 。 对应的余数序列是 ，加权和为 。 对应的余数序列是 ，加权和为 。 中所有下标都小于 ，加权和就是 。

题解：调和级数分块 + 前缀和

题目问题拆解

给定长度为 的数组 ，对每个 从 到 ，求下标对 取余后再与 相乘的总和，一共输出 个结果。 这是一道靠恒等变形换算法的题：按定义逐个算需要 轮、每轮 次取余， 取到 时是 次运算，必须把取余改写成可以整段处理的形式。

算法实现

先把取余拆开。对任意正整数 有 ，代入定义式得 左边那项与 无关，记 它只需在读入时算一次，此后每个 直接取用。 再看右边那项。 不像 那样每步都变，它在 落入 的整段区间上恒等于 ，整个下标范围只被切成 段。段内的系数既然固定，需要的就只是段内 之和，取前缀和 即可 拿到。于是右边那项写成按段累加的形式： 的那一段系数为 ，扫描从 的起点 开始即可；末段可能不满 个下标，右端点截到 。 这套做法之所以跑得动，在于总段数是调和级数：对固定的 有 段，所有 加起来约 ， 时约 段，比朴素解低了四个数量级。 取模有两处要留意。 与段和都可达 与模数量级，乘积到 ， 同理，C++、Java、Go 必须全程用 64 位整数并逐步取模。 在模意义下可能为负，要写成 修正；Python 的 % 对负数已返回非负，不必额外处理。

时空复杂度分析

时间复杂度 ：。瓶颈是对每个 的分段循环，总段数 是调和级数量级；前缀和与 的预处理只有 。 空间复杂度 ：。前缀和数组与存放 个答案的数组各占一份。 Python

# 余数加权和 - 调和级数分块 + 前缀和

MOD = 10 ** 9 + 7


def harmonic_sums(n, v):
    """求 H(1), H(2), ..., H(n) 对 MOD 取模的结果"""
    # 前缀和 P[j] = v[0]+...+v[j-1]（模意义），用来 O(1) 取出任意一段下标上的 v 之和
    P = [0] * (n + 1)
    # S = sum(i*v[i])，它与 d 无关，是每个 H(d) 共用的常量部分
    S = 0
    s = 0
    for i in range(n):
        s += v[i]
        if s >= MOD:
            s -= MOD
        P[i + 1] = s
        S = (S + i * v[i]) % MOD

    res = [0] * n
    for d in range(1, n + 1):
        # 由 i mod d = i - d*floor(i/d) 得 H(d) = S - d * sum(floor(i/d) * v[i])
        # 把下标按 k = floor(i/d) 分段：第 k 段是 [k*d, k*d+d-1]，段内 k 相同，
        # 于是整段的贡献 = k * 段内 v 之和，一次前缀和相减就得到
        t = 0
        k = 1
        start = d          # k=0 那一段乘的是 0，直接从 k=1 的起点 d 开始扫
        while start < n:
            end = start + d
            if end > n:
                end = n    # 最后一段可能不满 d 个，右端点截到 n
            t = (t + k * (P[end] - P[start])) % MOD
            k += 1
            start += d
        # Python 的 % 对负数返回非负，减法为负时不必额外修正
        res[d - 1] = (S - d * t) % MOD
    return res


n = int(input())
v = list(map(int, input().split()))
print(' '.join(map(str, harmonic_sums(n, v))))