A. Did We Get Everything Covered?
给定 \(n,k\) 和一个长度为 \(m\) 的字符串 \(s\)，你需要判断所有长度为 \(n\)，由前 \(k\) 种小写字母组成的字符串是否都是 \(s\) 的子序列。如果不是则构造一组反例。多测。\(n,k \leq 26\)，\(m \leq 1000\)，\(\sum n,\sum m \leq {10}^6\)。2s / 250M。
维护每个字符第一次出现的位置，每次选取最远的那个即可。
D. Balanced Subsequences
给定 \(n,m,k\)，求出所有左括号数量为 \(n\)，右括号数量为 \(m\) 的括号序列中，最长合法括号子序列长度恰为 \(2k\) 的括号序列数量。\(n,m,k \leq 2000\)。1s / 250M。
答案一定形如在 ))))((((( 的空隙中插入若干个合法括号序列。并且这些合法括号序列的总长度为 \(2k\)。直接拿卡特兰数的 OGF 算即可。当然，也可以用路径计数算。
F. Anti-Proxy Attendance
有 \(n\) 个学生，位置为 \(1 \sim n\)，其中有一个学生缺席。你可以向交互库询问，每次询问你需要给定两个参数 \(l, r\)，代表你询问的区间是 \([l, r]\)，交互库会告诉你该区间内是否有人缺席。不幸的是，交互库会说谎。但是，交互库不会连续三次说谎，也不会连续三次说真话。你需要在 \(\lceil \log_{1.116} n \rceil - 1\) 次询问内确定两个位置，有其中一个位置的学生缺席则被视为正确。 \(n \leq {10}^5\)。2s / 250M。
对于每个位置，维护一个字符集为 \(\{\tt0,\tt1\}\) 的字符串 \(S\)，\(\tt0\) 表示在此次询问中这个位置不可能缺席，\(\tt1\) 表示可能。维护 \(S\) 的过程中，我们相信交互库说的是真话。
由于交互库不可能连续说三次真话或者谎话，所以如果 \(S\) 中出现 \(\tt000\) 或者 \(\tt111\)，那么这个位置就肯定不可能缺席，我们称之为“锁定”，我们的目标是找到尽可能多的这样的位置。
接下来，考虑势能分析法。先考虑每个位置的势能，钦定锁定后势能为 \(0\)，对于未锁定的位置，我们只分析 \(S\) 结尾的两个字符，势能如下表：
| \(\tt00\) | \(\tt01\) | \(\tt10\) | \(\tt11\) |
|---|---|---|---|
| \(1\) | \(x\) | \(x\) | \(1\) |
考虑之后添加字符造成的影响：
| \(\tt00\) | \(\tt01\) | \(\tt10\) | \(\tt11\) | |
|---|---|---|---|---|
| 添加 \(\tt0\) | \(0\) | \(x\) | \(1\) | \(x\) |
| 添加 \(\tt1\) | \(x\) | \(1\) | \(x\) | \(0\) |
设 \(e_0\) 为添加 \(\tt0\) 后的势能，\(e_1\) 为添加 \(\tt1\) 后的势能，\(e\) 为原先的势能。考虑势能的变化量，即 \(\frac{e_0 + e_1}{e}\)，有下表：
| \(\tt00\) | \(\tt01\) | \(\tt10\) | \(\tt11\) | |
|---|---|---|---|---|
| \(\frac{e_0 + e_1}{e}\) | \(x\) | \(\frac{x + 1}{x}\) | \(\frac{x + 1}{x}\) | \(x\) |
为了方便分析，我们希望每种情况的势能变化量都相同，即 \(x = \frac{x + 1}{x}\)，即 \(x = \frac{\sqrt{5} + 1}{2}\)。为了方便，下文中，我们记 \(\varphi = x = \frac{\sqrt{5} + 1}{2}\)。
根据上文，我们发现有 \(e_0 + e_1 = \varphi e\)。将情况拓展到所有位置，设 \(E_0\) 为交互库回答区间内无人缺席时总势能，\(E_1\) 为有人缺席时总势能，\(E\) 为原来的势能。那么显然有 \(E_0 + E_1 = \varphi E\)。考虑最坏情况，下一步的势能显然是取 \(E_0\) 和 \(E_1\) 中较大者。如果我们能让 \(E_0\) 和 \(E_1\) 尽可能接近，那么我们每次询问后势能大概都会变为原先的 \(\frac{\varphi}{2}\) 倍。最开始询问一次 \([1,n]\) 和 \([1, \lfloor \frac{n}{2} \rfloor]\)，那么最初势能大概就是 \(\frac{\varphi+1}{2} n\)，而最终势能是 \(2 \varphi\)，所以总共操作次数大概就是 \(\log_{\frac{2}{\varphi}} n\)，肯定是符合题目要求的。
每次构造只需要 \(E_0\) 和 \(E_1\) 尽可能接近即可。我们询问时只考虑询问前缀，最接近的位置即为 \(E_0\) 和 \(E_1\) 两条曲线的交点，所以取离交点最近的整数位置即可。