大厂真题

携程技术岗 2026-09-06

本场考试概述

考试时间：2026-9-6

考试岗位：技术岗

难度评级：中等

考点分析：

第一题：栈（简单）

第二题：调和级数分块 + 前缀和（困难）

建议策略：

只有两道题，第一题必须稳拿。它的题面把配对规则写得很长，但”左边最近的、尚未配对的左括号”就是栈顶，看出这一点后一趟扫描即可，注意内部长度为 的相邻括号在任何 下都要计入。

第二题是本场的分水岭。按定义逐个算是 次运算，必须先把 拆成 ，再利用 在整段上取值相同的性质配前缀和分块。总段数是调和级数量级，这个套路在数论与计数题里复用度很高，值得专门练。

第 1 题：括号配对计数

题目描述

小明 拿到了一个长度为 的括号序列 ，它只由字符 ( 和 ) 组成，并且保证是合法的：从左往右扫描它的任意一个前缀时，( 出现的次数都不少于 ) 出现的次数；扫描完整个序列后，两种字符出现的次数相等。

在合法序列中，每个 ) 都与它左边最近的、尚未被配对的 ( 组成一对。设某一对括号所在的位置分别是 和 ，把它们之间的字符个数称为这对括号的内部长度，即 ，也就是位置 上的字符数量。

给定一个正整数 ，小明 想知道内部长度能被 整除的括号对有多少个。注意 能被任意正整数整除。

输入描述

第一行输入两个整数 ，分别表示括号序列的长度和整除的模数，保证 是偶数。

第二行输入一个长度为 的字符串 ，只由字符 ( 和 ) 组成，保证是合法的括号序列。

输出描述

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

样例1

输入

2 1
()

输出

1

样例解释

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

样例2

输入

6 3
(()())

输出

2

样例解释

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

样例3

输入

8 5
((()()))

输出

2

样例解释

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

题解：栈

思路分析

给定一个合法括号串，每个 ) 与左边最近的、尚未配对的 ( 配成一对，位置 与 的这一对内部长度为 ，求内部长度能被 整除的对数。

这是一道配对规则直接决定数据结构的题：计数本身只是一次取模判断，难点在于看出”左边最近的、尚未配对的”这句话说的就是栈顶。

算法实现

先看最直白的想法。对每个 ) 从它的位置往左找配对的 (，途中还要跳过已经配好对的那些，最坏每个右括号都要回扫大半个串，总量 ， 取到 时约 次比较，远超时限。

问题在于左括号的信息被反复重扫，其实可以边走边攒。配对规则里的”最近”与”尚未配对”合起来说的是：左括号一旦被配走就永久出局，且总是最晚出现的那个未配对左括号最先被配走。后进先出，这正是栈。

于是扫描只需一趟。遇到 ( 就把它的下标压栈，遇到 ) 就弹出栈顶下标 ，当前下标即 ，两者当场配成一对，判一次

成立就把答案加一。题面保证串合法，所以每次遇到 ) 时栈一定非空，不必额外判空。

最容易漏的输入是内部长度为 的那些对。相邻的 () 有 ，而 能被任何正整数整除，所以它们在任何 下都要计入；串 ()()() 全由这类对组成，答案恒为 ，这也是本题答案的上界。

复杂度分析

时间复杂度：。每个字符只被访问一次，至多入栈、出栈各一次，取模是常数操作。读入串本身就要 ，这个量级已经到底。

空间复杂度：。栈中存放未配对左括号的下标，全嵌套串 ((())) 时栈深达到 。

题解代码

import sys
input = sys.stdin.readline

def count_pairs(t, m):
    stack = []
    ans = 0
    for r, ch in enumerate(t):
        if ch == '(':
            stack.append(r)
        else:
            l = stack.pop()
            if (r - l - 1) % m == 0:
                ans += 1
    return ans

n, m = map(int, input().split())
t = input().strip()
print(count_pairs(t, m))

正确性说明

栈中按顺序保存所有尚未匹配的左括号，当前右括号的匹配对象恰好是栈顶。每一对在弹栈时计算一次内部长度，故没有漏计和重复计数。

易错点与边界

内部长度是 r-l-1 而不是 r-l+1；零可被任意正整数整除。

第 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 的 % 对负数已返回非负，不必额外处理。

复杂度分析

时间复杂度：。瓶颈是对每个 的分段循环，总段数 是调和级数量级；前缀和与 的预处理只有 。

空间复杂度：。前缀和数组与存放 个答案的数组各占一份。

题解代码

import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7

def harmonic_sums(n, v):
    """求 H(1), H(2), ..., H(n) 对 MOD 取模的结果"""
    P = [0] * (n + 1)
    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):
        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
        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))))

正确性说明

将 i mod d 写成 i-d floor(i/d) 是恒等变换。每个整除商分段内的系数固定，前缀和精确求出段内权值和；各段不交且覆盖所有非零商下标，故分块总和等于定义式。

易错点与边界

下标从 0 开始；最后不足 d 长度的分段必须截断；模意义前缀差可能为负，Python 的正模数取余可正确归一化。

小结

优先从题面约束提炼模型，再用样例检查边界。本文保留题面数学符号的原始 SVG，代码统一为 Python 3；未给出的评测限制或规则不补作事实。