338 loj#6296. 迷失的字符串
粘一个之前写的题解。
考虑一个串时的做法，令 \(f_{x,i}\) 为是否存在一条从 \(x\) 出发并进入 \(x\) 子树的路径为以 \(i\) 结束的前缀，\(g_{x,i}\) 为是否能匹配以 \(i\) 开始的后缀，转移为：
\[f_{x,i}\leftarrow\or_{y\in son(x)} (f(y,i-1)\and [(x,y)=s_i])\\ g_{x,i}\leftarrow\or_{y\in son(x)} (g(y,i+1)\and [(x,y)=s_i]) \]可以使用 bitset 优化至 \(O(\frac{n|S|}{\omega})\)，多个串只需拼接在一起做上述算法，复杂度一样。
再说一个 \(O(n\sqrt n)\) 的做法。
对原树进行点分治，对当前点分治到的子树大小进行根号分治：
若子树大小小于 \(B\)，那么我们在询问串的 trie 上暴力标记这些串，复杂度 \(O(nB+\sum|S|)\)。
若子树大小大于 \(B\)，我们可知这样的点不超过 \(\frac{n}{B}+\frac{n}{2B}+\cdots=O(\frac{n}{B})\) 个，我们预处理分治中心到每个位置的字符串存到哈希表里，然后枚举分支中心处于每个询问串的位置查一遍哈希表即可，复杂度 \(O(\frac{n}{B}\sum|S|)\)。
总复杂度 \(O(n\sqrt n)\)。（令 \(n,\sum|S|\) 同阶）
339 P9248 [集训队互测 2018] 完美的集合
不知道为啥要有前面的包装。
完美集合的处理无非钦定一个在完美集合里的点并做 dfs 序上的背包，并使用点减边容斥来修正贡献的计算。
重点在计算：
\[{n\choose k}\bmod 5^{23} \]类似 exLucas，我们把问题转化成求 \(g(n)\)（表示 \(n!\) 中 \(5\) 的出现次数）以及 \(f(n)=\frac{n!}{5^{g(n)}}\)。
重点在后面的计算，我们记 \(F_n(x)=\prod_{i=1}^n(k+i)^{[i\perp 5]}\)（所求即 \(F_n(0)\)），有如下事实：
\[F_{10n}(0)=F_{5n}(0)F_{5n}(5n) \]注意到若展开 \(F_{5n}(x)\)，我们仅需维护多项式的前 \(23\) 次项。
于是我们每次通过手动乘 \(O(1)\) 个单项式转化为求 \(F_{10n}(0)\)，再使用上述方法递归求解即可。
340 P9247 [集训队互测 2018] 完美的队列
还不会。
2023 Hubei Provincial Collegiate Programming Contest，打一半打雀去了，A 与 D 没写。
341 D Darkness II
显然只需维护长方形之间的合并，也就是做插入/删除矩形，以及查询一个与给定矩形有交的矩形编号。
对 \(x\) 维建立线段树，\(x\) 维交的限制可以用类似 P7312 [COCI2018-2019#2] Sunčanje 使用线段树处理。
对 \(y\) 维扫描线，矩形按照 \(y\) 左端点顺序插入进线段树，每个线段树结点维护一个有序区间集合，注意每次插入都是 pushback，合并是类似单调栈的，复杂度 \(O(n\log n)\)。
342 E Inverse Counting Path
首先有一个 \(2\log V\) 的构造：二进制分解，构造一些 \(2\times 2\) 的小正方形依次摆放使得到第 \(i\) 个正方形的右下角方案数为 \(2^i\)，然后引一些路径到边缘，最后顺着边缘走下来。
二进制由于需要衔接小正方形，会造成一些冗余，考虑使用 \(3\times 3\) 的小正方形，左上角与右下角重合，使用六进制进行构造即可。六进制表示需要乘一个 \([1,5]\) 内的系数，在汇入边缘的位置进行一些处理即可。
343 G Guess the Polynomial
\江莉/
对着官方题解复读一下。
经典地使用倍增，我们假设已经得知 \(A=F(x)\bmod x^n\)，想要推出 \(B=F(x)\bmod x^{2n}\)。
也就是将 \([x^i]A(x)\) 的系数拆成 \([x^i]B(x)\) 与 \([x^{n+i}]B(x)\)，注意到系数总和不超过 \(998244353\)，\(B\) 中非零的位置一定对应 \(A\) 中非零的位置，于是我们只需维护多项式非零位置。
多项式忽略掉某项贡献不好做，我们尝试通过配系数求出 \(C_k=[x^k]B(x)-[x^{n+k}]B(x)\)，使用单位根反演的技巧能得到（这里我想了下，感觉能直接单位根反演提取 \([x^k]\) 系数，目前还不知道为啥要按照题解的这个做法）：
\[[x^k]B(x)-[x^{n+k}]B(x)=\frac 1n\sum_{i=0}^{n-1}f(\omega_n^i\omega_{2n})\omega_n^{-ik}\omega_{2n}^{-k} \]可以列出：
\[\begin{bmatrix}\omega_n^{0\cdot 0}&\omega_n^{0\cdot 1}&\cdots&\omega_n^{0\cdot(n-1)}\\\omega_n^{1\cdot 0}&\omega_n^{1\cdot 1}&\cdots\omega_n^{1\cdot(n-1)}\\\vdots&\vdots&\ddots&\vdots\\\omega_n^{(n-1)\cdot 0}&\omega_n^{(n-1)\cdot 1}&\cdots&\omega_n^{(n-1)\cdot(n-1)}\end{bmatrix}\times\begin{bmatrix}C_0\omega_{2n}^0\\C_1\omega_{2n}^1\\\vdots\\C_{n-1}\omega_{2n}^{n-1}\end{bmatrix}=\begin{bmatrix}f(\omega_n^0\omega_{2n})\\f(\omega_n^1\omega_{2n})\\\vdots\\f(\omega_n^{n-1}\omega_{2n})\end{bmatrix} \]该运算明显可以保留所有有值的
344 L Game
别急。
345 CFgym102412B Alexey the Sage of The Six Paths
假设度数序列不变应该如何处理，此时代价固定，只需判定是否有解。
假设最小的最大匹配为 \(L\)，最大的最大匹配为 \(R\)，我们断言能构造出所有 \([L,R]\) 内的最大匹配大小，构造很简单，任取两个度数非零的非匹配点 \(a,b\)，取出其连向的任意两个匹配点 \(u,v\)，拆掉 \((a,u),(b,v)\) 连上 \((a,b),(u,v)\) 即可。
\(R\) 好求，左右两部非零点贪心连一下即可，重点在如何求 \(L\)。
使用 Hall 定理，最大匹配大小为 \(|X|+\min_{S\subseteq X}(|N(S)|-|S|)\)（\(X\) 为左部点集合），也就是找到一个 \(X\) 的子集满足 \(|X|+|N(S)|-|S|\) 最小。我们枚举 \(N(S)\)，只需找到连边都在其内部的最大 \(|S|\)，那么其只要求 \(S\) 度数和小于等于枚举的集合，可以 dp 记录左右部点集合大小，子集和进行判定。
如果度数序列不固定，我们考虑对度数序列进行 dp 的过程中记录上面的子集信息，设计一个 dp 求出数组 \(g_{i,j,k}\) 表示左部钦定了 \(i\) 个点，钦定度数和为 \(j\)，有 \(c\) 个非零度数点，然后枚举两边信息 \(O(n^6)\) 合并即可。
346 CFgym102412C Steel Ball Run
带权重心一定是 dfs 序带权中点的祖先，倍增判定是否合法即可，复杂度 \(O(n\log^2 n)\)。
347 CFgym102412D The Jump from Height of Self-importance to Height of IQ Level
shift 操作要求我们使用平衡树维护，考虑怎么合并信息。
题意就是要求不存在一个点既不是前缀最小值，又不是后缀最大值，我们对于一个区间维护最小值 \(mn\)，最大值 \(mx\)，非前缀最小值的最小值 \(mx\)，非后缀最大值的最大值 \(smx\)。
若左区间 \(mn\) 小于右区间 \(smx\)，或是左区间 \(smn\) 小于右区间 \(mx\)，则不合法。考虑怎么合并 \(smn\)，此时由于合法，左区间 \(smn\) 大于右区间 \(mx\)，于是合并后的值要么从原来的 \(smn\) 贡献而来，要么等于右区间内大于左区间 \(mn\) 的最大值，这个可以类似楼房重建线段树进行二分。
复杂度 \(O(n\log^2 n)\)。
348 CFgym102412E Minimums on the Edges
赋予权值组合意义，对于所有权值 \(x\)，取出权值大于等于 \(x\) 的子集。也就是我们要取出若干互相包含的子集，所有子集大小和为 \(s\)，权值是每个子集导出子图边数和，可以直接 dp 做到 \(O(2^nns)\)。
事实上可以发现，我们忽略子集互相包含限制求出的答案仍然正确，因为若答案存在两个不包含的集合 \(A,B\)，将其替换为 \(A\cup B,A\cap B\) 不劣，于是每个子集大小求出权值最大子集即可，复杂度 \(O(2^nn+ns)\)。
349 CFgym102412L Yet Another Mex Problem
dp，移动右端点维护所有左端点对应的 mex 值，这是经典的颜色段均摊，不过那题我好像也没有记录，所以还是写一下！
加入一个数 \(x\) 时，我们找到 mex 为 \(x\) 的左端点连续段，我们需要分裂这个连续段，并进行 \(O(1)\) 次连续段合并。问题变为快速找到 \([l,r]\) 内的分裂位置，我们从右到左处理分裂，每次找到最小的，权值大于之前 mex 且最后一次出现位置在 \(r\) 前的某一权值（使用线段树二分），若其最后一次出现位置 \(\geqslant l\)，我们就分裂一个新段并将 \(r\) 赋为这个位置继续做。
我们直接使用线段树维护凸包即可做到 \(O(n\log^2 n)\) 的复杂度。
1log 做法还不会。
350 CF1787H Codeforces Scoreboard
容易转化为分配一个排列，最小化 \(\sum\min(k_i p_i,c_i)\) 之和，最小化 \(\min\) 可以变为钦定哪些题目选择第一种，于是选择了的题目一定按照 \(k_i\) 降序依次选择 \(1,2,\cdots,t\)：
\[f_{i,j}=\min(f_{i-1,j}+c_i,f_{i-1,j-1}+k_ij) \]我们不加证明地给出两个结论：（证明可见 ez_lcw 的题解）
- 假设钦定 \(i\) 个题目的最优方案为 \(S_i\)，存在一组 \(S_{0,1,\cdots,n}\) 使得 \(S_0\subseteq S_1\subseteq\cdots\subseteq S_n\)。
- \((f_{i,j+1}-f_{i,j})-(f_{i,j}-f_{i,j-1})\geqslant k_i\)。
使用 slope trick 维护差分值，根据上面的结论，更新一定是一段前缀使用 \(+c_i\)，一段后缀使用 \(+k_ij\)。使用平衡树维护差分值，修改即插入以及后缀加，复杂度 \(O(n\log n)\)。
351 HDU6973 Bookshop
树剖将问题变为 \(\log\) 条重链区间的模拟，离线对重链扫描线，我们要维护的事实上是：
- 插入/删除某个询问；
- 处理一个结点的影响，即将 \(\geqslant x\) 的值减去 \(x\)。
使用平衡树维护权值，将值域分为三个部分 \([0,x-1],[x,2x],[2x+1,\infty]\)，第一三部分的内部顺序不改变，第二部分可以暴力取出并插入，类似倍增分块的势能分析可知复杂度 \(O(n\log n\log V)\)。
351 BZOJ2567 篱笆
先考虑链的情况，二分答案 \(mid\)，考虑判定：
令 \(x_i\) 为第 \(i\) 个篱笆最后的位置，那么能列出不等式：
\[a_i-mid\leqslant x_i\leqslant a_i+mid\\ x_i-x_{i-1}\leqslant 2r\\ x_0=-r,x_{n+1}=L+r\]我们将所有 \(x_i\) 的限制替换为 \(a_i\)，于是可以变换为（特判掉 \(x_1,x_n\) 与边界的限制，其限制很好刻画）：
\[\forall_{i<j}a_j-mid\leqslant a_i+mid+2r(j-i) \]注意到满足该条件一定可以构造出一组合法的 \(x\)，于是其同样是一个形如 \(mid\geqslant C\) 的限制。
注意到 \(i\geqslant j\) 一定不优，所以我们可以拆贡献，\(C\) 的计算无非两个最值相减。
环的处理只需倍长，复杂度线性或一个 \(\log\)。
标签：log,cdot,复杂度,53,子集,2023,弥留之际,omega,2n From： https://www.cnblogs.com/xiaoziyao/p/17352943.html