1. 题目回顾：一个看起来不可能的构造题

CF1554D 是 Codeforces Round 1554 的 D 题，题名叫 Diane。题面本身短到可以抄在便签纸上：给你一个正整数 n，请你构造一个长度为 n、只由小写字母组成的字符串，要求字符串的每个子串在它里面出现的次数都是奇数。

我第一次看到这个要求时，第一反应是"这题是不是在玩我"。因为随便写一个字符串，比如 "abab"，子串 "a" 出现 2 次就已经违规了；"ab" 也出现 2 次，同样违规。哪怕你想取巧，输出 n 个 'a'，子串 "a" 出现 n 次，子串 "aa" 出现 n-1 次，n 和 n-1 的奇偶性必然不同，总有一个是偶数。换句话说，最朴素的两种思路——全 a 串和随便乱写——都是死路。

但这类构造题有一个特点：题目越像"不可能"，往往越藏着一条特别简洁的出路。Diane 这道题的核心不在什么高级数据结构上，而在一个非常朴素的观察——只要字符串里存在某个只出现一次的字符，所有包含它的子串就自动满足条件了。想通这一点，代码只需要五行。

这篇主要适合正在刷 Div2 D 级别构造题、想练奇偶性思维的人。就算你只有最基础的概念，知道子串是字符串里连续的一段，也能顺着下面的思路把它完整推出来。

1.1 题面到底在说什么

先把已知条件理清楚。"子串出现次数"指的是同一个字符串在整个字符串中作为连续片段一共出现多少次。例如 s = "aaba"，子串 "a" 出现 3 次，分别落在位置 1、2、4；子串 "aa" 出现 1 次（位置 1-2）；子串 "ab" 出现 1 次（位置 2-3）；子串 "ba" 出现 1 次（位置 3-4）。注意这里统计的是不同的子串内容，不是按照位置去数；一个子串出现多少次，就是统计它在 s 里所有能匹配的位置总数。

题目有多组测试用例，每个给一个 n，要求对每个 n 输出一组合法字符串。输出哪个合法字符串都可以，不要求唯一。n 的范围给得很大，所以你几乎不可能用"枚举候选串 + 验证"的思路去做，必须直接给一个公式化的构造。这类题在 CF 里经常出现，考验的不是你会不会后缀数组，而是你能不能从数学上找到一个处处成立的充分条件。

1.2 为什么"全 a 串"和"随便写"必然失败

如果整个字符串全是 'a'，长度为 n，那么子串 'a' 出现 n 次，子串 "aa" 出现 n-1 次。这两个次数一个是 n，一个是 n-1，奇偶性必然相反，所以至少有一个是偶数，直接违规。这个简单反例揭示了一个重要事实：一段连续的相同字符越长，不同长度的子串出现次数会形成 n、n-1、n-2、… 的递减序列，奇偶性跟着交替。想打破这种交替，就必须用其他字符把长串的 a 切开。

"随便写"同样不行。但凡某个字符在整个串里出现偶数次，长度为 1 的子串就已经违规了；而想让所有字符的出现次数都是奇数，本身已经是很强的约束。再加上长度为 2、3 的子串也要满足条件，随便构造几乎必挂。这道题真正要你回答的问题是：在这么多"必须满足"的限制下，到底存在不存在一个统一的构造模板？答案是存在，而且模板非常简单。

1.3 一个关键的破题视角：先找"天生安全"的子串

在思考构造之前，先问自己一个问题：什么样的子串不管怎样出现都是奇数？答案脱口而出：出现次数为 1 的子串。如果某个字符串在整个大串里只可能出现一次，那它当然是奇数。顺着这个思路继续：如果有一个字符只在整个串里出现一次，那么任何包含这个字符的子串都只能出现一次。因为你想再找一处一模一样的匹配，至少得再找一个同样的字符出来——但它只有一个。

于是整个问题被一下子简化了：把字符串设计成"大量危险的 a 串区域，被一些只出现一次的字符隔开"，然后专心处理那些不包含特殊字符的纯 a 子串。这就是 Diane 的全部秘密。剩下的事情，无非是用一个奇偶性公式选出最合适的块长。

2. 破题思路：把"奇数"翻译成奇偶性

现在进入正题。设我们的构造形态是：

左段 p 个 'a' + 一堵特殊的"墙" + 右段 q 个 'a'

墙里面放一个或两个"只出现一次"的字符。这样一来，所有包含墙字符的子串都天然出现奇数次（更准确地说恰好一次），我们只需要验证纯 a 子串即可。这个"先隔离再处理"的思路，比直接对着整个字符串想条件要清爽得多。

2.1 单段 a 串的子串计数

先把基础公式写清楚。假设有一段连续的 R 个 'a'，那么对由 L 个 'a' 组成的子串 A_L（也就是 "a" 重复 L 次），它在这段里出现的次数是：

R - L + 1

原因是 A_L 可以以第 1 到第 R-L+1 个位置作为开头。比如 "aaaa" 里，"a" 出现 4 次，"aa" 出现 3 次，"aaa" 出现 2 次，"aaaa" 出现 1 次。这虽然是小学数学，但它是今天所有推导的地基——构造题里真正决定成败的往往就是这种小学公式加上一个模 2 的观察。

2.2 两段 a 串合并时，出现次数怎么算

我们的构造是左段 p 个、右段 q 个，中间是墙，墙里没有 'a'。那么一个纯 a 子串 A_L 到底出现几次？分两种情况：

• 如果 L 同时不超过 p 和 q，左右两段都有贡献：左边贡献 p-L+1 次，右边贡献 q-L+1 次，总数是 (p-L+1) + (q-L+1) = p+q-2L+2。
• 如果 L 只能被其中一段完全容纳，那就只算那一段的贡献。

第一行那个式子有个非常漂亮的性质：p+q-2L+2 对 2 取模，等于 p+q 对 2 取模。因为 -2L+2 永远是偶数，完全不影响奇偶性。换句话说：只要 p+q 是奇数，那么所有满足 L ≤ min(p,q) 的纯 a 子串，出现次数一律是奇数，和 L 的具体大小一点关系都没有。这是本题最核心的结论。

你可能要追问：那 L 超过 min(p,q) 怎么办？比如 L = p 但 q < p 时，右边没贡献，只有左边贡献 p-L+1，而这个数不一定是奇数。但注意，在我们的最终构造里 p 和 q 只相差 1，所以这种"一边不够放"的情况只可能发生在 L 恰好等于 p 时，那时 p-L+1 = 1，正好是奇数。这个细节等第 3 节构造完毕后再严格检查一遍。

2.3 为什么必须是两段，而不是一段或三段

既然关键结论是 p+q 要为奇数，有人会想：那干脆把 a 串切成一段不就行了？不行，一段时计数公式是 R-L+1，奇偶性随 L 交替变化，全 a 串反例已经说明问题。那三段呢？

假设三段长度是 p1、p2、p3，对不超过三个数最小值的 L，出现次数是 (p1-L+1)+(p2-L+1)+(p3-L+1) = S - 3L + 3，其中 S 是 a 的总数。这个式子对 2 取模会得到 S + 3(1-L) ≡ S + 1 - L (mod 2)，也就是说它还依赖 L 的奇偶，并没有被消干净。更一般地，k 段 a 串的计数是 S - kL + k，奇偶性 = S + k(1-L) (mod 2)，只有当 k 是偶数时，L 前面的系数才会消失。两段是满足这个条件的最简单选择，出题人的答案形态几乎是被数学逼出来的。

这段分析平时不会写进题解，但我觉得它比结论本身更值得记住：当你发现一个式子"恰好只跟总数有关、跟具体长度无关"时，多半是设计者精心挑过段数。做题时遇到类似情况，可以主动往"段数必须是偶数"这个方向想。

2.4 墙的长度也有限制

现在约束条件逐渐成形：墙里的字符必须都只出现一次；左右两段 a 的块长之和 p+q 必须为奇数；同时整串长度必须是 n。这三个条件会精确逼出最终构造。墙为什么有时候要一个字、有时候要两个字？因为墙字符同样占用长度，而 n 的奇偶性决定了你能往墙里塞多少东西。下一节按 n 的奇偶性分别求解，你会发现所有参数都是定死的，没有自由发挥空间。

3. 构造方案与完整证明

3.1 n 为偶数：n = 2m

偶数时直接用一个字符 'b' 当墙。构造：

s = 'a' 重复 m 次 + 'b' + 'a' 重复 m-1 次

长度：m + 1 + (m-1) = 2m = n，正好。左段 p = m，右段 q = m-1，p+q = 2m-1，是奇数，完美满足奇偶性条件。

验证部分：

• 纯 a 子串 A_L：当 L ≤ m-1 时，出现次数是 (m-L+1)+(m-1-L+1) = 2m-2L+1，是奇数；当 L = m 时，只有左段容纳得下，出现 1 次，也是奇数。L 再大就不存在了，不需要管。
• 包含 'b' 的子串：'b' 只出现一次，所以所有包含它的子串都恰好出现一次。
• 两者并集覆盖了全部子串，结论成立。

举几个小例子，用表格记录实际计数：

表格里 1、3、5 全是奇数，其他子串要么出现 1 次，要么根本不存在。条件全部满足。

3.2 n 为奇数且 n ≥ 3：n = 2m+1

奇数才是最需要小心的。很多人第一次会照抄偶数思路，写成 'a'*m + 'b' + 'a'*m，长度是 2m+1 刚好对，但此时 p = q = m，p+q = 2m 是偶数，子串 'a' 出现 2m 次，直接违规。这个坑我后面还会专门复盘。

于是我们把墙做长一点：用两个不同的字符 'b' 和 'c' 当墙。构造：

s = 'a' 重复 m 次 + 'bc' + 'a' 重复 m-1 次

长度：m + 2 + (m-1) = 2m+1 = n，正好。p = m，q = m-1，p+q = 2m-1，又是奇数。验证方法和偶数情况完全对称：

• 纯 a 子串 A_L：L ≤ m-1 时，出现 2m-2L+1 次，是奇数；L = m 时只有左段出现 1 次，奇数。
• 包含 'b' 或 'c' 的子串：'b' 出现一次、'c' 出现一次，任何包含其中至少一个字符的子串都只能在唯一位置匹配，所以恰好出现一次。
• 全部子串都是奇数，构造正确。

注意墙为什么必须是两个互不相同的字符。如果你在奇数长度里也只用单个 'b' 当墙，为了凑出 p+q 为奇数，p 和 q 只能差 1，比如 m 和 m-1，但这样总长度是 m + 1 + (m-1) = 2m，比 n 少 1，还得额外再塞一个字符。与其硬塞到某段 a 里破坏奇偶性，不如直接让墙占两个位置，反正墙字符只出现一次的特性依然成立。而两个墙字符如果相同，比如 "bb"，'b' 就出现两次，子串 'b' 出现偶数次，也不行。所以 "bc" 这种互不相同的组合是最自然的选择，你把它换成 "xy"、"mn" 也完全没问题。

3.3 边界情况：n = 1

n = 1 时，上面的奇数构造会得到 'a'0 + "bc" + 'a'(-1)，右段长度是负数，显然不对。所以单独特判：直接输出 "a"。整个字符串只有一个子串 "a"，出现 1 次，奇数，合法。

到这里，所有 n 的情况都有了构造方案，整理成一张总表：

3.4 用手工验证几个小 n

我写题解前习惯先用程序对 n=1..20 全部跑一遍，这里给两个手工能算的例子，让你直观感受构造串长什么样。

n = 5 时，m = 2，构造是 "aabca"。纯 a 子串方面，"a" 出现 3 次，"aa" 出现 1 次；包含 'b' 或 'c' 的，比如 "ab"、"bc"、"ca"、"aab"、"abc"、"bca"、"aabc"、"abca"、"aabca"，全都是 1 次，因为 b、c 各只出现一次。全部奇数。

n = 7 时，构造是 "aaabcaa"。"a" 出现 5 次，"aa" 出现 3 次，"aaa" 出现 1 次；其余含墙字符的子串最多出现 1 次。又是全部奇数。

4. 最短的 AC 代码与复杂度分析

思路理清楚之后，实现几乎没有技术含量。下面给出 C++17 和 Python 两个版本，都是 O(n)。

4.1 C++17 实现

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; string ans; if (n == 1) { ans = "a"; } else if (n % 2 == 0) { int m = n / 2; ans = string(m, 'a') + "b" + string(m - 1, 'a'); } else { int m = n / 2; ans = string(m, 'a') + "bc" + string(m - 1, 'a'); } cout << ans << '\n'; } return 0; }

C++ 的 string(cnt, ch) 构造器会生成 cnt 个指定字符，复杂度 O(cnt)。三个部分拼起来总长度正好是 n，所以每个测试用例 O(n)，总复杂度 O(∑n)。代码里不需要任何高级数据结构，也别去写什么后缀自动机。

4.2 Python 实现

import sys def solve(): data = sys.stdin.read().split() t = int(data[0]) out = [] idx = 1 for _ in range(t): n = int(data[idx]) idx += 1 if n == 1: out.append("a") elif n % 2 == 0: m = n // 2 out.append('a' * m + 'b' + 'a' * (m - 1)) else: m = n // 2 out.append('a' * m + 'bc' + 'a' * (m - 1)) sys.stdout.write('\n'.join(out)) if __name__ == "__main__": solve()

Python 里 'a' * m 生成 m 个字符，同样是线性操作。一次性读入所有数据、最后统一输出，这样可以避免逐行 print 在大数据量下的额外开销，属于一个很基础但也实用的 IO 习惯。

4.3 复杂度和实现注意点

• 时间复杂度：每个测试用例 O(n)，总 O(∑n)。这类题的数据规模通常是总和上百万级别，线性做法完全够用。
• 空间复杂度：除了存答案字符串 O(n) 外，没有任何额外空间。
• 多测试用例格式：题目给了 T，记得每个答案单独换行，最后一个字符串也要换行。
• n=1 特判必须放在最前面：奇数分支在 n=1 时会算到负数的重复次数，C++ 的 string(m-1, 'a') 在 m-1 为负数时会抛出异常或产生未定义行为；Python 里 'a' * -1 是空串，最终会构造出长度为 2 的 "bc"，完全错误。

5. 常见错误与对拍自测

这一节把最容易出错的地方集中拿出来复盘，都是我或者周围朋友真实踩过的坑。构造题不怕想不到，最怕的是想了个"差不多对"的方案就直接交，结果挂在边界上。

5.1 最常见的错误构造：奇数长度用了单个分隔符

设 n = 2m+1，很多人会写：

s = 'a'*m + 'b' + 'a'*m

这个长度正确，p = q = m，但 p+q = 2m 是偶数。验证 n=5：得到 "aabaa"，子串 'a' 出现 4 次，偶数，WA。问题出在哪？两段等长时，a 的总数被均分，子串 'a' 的出现次数是 2m，而 2m 永远偶数。所以在奇数长度下，两段 a 块绝对不能等长。

对比错误和正确方案：

从表格能直观看到：只要两段 a 串一样长，子串 'a' 的次数必为偶数。把墙从单字符变成双字符、并把右段减掉一个 a，问题立刻解决。这个错误极其经典，我估计提交这道题的人里有一大半都挂在它上面。

5.2 边界与实现细节的坑

第二个高频坑是 n=1。如果没特判，奇数分支会构造出 "bc" 甚至直接崩溃。第三个坑是输出格式：多组用例时最后一个字符串后面少换行，这类题对输出格式很敏感，少换行在某些判题机上会被判 WA。第四个坑是 C++ 里写 ans = m * 'a' 之类的表达式，这会把字符的 ASCII 码乘上 m，得到的是一个整数而不是字符串；必须写 string(m, 'a')。这些都属于语法层面的低级失误，但对拍或者编译一次就能发现。

5.3 暴力 checker：五分钟写个自测程序

构造题最怕的不是想不到，而是想到了却不敢确信。我的习惯是写个小暴力验证器，把所有小 n 跑一遍，心里有底再提交。checker 的思路极其简单：生成所有子串，用哈希表统计每个子串出现次数，检查是否全部为奇数。

from collections import Counter def ok(s: str) -> bool: cnt = Counter(s[i:j] for i in range(len(s)) for j in range(i + 1, len(s) + 1)) return all(v % 2 == 1 for v in cnt.values()) def construct(n: int) -> str: if n == 1: return "a" m = n // 2 if n % 2 == 0: return 'a' * m + 'b' + 'a' * (m - 1) return 'a' * m + 'bc' + 'a' * (m - 1) for n in range(1, 30): s = construct(n) assert len(s) == n and ok(s), (n, s) print("all small n passed")

这个程序对 n 到 30 以内的构造做了全量验证。n 再大的话暴力枚举子串是 O(n^3) 级别，没必要；公式证明已经齐了。但"先写 checker 再提交"这个习惯我一直推荐，尤其是构造题，它能帮你快速发现 5.1 那种"长度对但性质错"的隐蔽问题。

5.4 构造题验证的通用习惯

除了写 checker，另一个有效的办法是做一些"扰动实验"：把 a 块长度微调、把墙字母换成其他字母、把左右块交换，再用 checker 验证。这样做能让你对"哪些参数是必须的、哪些是自由的"有更直观的理解。比如你会很快发现，墙字母只要互不相同且不是 'a'，换成 x、y 也没问题；但墙字母相同就必挂，两段 a 等长就必挂。这种扰动式的思考方式，比单纯背一个结论有用得多。

6. 从这题能带走的通用套路

CF1554D 本身已经讲完了，但"构造一个满足奇怪子串条件的字符串"这类问题，在 CF 里隔三差五就会出现一次。最后分享几个我从中提炼的通用方法论，都是我后来做题反复用到的。

6.1 "唯一低频字符当墙"是一个高频范式

很多字符串构造题的核心矛盾是：有些子串天然难控制，比如连续相同字符形成的长串。这时候引入一个在整个字符串里只出现一次（或频率极低）的字符，把难搞的区域隔开，就能让所有"穿墙"的子串瞬间变成安全状态。这个范式不止出现在 Diane 里，很多涉及子串计数、子串是否出现、子串频次奇偶性的题目都靠这一招破局。学会它，至少能让你在面对同类题时有一个正确的起步方向。

6.2 看到"出现次数为奇数"就想到模 2

奇偶性问题的标准动作，是把计数写成关于长度的表达式，然后整体对 2 取模，把所有偶数项扔掉。这题里 (p-L+1)+(q-L+1) 中那一大坨 -2L+2 直接消失，剩下 p+q 独立决定一切。做题卡住时，试着把计数公式写成关于长度的多项式再模 2，经常会有"原来如此"的瞬间。奇偶性过滤是一个非常廉价的探路工具，成本只有一张草稿纸。

6.3 字符串构造题的做题顺序

我自己总结的三步流程：

1. 先看长度最小的子串能从必要条件里推出什么。比如单字符出现次数必须奇数次，整串长度和字符频次奇偶数量之间还有隐藏约束。
2. 挑出"最难搞"的那类子串，设计隔离方案，让其他子串自动安全。
3. 验证边界（n=1、全同字符、最短反例），再用暴力 checker 兜底。

这套顺序帮我解决过好几道 Div2 D 和 Div2 E 的字符串构造题，不敢说万能，但至少能让你不再对着题面发呆。尤其是第一步，很多人一上来就想"怎么构造出所有子串都满足条件的串"，这太难了；反过来从必要条件入手，反而很快能圈定候选结构。

最后说点个人体会。我做这题时一开始也走偏了，想着用后缀自动机去数子串出现次数，然后反向构造——后来意识到这完全是方向性错误，构造题要的是充分条件，不是把条件精确算出来。把"只出现一次的字符会自动搞定一切包含它的子串"这个观察写下来之后，五分钟就写出了 AC 代码。之后我遇到类似的"所有子串都要满足某种奇怪性质"的构造题，都会先问自己三个问题：哪些子串是天生安全的？哪些子串是最难控制的？我能不能用低频字符把它们隔开？这套想法帮我解决了不少同类题目，希望也能帮到你。