——泛音堂《破晓将至》
每次看到时之歌 Project 觉得惋惜。
这场 CF 是没有 tester 吗?。
1B 写了 2h，下考 5min 内调完，破防了。
406 HDU6358 Innocence
场上做法太复杂没写完，下面是一种好写的做法（令 \(B=30\) 为位数）：
我们将 \([l,r]\) 内的数表示成若干个 trie 上的子树，即一些固定的前缀与任意的后缀。
考虑 \(n\) 个 trie 上的子树异或出 \(k\) 的方案数，不妨考虑 \(n=2\)，两个子树限定的前缀分别是 \(s,t\)，那么能异或出 \(k\) 的条件是 \(s,t\) 不冲突且较短的一个前缀能与 \(k\) 匹配，方案数是 \(2^{B-\max(|S|,|T|)}\)。
推广到任意 \(n\) 的情况就是这些子树互不冲突，最短的前缀能与 \(j\) 匹配，方案数是 \(2\) 的（后缀大小之和减去最长后缀长度）次方。
我们枚举最长后缀长度，注意到此时合法的前缀只有至多 \(4\) 种，于是我们可以状压状态，做异或 FWT 快速幂。
复杂度 \(O(qB)\)。
407 CF1261F Xor-Set / P3791 普通数学题
做法类似的两道题。
第一题：
在 trie 上表示出所有区间，如果暴力枚举 A 与 B 种的区间合并可以得到 \(O(n^2\log^2)\) 个区间。计算区间并还要多一个 \(\log\)，不能通过。
注意到只需找同层区间合并，少一个 \(\log\)，可以通过。
第二题：
表述出区间，暴力枚举区间合并，只需计算区间约数个数和，容易发现记忆化后只有 \(O(\log)\) 组询问，复杂度 \(O(\sqrt n\log n)\)。
408 HDU6423 Rikka with Bubble Sort
场上没想到分块，只会 \(O(q^2\log n)\)。
考虑只有全局修改的情况。
刻画一轮冒泡排序的过程：取出所有前缀最大值，从前往后考虑每个位置，将其平移到下一个前缀最大值之前，此时有一些非前缀最大值会变成前缀最大值，将其更新。
注意到如果忽略每次操作的平移，一个位置只会变成前缀最大值所在位置而不会从前缀最大值位置变成非前缀最大值位置。于是可以使用两棵线段树维护前缀最大值的值与位置，根据单调性其一定按顺序一一匹配。找到新增的前缀最大值可以求出反序表 \(t_i\)，第 \(i\) 个位置会在 \(t_i\) 时刻变为前缀最大值。因此我们能做到 \(O((n+q)\log n)\)。
询问分块，每次将值域分成 \(O(块内询问数量)\) 个块，每个块需要支持的是：维护首尾元素以及块内总和，进行一轮冒泡排序，将第一个数变大，将最后一个数变小。
查询最后一个数之前一定有一次冒泡排序，因此最后一个数一定为块内最大值。类似地，假设进行了 \(t\) 轮冒泡排序，容易发现第一个数是 \([1,t+1]\) 的最小值，两者都可以使用堆维护。
进行冒泡排序同样维护一个位移量，修改首尾元素直接在堆内加入删除元素。
由于我们需要维护出每个块在当前询问块结束后的形态，所以我们必须谨慎地考虑修改对最终形态的影响（因为我们只能维护询问块开始时的形态，不能维护每个时刻）：
- 修改第一个元素：在修改之后会立即进行一轮冒泡排序，因此对反序表的影响仍然是全局减一，因此我们可以直接将数组对应位置修改。
- 修改最后一个元素：这一操作一定在一次冒泡排序后，我们给原来的最大值位置打上删除标记，并在位置 \(len+t\) 插入新的元素（\(t\) 为冒泡排序轮数）。若一次冒泡排序后没有进行这种操作，我们也在序列尾端（即位置 \(len+t\)）增加一个被删除的元素，重构块时将所有被删除的元素看作 inf 统计反序表。这样处理的原因是新添的位置并没有进行全部 \(t\) 次冒泡排序，添加缓冲才能正确维护反序表。
注意特殊处理块长为 \(1\) 的情况，复杂度 \(O(n\sqrt q\log n)\)。
409 牛客挑战赛 69 D coin
考察前缀和序列，我们关注的信息事实上只有当前前缀和比前缀最小值大多少，比前缀最大值少多少，令 \(f_{i,j}\) 为两个值分别为 \(i,j\) 时的胜率，我们所求即 \(f_{0,0}\)。
边界条件 \(f_{0,n}=0,f_{n,0}=1\)，递推式：
为了更形象地刻画递推，我们单独提取一条对角线 \(i+j=t\) 按照 \(i\) 从小到大排列，并在左右分别加上 \(f_{0,t+1},f_{t+1,0}\)，其满足 \(a_i=pa_{i+1}+(1-p)a_{i-1}\)，根据 P3750 [六省联考 2017] 分手是祝愿 的经验，我们作差分，得到 \(b_i=\frac{pb_{i-1}}{1-p}\)，记 \(C=\frac{p}{1-p}\)，于是我们可以只关注 \(i=0\) 或 \(j=0\) 的 \(f\)。
上面的递推式可以导出：
令 \(g_i=f_{i,0}-f_{0,i}\)，容易得到：
有边界 \(g_n=1\)，于是：
注意到 \(f_{0,0}=\sum_t f_{0,t}-f_{0,t+1}\)，我们带入上面的式子：
已经可以计算，不过还能进一步化简：
410 HDU74011 被EI加0了
不会 ei 的推法啊，搞不明白 e^x 求导积分的一些组合意义，参考了 PYWBKTDA 的推法。
\(k\) 的限制显然没用，我们只需枚举一共使用了多少种颜色。前缀最大值/后缀最小值的限制考虑使用插入法生成排列，我们容斥不合法值的一个子序列，系数为 \((-1)^l\)。
我们钦定一个值不合法需要令其出现至少两次，一次在结尾出现，第一次出现的位置前面不再插入数字，所以令 \(f_{t,i,j}\) 表示恰好 \(t\) 种值，前面 \(i\) 个空隙不能插入数字，一共有 \(i+j\) 个数的容斥系数之和，那么转移是：
列出 \(f\) 的二元生成函数，\(F(x,y)\)，其中在 \(x\) 上是 OGF，\(y\) 上是 EGF，使用归纳法可知所有 \(F_i(x,y)\) 均能表示成 \(\sum g_{i,j}x^ie^{jy}\) 的形式。
第一种转移就是 \((e^y-1)F_i\rightarrow F_{i+1}\)，第二种转移不妨对于每个 \(x^ie^{yj}\) 分别考虑贡献：
（第二行换元 \(u=k-t+s,v=k-t\)）
故我们能做到 \(O(1)\) 转移，复杂度 \(O(n^3+Tn)\)。
411 P8368 [LNOI2022] 串
哈哈，不会做，是不是没救了。
一个显然的 \(\lfloor\frac n2\rfloor\) 策略是从 \(s_1\) 开始每次往后走两步。
把子串用区间描述，跳一步即长度加一且 begin pos+1，我们还能任意移动到相同子串的区间。
注意到若一个子串出现两次，一定可以从空串移动到它，具体地我们可以从后往前构造，每次跳到前面的出现位置就移动到后面去，因此步数一定能消耗完。
我们考察最后一次移动相同子串操作对应的串区间 \([l,r]\)，其后面只能用开头说的策略跳 \(\lfloor\frac {n-r}2\rfloor\) 步，根据上面的结论前面的步数也一定能达到上界 \(r-l+1\)，因此其贡献容易计算。
只需建 SAM，复杂度 \(O(n|\Sigma|)\)。
412 ABC280H Substring Sort
太久没碰 SAM 啥都不会了。
在 DAWG 上求解 k 小子串处理多组询问较为麻烦，需要 DAG 剖分。事实上我们可以在后缀树上类似地处理这一问题（回忆后缀树的定义，其可以看作字符串所有后缀的压缩 trie）。
类似 trie 上，我们贪心遍历后缀树即可得到字典序顺序，每个结点对应的串数量也容易计算。可以直接二分定位到对应结点，也可以离线处理询问少一个 \(\log\)（本题不需要排序）。
413 ABC306H Balance Scale
为啥我不会啊？？？？？？？？？？？？？？？？
有经典的定向为 DAG 计数模型：容斥一个度数为 \(0\) 的子集 \(S\)，系数是 \((-1)^{|S|}\)。
本题若确定了 = 的边，我们将这些边缩起来做 DAG 计数就好了。因此我们枚举一个度数为 \(0\) 的子集，每个子集内的边都必须填 =，容斥系数就是这些边缩起来的连通块数量加一。
复杂度 \(O(3^n)\)，当然可以集合幂级数 exp 做到 \(O(2^nn^2)\)。