没记错的话，第一次见到“HJ119 小红的01子序列构造（hard）”是在某次线上模拟赛的压轴位。当时我花了大半个小时在暴力枚举上死磕，样例都跑不对，一度怀疑自己连子序列定义都没搞明白。后来真正卡住我的是“本质不同”这四个字——等我把去重这件事想透了，这题的骨架其实非常干净：一个去重计数 DP，配合逐位构造的字典序贪心，就能漂亮地把第 K 小答案抠出来。
这篇文章写给两类人：一是准备算法竞赛、想系统掌握“第 K 小构造类题目”套路的选手；二是对字符串子序列计数感兴趣、想搞懂为什么不能简单枚举的学习者。我会把题面拆开，把 hard 点、去重原理、DP 设计、边界坑完整走一遍，最后给出可复现代码和几组测试用例。下面的推导不依赖任何平台上的原题细节，只要题目符合“本质不同子序列 + 字典序第 K 小”的设定，思路就能直接用。
1. 先把题目拆明白：小红要的子序列到底怎么算
1.1 题面还原与约定
我拿到的题面大概是这样一个版本：给定一个长度为 n 的 01 串 s，再给两个参数 k 和 K。小红想知道，s 的所有长度为 k 的子序列中，字典序第 K 小的那个是什么。如果长度为 k 的子序列根本不存在，或者 K 超过了本质不同子序列的总数，输出 -1。数据范围方面，n 可以到 2×10^5，k 在 1 到 n 之间，K 最大能到 10^18。
这里有三个非常容易理解偏的约定：
- 子序列不需要连续，但字符顺序必须保持原串中的相对顺序。
- 两个不同的位置选择方式，如果得到完全相同的字符串，只能算同一种子序列。这一步是整道题的分水岭。
- 字典序按字符比较，'0' 小于 '1'。先比第 1 位，再比第 2 位，依此类推。
为了后续讨论统一，我先把参数表列出来：
| 参数 | 含义 | 范围 |
|---|---|---|
| n | 原串长度 | ≤ 2×10^5 |
| s | 01 串，下标从 1 开始 | 长度 n |
| k | 需要构造的子序列长度 | 1 ≤ k ≤ n |
| K | 字典序排名（第 K 小） | 1 ≤ K ≤ 10^18 |
| 输出 | 第 K 小的本质不同子序列 | 不存在则输出 -1 |
这里的 K 是 64 位整数级别的，不是 int 能装下的。后面所有中间计数都得用 long long，甚至要做截断处理，否则还没开始构造就溢出了。
1.2 这个 hard 到底难在哪
有人可能会说：既然只要长度为 k 的子序列，枚举所有 C(n,k) 种选法，排序后取第 K 个不就行了？问题是数量。当 n=30 时，C(30,15) 已经超过 1.5 亿；n 一旦到 2×10^5，组合数直接超过任何整数类型能表达的范围，更别说逐条枚举了。
但组合爆炸只是“硬”的基础，真正让这道题配得上 hard 标签的有三个点：
- 要能快速数出某个前缀能引出多少种本质不同的子序列。这样才能在每一步决定第 K 小落到“填 0”分支还是“填 1”分支。
- 计数必须去重。如果不去重，同一个字符串会被多个位置组合重复统计，K 的语义就错了，后面的构造全部失真。
- 每一步的计数结果要扛得住 10^18 量级的 K。不能溢出，也不能因为状态太多而超时。
第 1 点和第 3 点是很多“第 K 小构造题”的共性，第 2 点是 01 串特有问题，也是整道题最容易翻车的地方。理解了这三点，后面思路就顺了。
2. 暴力枚举为什么想都别想：重复解是最大的坑
2.1 组合爆炸的规模感受一下
先说最朴素的思路：长度为 n，子序列长度为 k，位置选法就是 C(n,k)。当 n=2×10^5、k=10^5 时，这个数比宇宙中的原子数量还大好几个量级。不要说枚举，光是“生成一个字符串再比较一次”的复杂度就已经无法接受了。
更麻烦的是，即便 K 很小，比如 K=2，我们依然不能“只枚举前几个”。因为字典序第 K 小和位置选法的顺序没有任何关系，你无法知道第 2 小的字符串出现在第几次枚举里，除非把所有结果都生成出来再排序。
退一步说，假设我们用了某种剪枝，只生成“一部分”候选，但子序列的字典序不是按生成顺序排列的，剪枝很容易剪掉正确答案。所以暴力枚举这条路在第一步设计上就走死了。
2.2 同样一个子序列，原串里可能有一百种选法
我去重这个问题的真正顿悟，是在一个极端的例子上。s = “0000”，k=2。从 4 个位置里选 2 个，有 C(4,2)=6 种选法，但得到的子序列全都是 “00”。本质不同只有 1 种。如果题目不做去重，那“第 2 小”在哪？直接不存在。这个例子很夸张，但它说明了核心矛盾：位置选法的数量，和本质不同字符串的数量，完全是两套计数体系。
去重的标准做法是：给每一种字符串规定唯一的一组“代表位置”。最常见也最自然的规则是：构造字符串时，每次添加一个字符，都选择该字符在当前扫描位置之后第一次出现的位置。
为什么这样能去重？因为对于任意一个能在 s 中作为子序列出现的字符串 t，用“每次选择字符第一次出现位置”的贪心方式去选，得到的 t 只对应一组位置；反过来，任意一组位置也唯一确定一个字符串。于是“本质不同的子序列集合”和“按首次位置规则选出的序列集合”形成了一一对应。这个一一对应关系，是整个去重 DP 的地基。
我最初没想通这一点，直接写了一个“枚举每个位置选或不选”的 DP，数组里的数字大得离谱，调试了半天不知道错在哪。后来把状态改成“只关心下一个 0 在哪、下一个 1 在哪”，一切才豁然开朗。
2.3 我踩的第一个坑：把方案数当成了本质不同数量
这个坑在题目里特别隐蔽。如果你曾经刷过“统计一个字符串的所有不同子序列个数”的题，会知道那里也有一个去重套路：dp[i] = 2*dp[i-1] - dp[last[s[i]]-1]。很多选手会试图把那套公式直接搬到这题上来，但这里子序列长度是固定的 k，不是任意长度，而且还要支持“从某个位置之后开始计数”的查询，直接套公式会让状态设计变得很别扭。
我当时犯的错更基础：我统计的是“从 i 开始能选出多少条位置路径”，而不是“能选出多少种字符串”。路径数量天然是组合数的叠加，重复率极高。直到我把“首次位置规则”画出来，才发现正确的状态里根本不需要记录“具体选了哪些位置”，只需要记录“第一个 0/1 落在哪”。
3. 核心思路：从“找第 K 小”变成“逐位决定填空”
3.1 字典序的本质：第 i 位越小，字典序越小
想想我们平时怎么比较两个字符串。从左往右看，遇到第一个不同的字符，'0' 那边就比 '1' 那边小。所以找字典序第 K 小的子序列，完全可以逐位确定：先定第 1 位是 0 还是 1，再定第 2 位，依此类推。
这就像翻字典找单词。你先确定第一个字母，再确定第二个字母，每步都把候选集一分为二。关键在于，你必须知道一个数：如果这一位填 0，后面还能接出多少种长度为剩余量的本质不同子序列。这个数如果大于等于 K，说明答案第 1 位是 0；否则把 K 减去这个数，答案第 1 位就是 1。
这个“提前数数”的过程决定了效率。因为每一步只做一次“填 0 还是填 1”的判断，总步数就是 k，只要能在常数时间得到计数，整体算法就是 O(n·k) 量级——这已经比枚举所有子序列不知道快了多少个量级。
3.2 决定走 0 还是走 1，需要“提前数数”
假设当前我们从原串的某个位置 pos 之后继续选，还剩下 rem 个字符要填。先尝试填 '0'：
- 设 nxt0 为 s 在 pos 之后第一个 '0' 出现的位置；
- 如果 nxt0 存在，在 nxt0 之后还要选出 rem-1 个字符组成剩余部分，这个剩余部分的本质不同数量记为 cnt0。
- 如果 K ≤ cnt0，这一位确定为 '0'，下一轮从 nxt0 之后重新开始，rem 减 1。
- 如果 K > cnt0，说明第 K 小的子序列这一位是 '1'，K 先减去 cnt0（跨过所有以 0 开头的候选），再走 '1' 分支。
这里有一种边界情况：pos 之后根本没有 '0'，那 cnt0=0，自然直接落到 '1' 分支；如果连 '1' 也没有，说明当前已经无法继续构造，应该输出 -1。
于是核心子问题变成：给定一个起点 p 和一个长度 len，问 s[p..n] 能构造出多少种本质不同的长度为 len 的子序列。这个子问题用 DP 解决，下面就是最关键的推导。
3.3 DP 去重计数：只看每个字符最近出现的位置
定义 dp[i][j] 表示从位置 i 开始（包含 i），s[i..n] 能构造出的长度为 j 的本质不同子序列数量。因为只有 0 和 1 两种字符，转移只需要两支：
dp[i][j] = dp[nxt0(i) + 1][j - 1] + dp[nxt1(i) + 1][j - 1]
其中 nxt0(i) 表示 s[i..n] 中第一个 '0' 的位置，nxt1(i) 表示第一个 '1' 的位置。如果某个字符不存在，对应分支就是 0。初值 dp[i][0] = 1，表示空串有 1 种。
这个转移看起来简单，但正确性完全建立在 2.2 节的“首次位置规则”上。每一个从 i 开始的子序列，第一个字符要么是 '0' 且落在 nxt0(i)，要么是 '1' 且落在 nxt1(i)，两个分支互不重叠，因为第一个字符是确定的。而每个子序列只会被计数一次，因为后续字符的选取同样强制走“首次出现位置”。
用序列自动机的视角看会更直观：把每个位置看成一个状态，每个状态有两条出边，一条指向下一个 '0'，一条指向下一个 '1'。任何一个子序列都对应一条路径，而“每个字符只从首次出现位置走”相当于把所有平行边折叠成一条边，路径数量恰好等于本质不同子序列数量。dp 就是这张 DAG 上的路径计数。
4. 代码实操：next 数组、去重 DP 与构造器
4.1 预处理 next0 和 next1
实现时我统一用 1-based 下标，s 前面加一个占位空格。nxt0[i] 表示 s[i..n] 中第一个 '0' 的位置，如果不存在设为 n+1。倒着扫一遍就能预处理出来：
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; ll K; cin >> n >> k >> K; string s; cin >> s; s = " " + s; // 转成 1-based vector<int> nxt0(n + 2, n + 1), nxt1(n + 2, n + 1); int p0 = n + 1, p1 = n + 1; // 哨兵：不存在的位置 for (int i = n; i >= 1; --i) { if (s[i] == '0') p0 = i; else p1 = i; nxt0[i] = p0; nxt1[i] = p1; }注意这里我是在更新 p0/p1 之后再记录 nxt，所以 nxt0[i] 是“从 i 开始第一个 0”，包含了 i 本身。这个语义必须和 DP 状态保持一致。
4.2 计数 DP 的写法与 K 截断
dp[i][j] 从 i 倒序计算，因为转移用到的 nxt0[i]+1 一定大于 i，所以后面的状态会先算好。初值方面，dp[i][0]=1 对所有合法 i 成立，dp[n+1][j] 对 j>0 应该全是 0。
// dp[i][j]: s[i..n] 中长度为 j 的本质不同子序列数量 vector<vector<ll>> dp(n + 2, vector<ll>(k + 1, 0)); for (int i = 0; i <= n + 1; ++i) dp[i][0] = 1; for (int i = n; i >= 1; --i) { for (int j = 1; j <= k; ++j) { ll cnt = 0; if (nxt0[i] != n + 1) cnt += dp[nxt0[i] + 1][j - 1]; if (nxt1[i] != n + 1) cnt += dp[nxt1[i] + 1][j - 1]; if (cnt > K) cnt = K; // 截断，避免溢出 dp[i][j] = cnt; } }这里有一个非常容易写错的地方：dp[n+1][0] 的值。哨兵 n+1 表示“空后缀”，它不应该贡献任何非空子序列。上面的初值循环会把 dp[n+1][0] 设为 1，而 dp[n+1][j>0] 保持 0，这是正确的。但如果你顺手把 dp 初始化成全部为 1，或者用了 dp[n+2][0]=1 这种多余的状态，转移时就会发现空后缀也能“变出”长度为 1 的序列，样例直接崩掉。边界哨兵只保留一个，不要画蛇添足。
4.3 最后一步：按 K 的值逐位构造子序列
构造过程需要一个当前扫描位置 pre，初始 pre=0，表示从 s[pre+1..n] 这些位置里继续选。每次先定位从 pre+1 开始的第一个 0 和第一个 1，然后利用 DP 计数决定填哪个字符。
int pre = 0, rem = k; string ans; while (rem > 0) { int st = pre + 1; if (nxt0[st] == n + 1 && nxt1[st] == n + 1) { cout << -1 << '\n'; return 0; } int a = nxt0[st]; // 之后第一个 0 int b = nxt1[st]; // 之后第一个 1 ll cnt0 = 0; if (a != n + 1) cnt0 = dp[a + 1][rem - 1]; if (K <= cnt0) { ans.push_back('0'); pre = a; rem--; } else { K -= cnt0; if (b == n + 1) { // 理论上不会发生，但保留判断更稳 cout << -1 << '\n'; return 0; } ans.push_back('1'); pre = b; rem--; } } cout << ans << '\n';为什么要用 dp[a + 1][rem - 1] 而不是 dp[st][rem] 之类的东西？因为 dp[a+1] 表示从选中 a 位置之后开始选，正好排除掉已经用掉的 a；同时 a 是 st 之后第一个 0，正是“首次位置规则”规定的代表位置。看向 dp[st][rem] 会把所有没有明确首位字符的空串情况也卷进来，计数语义就错了。
5. 边界测试与踩坑记录：几个差点送走的 case
5.1 K 的起点问题：第 0 小是什么？
大部分题面里 K 从 1 开始，这个约定很重要。因为在构造过程中，每一步的判断都是 K ≤ cnt0，K 的最小值是 1，正好对应“取当前分支里第一个候选”。如果题目变体允许 K=0，那意味着要输出“字典序第 0 小”，通常等价于某种空串/特判，需要在构造前单独处理。我建议写代码前先确认 K 的下界，省得构造做到最后还是错的。
还有一点：如果输入给的 K 是 1，而长度为 k 的本质不同子序列至少有 1 种，那么答案永远是“所有长度为 k 的候选里字典序最小的那个”。这个最小的候选很好猜：尽量让前面的字符都填 0。用我们的构造逻辑跑一遍，会发现每一步 cnt0 都足够大，永远走 0 分支，最终输出一串尽量靠前的 0 和必要时的 1，结果完全正确。
5.2 填 0 分支计数为 0，但填 1 可行
构造时，如果 K > cnt0，说明所有以 0 开头的候选都被跨过了。这时 K 要减去 cnt0，再进入填 1 分支。很多人会在这里少写 K -= cnt0 这一行，导致后面所有判断全部偏移。
另一种情况更隐蔽：cnt0 是 0，K 是 1，直接 K>cnt0，于是填 1。这没问题。但如果 K 很大，比如 10^9，而 0 分支和 1 分支的总数都不足 K，理论上应该在某个时刻发现走不下去。由于 DP 被 K 截断过，这里不会出现“错误地认为足够”的问题吗？
答案是安全。设初始 K 为 K0，预处理时我们做的截断是 min(真实值, K0)。构造过程中 K 只会保持不变或减小，永远不会超过 K0。如果一个分支的真实数量小于当前 K，那么它也小于 K0，DP 里保留的就是真实值，判断正确；如果一个分支的真实数量不小于当前 K，那么它可能被截断为 K0，但只要真实值 ≥ 当前 K，截断后的值一定也 ≥ 当前 K，判断依然正确。这个“只截不断错”的性质，是 K 截断能用在这类题里的根本原因。
5.3 全 0、全 1 与大量重复字符
极端数据是检验去重 DP 是否写对的好工具。我用几组测试验证过：
| 输入 | 输出 | 说明 |
|---|---|---|
| s="0000", k=2, K=1 | "00" | 本质不同只有 1 种 |
| s="111", k=2, K=2 | "11" | 全 1，同样只有 1 种 |
| s="0101", k=2, K=2 | "01" | 所有长度为 2 的子序列：00,01,10,11 |
| s="1010", k=2, K=5 | -1 | 本质不同只有 00,01,10,11 |
| s="01", k=3, K=1 | -1 | 长度不足，无解 |
全 0 和全 1 这种串，长度 k 的子序列无论怎么选，结果都只有一种。如果 DP 写成了路径计数，这里会输出一个大于 1 的数字，K=2 时就会错误地进入某个分支，最后构造出乱七八糟的东西。能用这组用例跑通，说明去重逻辑基本没问题。
5.4 性能观察：n×k 打满怎么办
说句实话，最坏情况下 O(n×k) 在 n 和 k 都拉满到 2×10^5 时，无论是时间还是空间都扛不住。这也是这题被标 hard 的另一个原因。刷题时常见的应对方式有几种：
- 当 K 比较小时（比如 K ≤ 10^6），大量 dp 状态会被截断成 K，实际运算量远小于 n×k，跑起来飞快。
- 当 k 接近 n 时，可以考虑“反向删除”：长度为 k 的子序列等价于原串删掉 d=n-k 个字符。如果 d 很小，可以反过来做删除方案的构造，复杂度和 O(n·d) 相关，而不是 O(n·k)。
- 空间上 dp 可以滚动，因为 dp[i][j] 只依赖 j-1 层的状态，按 j 从 1 到 k 逐层计算，只需要两个长度为 n 的数组滚动使用。
我个人的经验是：先按 O(n×k)+截断写一版，能过大部分子任务和中等数据；如果题目明确给极限数据，再针对 k 和 n-k 的较小值选择正反方向。比赛里“能拿部分分 + 快速换方向”往往比死磕一个满分做法更划算。
6. 套路沉淀：这类“第 K 小构造题”的通用解法模型
6.1 和经典第 K 小子序列题的异同
如果你刷过“第 K 小子串”“第 K 小排列”这类题目，会发现核心套路是一样的：先做计数，再逐位构造。计数环节负责回答“以某个前缀开头的候选有多少个”，构造环节负责根据 K 的大小不断二分候选集。
不同的是“子串”天然不会有位置重复问题，而“子序列”必须处理同一字符串由不同位置组合造成重复计数的问题。这就是为什么子串题可以用后缀自动机或前缀和直接数，子序列题却要引入“首次位置规则”来做去重。理解了这一层，很多变体题都能看出共性：只要计数逻辑能去重，剩下的逐位构造框架可以原封不动地搬过去。
6.2 换题不换骨：从 01 串推广到字符集更大的题
如果题目把 01 串换成小写字母串，思路完全一样，只是转移从 2 个分支变成 26 个分支。dp[i][j] = Σ dp[nxt_c(i)+1][j-1]，其中 nxt_c(i) 表示 s[i..n] 中字符 c 第一次出现的位置。复杂度会乘以字符集大小，但只要字符集不大，依然可行。
如果题目要求“字典序第 K 大”，同样简单：把比较方向反过来，构造时先尝试填 1 分支即可。如果题目要求输出所有本质不同子序列，那 DP 去重计数可以直接用于回溯生成，只是数量多了会爆炸。
6.3 一点提速与调试建议
最后分享几个我实操中积累的小技巧：
- 预处理 next 数组时，哨兵统一用 n+1。这样“不存在”和“空后缀”是同一个值，判断分支会非常干净。
- DP 数组的初值只对 dp[i][0] 设 1，不要给非法状态随便设值。一个多余的哨兵会让错误发生得非常隐蔽。
- 构造答案时，手动维护 pre 而不是在 DP 表里记录位置。因为 DP 表是按长度和起点组织的，构造时需要在原串上跳跃，直接维护一个位置变量最直观。
- 调试时先跑全 0、全 1 样例，再跑有多个重复 0/1 的样例。这两类数据能快速暴露“是否真的去重了”的本质问题。
这套模型我后来在好几道变体题里都直接套用过，包括字符集 26 的“第 K 小子序列”、带循环节的“周期串子序列”等。只要计数去重这一关过了，逐位构造的代码几乎不用改，直接就是稳定输出。
