大厂真题 / 阿里巴巴
阿里 4.25 笔试真题 - 算法岗
本场考试概述
考试时间：2026年4月25日 考试岗位：算法岗 难度评级：中等偏难
考点分析：
- 第一题：组合数学（难度中等）
- 第二题：排序 + 二分查找（难度中等）
- 第三题：动态规划（难度困难）
建议策略：
- 第一题的组合数学推导是关键——想清楚排列与操作序列的一一对应关系后做法极简
- 第二三题需要扎实的二分和 DP 能力，建议优先稳住前两题分数
第一题：插入顺序
题目描述
给定长度为 $n$ 的字符串 $s$。从空串开始，共进行 $n$ 次操作，每次在当前字符串的任意位置插入一个小写字母。问一共有多少种不同的操作序列，使得最终得到字符串 $s$。
两个操作序列不同，当且仅当在某一步中，选择的插入位置或插入的小写字母不同。答案对 $10^9 + 7$ 取模。
多组测试数据，$n$ 之和不超过 $5 \times 10^5$。
样例
输入
2
1
a
3
aba
输出
1
6
思路分析
第一步：建立操作序列与排列的对应
每个操作序列可以用”哪个位置的字符在第几步被插入”来描述。这构成一个 $1$ 到 $n$ 的排列：排列的第 $k$ 个值表示”第 $k$ 步插入的是最终字符串中第几个位置的字符”。
第二步：排列唯一确定操作序列
给定一个排列后：
- 第 $k$ 步插入的字符由最终字符串 $s$ 决定（字符确定）
- 插入位置等于”该位置左侧有多少个已插入的位置”（位置确定）
从最终串逆向可唯一还原排列，不同排列对应不同操作序列。
第三步：答案就是 $n!$
每一种排列对应恰好一种合法的操作序列，因此答案就是 $n!$。预处理阶乘表后直接查询。
注意：字符串的内容完全不影响答案——无论字母是什么，排列数都是 $n!$。
题解代码
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
MAXN = 500001
fact = [1] * MAXN
for i in range(1, MAXN):
fact[i] = fact[i - 1] * i % MOD
T = int(input())
out = []
for _ in range(T):
n = int(input())
s = input().strip()
out.append(str(fact[n]))
print("\n".join(out))
复杂度分析
时间复杂度：$O(N + T)$，预处理阶乘 $O(N)$，每组查询 $O(1)$。 空间复杂度：$O(N)$，存储阶乘数组。
第二题：矩阵计数
题目描述
给定两个整数序列 $a$（长度 $n$）和 $b$（长度 $m$），以及阈值 $k$。构造矩阵 $C$，其中 $C_{i,j} = a_i \times b_j$。统计矩阵中有多少个元素满足 $C_{i,j} \geq k$。
多组测试数据，$n + m$ 之和不超过 $2 \times 10^5$。所有元素为非负整数。
样例
输入
3
3 3 6
1 2 3
2 3 4
2 4 1
0 5
0 1 1 10
2 3 1
1 1 1
输出
5
2
6
思路分析
第一步：暴力为什么不行
直接枚举所有 $n \times m$ 个元素的复杂度为 $O(nm)$，$n$ 和 $m$ 均可达 $10^5$，$O(10^{10})$ 无法承受。
第二步：排序 + 二分
对 $b$ 排序后，对每个 $a_i$，满足 $a_i \times b_j \geq k$ 的 $b_j$ 构成排序后的一个后缀。对于 $a_i > 0$，条件等价于 $b_j \geq \lceil k / a_i \rceil$，可以用二分查找在 $O(\log m)$ 内定位后缀的起始位置。
第三步：$a_i = 0$ 的特殊处理
$0 \times b_j = 0$，仅当 $k = 0$ 时全部 $m$ 个元素满足条件。
题解代码
import sys
from bisect import bisect_left
input = sys.stdin.readline
T = int(input())
out = []
for _ in range(T):
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
b.sort()
ans = 0
for ai in a:
if ai == 0:
if k == 0:
ans += m
else:
t = (k + ai - 1) // ai
ans += m - bisect_left(b, t)
out.append(str(ans))
print("\n".join(out))
复杂度分析
时间复杂度：$O((n + m) \log m)$，排序 $O(m \log m)$，每个 $a_i$ 二分 $O(\log m)$。 空间复杂度：$O(n + m)$，存储两个数组。
第三题：取模仪式
题目描述
给定正整数数组 $a$（长度 $n$）和初始数字 $x$。将数组重新排列为任意排列 $p$，然后从 $x$ 开始依次执行 $x \leftarrow x \bmod p_i$（$i = 1, 2, \dots, n$）。求所有排列中可能得到的最大最终值。
$n \leq 500$，$x \leq 10^9$，$a_i \leq 10^5$。
样例
输入
2
3 20
5 6 8
5 37
7 13 6 10 4
输出
4
3
思路分析
第一步：观察取模的性质
$x \bmod a_i$：当 $a_i > x$ 时无效（$x$ 不变）；当 $a_i \leq x$ 时 $x$ 严格变小，变为 $x \bmod a_i < a_i$。
真正改变 $x$ 的取模器构成一个值的递减序列。同一个值最多生效一次——重复对相同值取模不会改变结果。因此可以先去重，问题归结为对去重后的值做决策。
第二步：动态规划状态定义
将去重后的值降序排列为 $v_0 > v_1 > \dots > v_{k-1}$。定义：
\[g[i][y] = \text{还剩 } v_i, v_{i+1}, \dots, v_{k-1} \text{ 未使用，当前值为 } y \text{ 时的最大最终值}\]第三步：状态转移
从 $i = k-1$ 倒推到 $i = 0$。对于 $v_i$ 和当前值 $y$，有两条路：
- 立即使用（$v_i \leq y$ 时可选）：$y$ 变成 $y \bmod v_i$，后续得到 $g[i+1][y \bmod v_i]$
- 推迟到最后：先让更小的值处理完得到 $\text{res} = g[i+1][y]$，再对 $v_i$ 取模——若 $v_i \leq \text{res}$ 则得 $\text{res} \bmod v_i$，否则 $\text{res}$ 不变
两条路取最大值。
第四步：处理大 $x$
$x$ 可能很大（$\leq 10^9$），无法直接做下标。但第一次有效取模后 $x < v_0 \leq 10^5$，进入 DP 范围。枚举第一个取模器 $v_j$，取模后查 DP 表取最大值。
题解代码
import sys
input = sys.stdin.readline
T = int(input())
out = []
for _ in range(T):
n, x = map(int, input().split())
a = list(map(int, input().split()))
vals = sorted(set(a), reverse=True)
k = len(vals)
max_val = vals[0]
g = [None] * (k + 1)
g[k] = list(range(max_val))
for i in range(k - 1, -1, -1):
v = vals[i]
cur = [0] * max_val
for y in range(max_val):
res = g[i + 1][y]
delayed = res % v if v <= res else res
if v <= y:
used = g[i + 1][y % v]
cur[y] = max(used, delayed)
else:
cur[y] = delayed
g[i] = cur
if x < max_val:
ans = g[0][x]
else:
ans = 0
for j in range(k):
y = x % vals[j]
ans = max(ans, g[j + 1][y])
out.append(str(ans))
print("\n".join(out))
复杂度分析
时间复杂度：$O(k \times V)$，其中 $k$ 为去重后的值个数（$\leq 500$），$V = \max(a_i) \leq 10^5$。 空间复杂度：$O(k \times V)$，DP 表。
小结
- 第一题的组合数学结论出乎意料地简洁——每种排列恰好对应一种合法操作序列，答案就是 $n!$。关键在于想清楚排列与操作的一一映射关系
- 第二题是经典的”乘积 $\geq k$”计数问题，排序一个数组后对另一个数组逐元素二分，把 $O(nm)$ 优化到 $O((n+m) \log m)$
- 第三题将取模排列优化问题转化为 DP：去重后按值从大到小倒推，每个取模器”用或不用”两路取最大值，利用值域有限性保证 DP 可行