省选后做题记录

· · 个人记录

记录一下的原因是主要是防止自己太颓了，就算口胡也要多做题。

3.20

正式回归的 day 1，whk 好难/ll

CF1019E Raining season

秒了的 *3200，我真的有这个水平吗？但是想到分治是不是就完了？

这个直线最值想到凸包，凸包的合并就是闵可夫斯基和，所以可以合并链。

直接边分治，然后两边的函数跑凸包，然后就是闵可夫斯基和了，最后求得的凸包再取 \max 一下。

直线凸包其实是半平面交，是不是要对偶一下才能转化为凸包？

等会去学，准备写写。

这个把半平面 y\leq kx+b 全部转成 (k,b) 然后跑下凸壳就行了。

时间大概 O(n\log ^2n )。

CF1179E Alesya and Discrete Math

刚从 whk 回来的我会 *3200 的交互，真的假的？

首先有个简单的 O(n\log n\log L) 的分治做法，就是每次找到所有 f_{i}(x)=\frac{L\lfloor\frac{n}{2}\rfloor}{n} 的位置，然后按 x 的大小分成两组，变成了子问题递归下去即可，显然过不去，不然可能 *3200？

瓶颈在于每次都对所有数求出 = 某个值的端点，剩下的就是找到中位数然后比大小分成两部分。

注意如果到先用 O(\log V) 次求出某个 f_i(x)=p 的 x，可以 O(1) 比较它和另一个 f_t(x)=p 的 x 的大小。

用我们 O(n) nth_element 的随机思想，每次随机一个作为基准数比大小，把函数列分成两部分，然后递归找下去，期望比较的次数是 O(n) 的。

然后期望寻找基准数的次数是 O(\log n) 次的，这样一共是 \sum_{i}\log len_i\log L 的，分治树就是一颗线段树，去 【UNR #5】诡异操作看看知道这个复杂度实际是 O(n\log L) 的，实际上手算一下满二叉树就知道了。

于是就得到了一个期望 O(n\log n+n\log L) 的做法，实际上允许的操作上界要大一些所以不怕我们脸黑。

CF117E Tree or not Tree

没看是基环树这辈子有了。

考虑一颗树的话就是链取反操作。

基环树的话可能会经过环的一段，这一段可以简单讨论一下得到。

考虑点边容斥：连通块数量=点数-边数。

对于树的时候只用数亮的边的数量了，对于基环树如果环没有全亮的话依旧是一颗树，否则整个环缩成一个点还是一颗树。

所以需要做的是区间取反区间 1 的数量，非常容易，对每个去掉环后的子树树剖，然后和环一起线段树维护即可。

CF1261F Xor-Set

生成方式计数的话，考虑一个数有一种怎样的唯一表示？这个暂时不知道。

类似数位 DP，可以写成 O(n\log V) 段前缀固定，后缀任意的区间。

两两异或是不是也能得到前缀固定，后缀任意的数目。两两异或得到 O(n^2\log ^2 V) 个区间，只是要去重。

实际上貌似是过不去的，因为常数挺大，而且去重怎么可能小常数 O(1)。

注意到其实数位 DP 区间就是线段树上区间查询的节点，所以我们两个不同的节点其实只关心深度小的那个，所以只用在同一层异或即可，这样区间是 O(n^2\log V) 的，去重一下即可。

去重有个简单方法是扔进 trie 但是空间爆炸，但是值域区间只有包含或不交，直接 set 即可。

反正能过。

CF1268D Invertation in Tournament

图论结论题。

考虑兰道定理，对于强联通竞赛图，按出度升序排序，我们要让前 k\in [1,n-1] 个点的出度和 >\binom{k}{2}。

首先某个引理：对于强联通竞赛图，对每个点每个 [3,n] 的长度都存在经过该点该长度的环。

这指出 n >3 的 n 阶强联通竞赛图，存在 n-1 阶强联通子图。

有两个观察：

假设原图不是 SCC，一共存在 t 个强联通分量。

  1. 只要有存在一个 SCC 大小至少为 4，那么可以翻转一个点，此时原 SCC 依旧是 SCC，其他点被还入环内，变成了强联通图。
  2. 如果 t>2，找到不是开头或结尾的 SCC 任意点翻转，此时左右两边都一起划入环中。

然后要特判的只有 t=2,\forall i,\{scc_i\}\subseteq \{1,3\} 的图，随便暴力暴力就行了。

否则直接先判是否 SCC，不是就枚举每个点翻转后是否 SCC，用兰道定理轻松 O(n^2)。

3.21

我是口胡王。

P5400 [CTS2019] 随机立方体

一眼容斥。

设 N=nml，钦定 i 个极大点，剩下 X=N-(n-i)(m-i)(l-i) 个点的方案就是 N^{\underline X}，然后选长宽高的方案自然就是 {n}^{\underline i}{m}^{\underline i}{l}^{\underline i}。

剩下就是钦定点位置的方案数，发现能按大小关系画出一颗叶向树，所以可以计数拓扑序，注意只有 i 个点子树大小不为 1，直接找到，而且注意可以递推。

钦定至少 i 个极大点的方案就是：

g(i)=N^{\underline {N-(n-i)(m-i)(l-i)}}{n}^{\underline i}{m}^{\underline i}{l}^{\underline i} (N-(n-i)(m-i)(l-i))!\times\prod\limits_{j=1}^{i}\frac{1}{N-(n-j)(m-j)(l-j)}

概率就是除以 N!，就变成了 g(i)={n}^{\underline i}{m}^{\underline i}{l}^{\underline i}\prod\limits_{j=1}^{i}\frac{1}{N-(n-j)(m-j)(l-j)}。

但是我们要求 \min(n,m,l) 个数的逆元，离线求一下即可，答案二项式反演一下即可。

这个 k\leq 100 是在？

CF1386C Joker/P6684 [BalticOI 2020] 小丑 (Day1)

就是删掉一个区间的边看图是不是二分图。

但是可以直接使用莫队，直接用带权并查集就能判断。

不想撤销的话可以写回滚莫队，注意每次需要撤销的只有 O(B) 个点，直接对 O(B) 个点操作的时候改过的点暴力改回去即可。

注意到我们不能像山体滑坡一样只关心连通性，所以不能使用第二并查集的方法？

但是是均摊的，不对，还是有 \log。

其实用拓展域并查集就只维护连通性了，这样就没 \log 了。

可以变成区间连边，实际上，对于每个 l，其合法的右端点 r 不降，然后就是 P7843 「C.E.L.U-03」布尔，然后回滚决策单调性分治做完了。

为啥没一眼注意单调性？ 不是哥们这不评黑？ ### CF1609F Interesting Sections 一眼题。 分治一下，左右有 $(mx,pmx,mn,pmn)$。 比如求 $mx_l<mx_r,mn_l>mn_r,pmx_r=pmn_r$ 一类的对数，是一车二维数点？ 但是注意有单调性，可以双指针。 都在一侧的话是一个前缀，分居两侧的话是前后缀交的一段区间，都能双指针，统计无脑的。 可以做到 $O(n\log n)$，貌似 __builtin_popcountll 很快？ ### CF1787H Codeforces Scoreboard 被 DS 弄得有点烦，换 DP 玩玩，结果还是 DS。 选择顺序有点难搞。 没有 $\max $ 就按 $k$ 降序选，如果取了显然这个点在尽量后面取最好。 所以考虑设 $f_{i,j}$ 表示前 $i$ 个数，当前没被取 $\max$ 有 $j$ 个的最大权值，则： $$ f_{i,j}=\max f_{i-1,j}+a_{i},f_{i-1,j-1}+b_{i}-j\times k_i $$ 直觉告诉我们这是凸的，所以考虑 slope trick 维护。 差分一下，设 $g_{i,j}=f_{i,j}-f_{i-1,j}$，则： $$ \begin{aligned} \sum_{k=1}^{j} g_{i,k}&= \max \sum\limits_{k=1}^{j} g_{i-1,k}+a_i,\sum\limits_{k=1}^{j-1}g_{i-1,k}+b_{i}-j\times k_i \end{aligned} $$ 注意每次两边值的 $\Delta$ 分别是 $g_{i-1,j}$ 和 $g_{i-1,j-1}-k_{i}$，因为是个上凸函数，所以 $g_{i,j}$ 是单减的，但是还是不好比 $g_{i-1,j}$ 和 $g_{i-1,j-1}-k$ 的大小。 直觉上上凸函数取 $\max$ 还是上凸我们想只有一个交点，而且 $f_{i,i}$ 只能从 $f_{i-1,i-1}$ 转移过来。 大胆猜想：前一段取 $\sum\limits_{k=1}^{j} g_{i-1,k}+a_i$，后一段取 $\sum\limits_{k=1}^{j-1} g_{i-1,k}+b_{i}-j\times k_i$，即 $g_{i-1,j-1}-k\geq g_{i-1,j}$。 其实是对的，使用我们的数学归纳法即可~~（不如说猜结论然后证明）~~。 不管了，我是 OIer 不是 MOer。 于是可以二分找到这个点，我们维护差分数组，则我们的操作有：区间加，插入一个数，用平衡树即可。 ### CF793F Julia the snail 用你喜欢的 DS 维护。 离线对答案扫描线，因为 $r$ 不重，可以此时查询。 每次 $(l_i,r_i)$ 就是把 $(l_i,n)$ 中答案 $\geq l_i$ 的点对 $r$ 取 $\max$，吉司机即可。 ### Gym102920L Two Buildings 枚举右端点的话，考虑一个枝的减，自然另一边只会是严格前缀最大值，注意到其实右端点也只会是后缀最大值，于是只用保留一个单峰序列。 注意到一边端点增大的时候，对于长度的依赖会增大，可能更大的长度比更大的左端点好。 所以感谢理解右端点递增的时候最优左端点也是不降的，直接决策单调性分治即可。 严格证明的话考虑推进左端点的答案变化： $$ \Delta=(i-j+\delta_j)(h_j+h_i-\delta_h)-(i-j)(h_i+h_j)=\delta_{j}(h_{i}+h_{j})-\delta_h(i-j+\delta j) $$ 注意到当 $h$ 增大 $i$ 减小的时候 $\Delta$ 在增大，所以最优左端点也在减少。 ### P6776 [NOI2020] 超现实树 超越人脑？ 首先你需要：根没有左子树的，根没有右子树的，如果单点就直接做完了。 特殊性质的话？ 链：把可被其他生成的去掉后，并除了叶子都是和根都是三度点。 想了想发现：如果 $\mathcal T_x$ 根的两个子树都有点，那这个树有用当且仅当某一个子树是个单点。 否则你可以构造一个这个子树不同的非空子树，另一颗子树为任意二叉树，这样 $\mathcal T_x$ 得不到这类树，能造出这种树的 $\mathcal T_y$ 一定能造出 $\mathcal T_x$，所以 $\mathcal T_x$ 是无用的。 所以我们有四种树： 1. 根没有左子树； 2. 根没有右子树； 3. 根左子树为单点； 4. 根右子树为单点； 都能到子问题，都需要合法。 子问题可以看做四叉树，终止条件是这有个单点。 时间显然是线性的。 ## 3.24/3.25 作业好多银牌和铜牌题，还是很吃力/kel 懒得分辨哪天写的，就放一起了。 ### [AGC005E] Sugigma: The Showdown *3276，但是博弈论。 如果 A 能在 $(u,v)$ 反复跳当且仅当 $u,v$ 在 B 中距离 $>2$，此时答案 `-1`。 否则第一步如果不会马上结束的话 A 会从 $x$ 走到某个 $u$ 但 $Y$ 走不到，此时一定 B 从 $Y$ 能走到 $v$ 下一步能同时到 $X$ 和 $u$。 然后如果不会一步结束而且答案不是 `-1` 就只有 $u$ 走到另一个 $u'$，此时 $v$ 能走到 B 树中的 $u$ 而且 B 树中 $u$ 也能到 $v$。 发现是子树内的子问题，直接递归下去。 ### [AGC007E] Shik and Travel *3906，感觉稍微评高了点。 注意到恰好两次的限制意味着每次走完一颗子树必须走另外一边的子树。 考虑此时有两条合并的链和两条上下的链，如果二分答案一下只用关系新的两条上下的链即可。 令这种数对 $(a,b)$ 满足 $a\leq b$，则去掉包含后只有 $a$ 单增 $b$ 单减的序列。 每次合并子树的时候枚举一边，对于每个 $(a,b)$ 贪心选合并合法的同时另一个最小的。 暴力做 DSU 是 $O(n\log^2n\log V)$，但是跑得还挺快。 两个序列还能归并去重，$O(n\log n\log V)$。 ### [AGC008F] Black Radius *3995，这是真的银，太难想了。 考虑一个部分分，全是 $1$。 某些邻域 $C(u,d)$ 可能有不同的表示法，此时一定有某个子树深度 $maxd_{v}\leq d$，假设邻域不是整颗树。 > 想一会再补。 ### [AGC009C] Division into Two *2437，最清新的一集。 先浅浅排个序，然后套路 DP，一个在 $i$ 一个在 $j$ 的方案数，记录一下是谁在 $i$。 $$ f_{i,j,0/1}\to f_{i+1,j,0/1}(a_{i+1}-a_{i}\geq T_{0/1}),f_{i,j,0/1}\to f_{i+1,i,1/0} (a_{i+1}-a_{j}\geq T_{1,0}) $$ 随便线段树优化。 然后你发现前面是清零一段前缀，后面的操作是一段单调的后缀和，直接做到线性。 ### [AGC012E] Camel and Oases *3490，之前看过，怎么回忆做法的时候糖丸了。 只有 $\log V$ 次跳跃，每次都是把能走的走了，然后再装满水然后跳跃。 然后就是 $\log V$ 层的树，每一层都选一个，制定第一层选的情况下问可不可行。 你可以直接状压，但是这是 $O(nV)$ 的，注意第一层最多考虑的只有 $O(\log V)$ 个树， 这样状态是 $\sum \log V\times 2^{\log V-i}=V\log V$ 的。 转移需要无交合并，但是其实不用子集卷积。 又不需要合并子树，直接枚举前后缀覆盖即可，就是覆此时选了的状态数为 $S$ 能覆盖的最大最小前缀，第一层是有 $\log V$ 个区间，于是还是 $O(V\log V)$ 的。 ### [AGC012F] Prefix Median 问号题，不过远古了现在应该要低一点，好像之前在一类 DP 题中看见过这道。 生成答案，一般找充要刻画条件或者寻找一种唯一的刻画方式。 给 $a$ 排序，注意删数中位数比加好想，因为 $b_{n}$ 固定的是 $a_{n}$。 然后中位数删两个只会不变、左移一个、右移一个，而且 $b_{i}\in [a_{i},a_{2n-i}]$。 需要找个充要条件，注意到每次已知左移、右移、不变后两段就有若干不知道删了什么的操作，然后不连续跳 就怎么说呢，你每次从 $b_{i}\to b_{i-1}$ 的时候一定不会在值域**开**区间中经过 $b_{j}<i$ 因为都删完了，所以是一个左右横跳的样子。 所以我们得到了一个充要条件：$b_{i} \in a_{i\sim 2n-i},\forall j<i<n,b_{j\notin (\min (b_i,b_{i+1}),\max (b_{i,b_{i+1}}))}$。 除了当前所在点之外，左右各有一段无法到达，不算重的话我们需要某些存在相同数的位置是一定无法到达的。 直接设 $f_{i,l,r}$ 表示已经跳了 $i$ 次，左右分别有 $l,r$ 个数还能到达的方案数，枚举左右走，减少几个即可，每次更新要看看左右两个是否可以走。 直接转移是 $O(n^4)$ 的，注意我们的转移形如 $f_{i,l,r}\to f_{i,l+dl-x,r+dr+1}/f_{i,l+dl+1,r+dr-x}$，容易前缀和优化到 $O(n^3)$。 ### [ARC104F] Visibility Sequence *3213，比较简单。 直接枚举最大值所有位置，然后就是子问题。 于是 $f_{l,r,v}$ 表示当前考虑 $[l,r]$ 的最大值为 $\leq v$ 的方案数，则 $f_{l,r,v}=\sum f_{l,k-1,\min (a_k,v)}\times f_{k+1,r,\min (a_k,v)-1}$。 值域有点大，其实差分后可以对 $cnt$ 取 $\min$，这样就是 $O(n)$ 的，其实对 $n$ 取 $\min$ 就行了。 $O(n^4)$，不会有人写拉插吧，怎么我一开始看 DP 式子以为是拉插。 ### [ARC089F] ColoringBalls *3782，银牌题太困难了/ll 怎么检验一个局面合法，特别的，直接先把颜色段缩成单点，最后用组合数缩回去。 注意蓝色的可以被红色重新分开。 我们的小球序列是 `wrbrbw…wrbrbrwrw` 这样的。 我们认为所有的非白小球段都是 `rbr……rbr` 或者 `r` 形状的，这样对于存在 `b` 的连续段，我们认为其两边的 `r` 实际个数是 $\geq 0$，其余所有 `r` 或 `b` 实际个数都是 $>0$ 的，然后非两端点的 `w` 个数 $>0$ 否则 $\geq 0$。 于是就是经典问题，有若干未知数，每个满足 $\geq t_i$，问其和为 $n$ 的方案数，插板简单计算。 考虑我们操作： 1. 加入一个蓝色球，此时要么不变，要么序列 `r` 和 `b` 都多一个， 2. 加入一个红色球，要么不变，要么 `w` 和 `r` 多一个，要么 `r` 和 `b` 多一个。 我们要知道最后有几个只有一个 `r` 的段和其他段有几个，除了每段第一个 `r` 和 第一个 `b` 之外都正好会新增两个字符。 考虑唯一表示，枚举有 $i$ 个同时有 `r` 和 `b` 的段和 $j$ 个只有一个 `r` 的段，贪心地想肯定是前 $i$ 个 `r` 当这些段第一个，靠前的 `b` 去匹配。 然后知道剩下的红和蓝只能给某些段贡献，然后这些红蓝等价的不用管颜色，如果我们知道放了 $T$ 个，一定是倒着的要去贡献。 直接 DP 一下设 $f_{i,j,k}$ 表示从多到少划分了 $i$ 段，放了 $j$ 个棋子，后面的棋子数量一定 $\leq k$ 的方案数。 则 $\binom{i}{l}f_{i-l,j-kl,k<t}\to f_{i,j,t}$，容易前缀和优化到 $O(n^3\log n)$，一共是 $O(n^5\log n)$ 但是常数很小。 需要在枚举 $l$ 的时候顺便判断每一段都是否合法。 离正解思路差了个直接枚举某些段数的个数，看来这种不好确定的东西直接枚举也是个不错的策略。 ### [ARC186E] Missing Subsequence *3178，但是脑子糊了。 啊啊啊？这什么限制条件啊？ 主播主播，你的 DP 确实很厉害，但还是太考验手法了，有没有简单又强势的方法推荐一下。有的兄弟，有的有的，后面忘了，反正 GF 太赖了。 先不管 $b$ 的限制，就直接求包含所有 $m^k$ 的子序列的数组，可以把序列分成 $k$ 段，每一段末尾是最后一个没出现的数，前面恰好出现了其他所有的数，长 $l$ 的方案是 $m[\frac{x^{l-1}}{(l-1)!}](e^x-1)^{m-1}=m{l-1\brace m-1} $，大概是若干段这个的 OGF 卷起来然后再卷另一个 GF，能 $O(n\log n)$。 现在考虑这个不能出现某个子序列的限制，所有的数还是都能分成 $m$ 段，倒着看，最后一段不能有 $a_m$，后面第 $i\in [1,m-1]$ 段不能在 $a_{i+1}$ 之前有 $a_{i}$。 最后一段不能有 $a_{m}$，就是正好 $m-1$ 种数，方案为 ${l\brace m-1}$。 剩下的讨论一下： 1. $a_{i}=a_{i+1}$，等价于 $a_{i}$ 只能选一个。 要么是最后一个数方案 ${l-1\brace m-1}$，要么就正好选个位置 $m{l-1\brace m-1}\to (m-1)(l-1){l-2\brace m-2}$。 2. 否则不相等，所有 $a_{i}$ 在 $a_{i-1}$ 后面。 还是如果 $a_{i}$ 正好是最后一个数，此时答案 ${l-1\brace m-1}$。 考虑这两个数钦定位置的话就的 EGF 就是 $\langle 0,1,2,3,4,\ldots,\rangle=ze^z$，其他数的 EGF 是 $e^z-1$，最后还是求 $(m-2)[\frac{x^{l-1}}{(l-1)!}]ze^z(e^x-1)^{m-2}$。 上面直接把两种情况的 GF 加一起就行了。 反正就是这样至多三种不同的 GF 的幂次卷起来，直接暴力模拟卷积是 $O(n^2)\sim O(n^3)$，良心模数 $998244353$ 随便 NTT 一下就 $O(n\log n)$ 了。 ### AT_nomura2020_f Sorting Game 注意到恰好一位不同的只能换一点。 ---- ## 一大车懒得统计哪天了 ### CF232E Quick Tortoise 尝试分治一下，然后就是看看两边能否到达中间某个节点，不弱于 DAG 可达性，于是我们就用 bitset 来维护，这样是 $T(nm)=2T(\frac{nm}{2})+O(\frac{n^2m^2}{w})=O(\frac{n^2m^2}{w})$ 的，然后查询就是 $O(\sqrt {nm})$ 的。 这样查询太慢了过不去。 换一下记录每个位置能到达哪些中间位置，这样是 $O(\frac{nm\sqrt {nm}}{w})$ 的，此时询问降到单次 $O(\frac{\sqrt{nm}}{w})$ 了。 ### 3.31 ### P10219 [省选联考 2024] 虫洞 主播主播，你的 DP 确实很强大，但是还是太考验手法了，有没有简单又快速的方法？有的兄弟，有的有的，后面忘了，我们 GF 可是能做到单 $\log$ 而且复杂度和 $k$ 无关的。 限制 $1,2,3$ 就说明每种颜色的边都是一个置换，就是若干个环组成。 然后是最为神秘的限制 $4$，其他题解有详细的证明，我才疏学浅，就不在这里乱胡了。 结论： 1. 一个弱连通块所有颜色的环大小相等，而且一个弱连通块每一个点都是等价的。 2. 考虑任意两种颜色，第一种颜色形成若干环，第二种颜色只会在等长的环之间连边。 拓展到多个就是任意颜色都只会在本质相同的弱连通块之间连边。 所以每次新加颜色就可以看做合并若干等价类，合并 $x$ 个大小为 $y$ 的等价类有 $y$ 种本质不同的合并方式，每一种的方案数都是 $(x-1)!y^{x-1}$。 假设当前有 $x$ 个大小为 $y$ 的等价类，你每一波变成了新的子问题的时候，假设你合并了 $c_{i,j}$ 个大小 $i\times y$ 的第 $j$ 种块，此时的方案数系数为： $$ \frac{x!}{\prod\limits_{i\geq 1}\prod\limits_{j=1}^{i} c_{i,j}!(i!)^{c_{i,j}}}\times\prod\limits_{i\geq 1}\prod\limits_{j=1}^{i}((i-1)!y^{i-1})^{c_{i,j}}=\frac{x!y^{x}}{\prod\limits_{i\geq 1}\prod\limits_{j=1}^{i}c_{i,j}!(yi)^{c_{i,j}}} $$ 那个 $x!y^x$ 有相同的形式，然后 $y$ 和 $yi$ 又正好是连通块大小，所以考虑以下 GF，$y$ 指刻画的等价类的大小： $$ H_{y}(z)=\sum\limits_{i\geq 0}\frac{a_i z^{yi}}{y^ii!} $$ 如果你考虑设 $ H_{t,y}(z)$ 表示当前操作了 $t$ 次，当前等价类大小为 $$，y关于每个数量 $z$ 最后的答案的上述形式 GF，你会发现有： $$ H_{t,y}(z)=\prod\limits_{i\geq 1}H^{y}_{t+1,iy}(z) $$ 特殊的我们知道边界条件 $H_{k,y}(z)=\sum\limits_{i\geq 0} \frac{z^{iy}}{y^ii!}=e^{\frac {z^y}{y}}$。 用一点组合计数技巧可以得到 $H_{k,yw}(z)$ 对 $H_{0,y}(z)$ 的贡献为（设 $w$ 的因数分解为 $\prod p_i^{a_i}$）： $val_{w}=\prod\limits_{i}[z^k]\prod\limits_{j=0}^{a_i}\frac{1}{1-p_i^jz}=\prod\limits_{i}{k+a_i\brack a_i}_{p_i}$ 次。（${k+a_i\brack a_i}_{p_i}$ 是 q-组合数，实际上就是 $\frac{\prod\limits_{j=k+1}^{k+a_{i}} (1-p_i^j)}{\prod\limits_{j=1}^{a_i}(1-p_i^j)}$，可以总共 $O(n\log _{n}mod)$ 预处理所有 $p$ 的幂次的答案，瓶颈在于对于所有 $p$ 算 $p^{k}$） 所以你可以知道 $H_{0,y}(z)=e^{y^{k}\large \sum\limits_{i\geq 1}val_{i}\times \frac{z^{iy}}{iy}} $，对于每个 $val_i$ 的贡献，可以用线性筛筛出，于是你可以用一次多项式 exp 得到答案，我们对于一开始有 $x_0$ 个 $y_0$ 大小的连通块，答案为 $[\frac{z^{x_0y_0}}{y_0^{x_0}x_0!}]H_{0,y_0}(z)$。 判同构你可以依次加入每种边，加入一种边之前一定还有若干联通分量，然后一种边的形态只和走多少步回到当前连通块以及回到位置的差异有关，可以记录下每种的颜色对应状态，这样可以通过哈希 $O(nm)$ 得到每种连通块数量和大小。 于是我们得到了 $O(n(m+\log n+\log_{n}mod))$ 的做法，和 $k$ 大小无关而且 $\log_n mod$ 实际上很小可以看做常数，所以很快。 ### [ARC142E] Pairing Wizards 不要把特殊问题一般化。 要么你自己 $\geq b_x$ 要么有关系的 $\geq b_x$，你自己肯定 $\geq a_i

所以 (T,(x,i),1),((x,i),(x,i-1),\inf) 表示选 i\geq a_x 的时候的代价。

限制 (x,y) 就是 (S,x,\max(0,b_x-a_x)) 表示自己满足限制，然后 (x,(y,\max (0,b_x-a_y)),\inf) 表示 y 来满足。

然后就是最小割了，时间 O(dinic(nV+m,nV+m))。

[ARC176E] Max Vector

就是 X_{i}\geq A_{i,j} 或者 Y_{i}\geq A_{i,j}，反着连一下。

[ARC125F] Tree Degree Subset Sum

直觉告诉我对于每个 y 答案是个区间，至于为什么只有直觉你别管。

然后就只用求表示出每种东西的最多最少个数。

然后注意到度数和为 2n-2，然后就只有 O(\sqrt n) 种了，直接单调队列优化一下，时间 O(n\sqrt n)。

二进制分组有点像暴风雪的复杂度分析，也是 O(n\sqrt n) 的。

直觉上先全部 -1，设 0 的个数为 c，然后考虑证 R_i-x\leq L_i+x+1\to R_{i}-L_{i}\leq 2x+1。

证明的话就是直接考虑任意集合 v-cnt 的话就是在 [-x,x-2] 之间。

[ARC125E] Snack

能建出一个图，答案是最大流，但是肯定过不了。

模拟最大流一般转最小割这样不存在没流满边的考虑，每个人要么自己满了，要么能拿的都拿了。

考虑最小割会划分两侧，答案为：

\sum\limits_{i=1}^{n} [l_i\in T] a_i+\sum\limits_{j=1}^{m}b_{j}[r_j\in T]\sum\limits_{i=1}^{n}[l_i\in S]+\sum\limits_{j=1}^{m}c_j[r_j\in S]

枚举 \sum\limits_{i=1}^{n}[l_i\in S]=cnt，然后发现就是 \sum\limits_{j=1}^{m}c_{j}+[r_{j}\in T](b_{j}\times cnt-c_j)+\sum\limits_{i=1}^{n}[l_{i}\in T]a_{i}。

想要最大，就把最小的 cnt 个 a_i 划分进 S，然后第一个和式就是 \sum\limits_{j=1}^{m}\max(c_j,b_j\times cnt)，于是就是按 \frac{c_{j}}{b_j} 的大小来即可，可以均摊移动，瓶颈在排序。

这个写出式子枚举某个的取值不就是之前在霸树的某次的形式吗？这都不会……

CF1416F Showing Off

还是要补了。

首先考虑以下观察：

所以可以对网格图黑白染色，环相当于是一个匹配。

假设找到了匹配，然后呢？剩下的就随便连向一个小于自己的位置，然后就行了？

注意有些点周围不存在小于自己的位置，分讨一下：

  1. 如果全部大于自己，直接 -1 走人；
  2. 否则必须成为匹配的点。

于是在合法的时候，就是存在若干必须匹配的点，此时二分图还有一个匹配。

于是就是一个上下界网络流，还是二分图的形式，于是复杂度是 O(nm\sqrt {nm}) 的。

AT_cf16_exhibition_final_e Water Distribution

首先 \max 的限制没用因为你肯定不会这样过去。

---- ### P4223 期望逆序对 怎么能没有经典老题，思想很有用。 考虑一对数 $(A,B)$，其他数出现的概率是均等的，讨论 $AB,BA,CB,BC,AC,CA,CC$ 七种位置状态的变化，矩阵快速幂一下。 构造得到的矩阵是： $$ \begin{bmatrix} \binom{n-2}{2}&1&n-2&0&n-2&0&0\\ 1&\binom{n-2}{2}&0&n-2&0&n-2&0\\ 1&0&\binom{n-2}{2}+(n-3)&1&0&1&n-3\\ 0&1&1&\binom{n-2}{2}+(n-3)&1&0&n-3\\ 1&0&0&1&\binom{n-2}{2}+(n-3)&1&n-3\\ 0&1&1&0&1&\binom{n-2}{2}+(n-3)&n-3\\ 0&0&1&1&1&1&\binom{n}{2}-4 \end{bmatrix} $$ 剩下每种对数的贡献和顺序对，逆序对之类的有关，可以直接求一求。 $AB,BA$ 和逆序对数量有关。 $CA,CB,BC,AC$ 和每个数大小有关。 $CC$ 均匀的，概率 $\frac{1}{2}$。 感觉去年 SCOI d2t1 能不能类似思想啊？感觉不是很行主要是数好像有 $100$ 个状态是不是很多了？不对不关心顺序压缩一下状态，是不是思想一样的啊。 有个 AT 的题很像，是不是看过 hanghang 的题解？ ### P5540 [BalkanOI 2011] timeismoney/最小乘积生成树 这个 trick 都没见过，汗流浃背了。 两维值域在 $[1,V]$ 的整点的凸包点数上界 $O(V^{\frac{2}{3}})$，然后这题两维和看做点对，答案就在凸包上边。 然后考虑分治找凸包，先求出 $y,x$ 最大的点 $A,B$，然后开始分治，每次找 $S_{\triangle ABC}$ 最大的点，此时 $\overline{AB} \times \overline{AC}$ 最小的，用叉乘考虑就是：$(x_{B}-x_{A})(y_{C}-y_{A})-(x_{C}-x_{A})(y_{B}-y_{A})$ 最小的点。 注意到其实就是 $(x_B-x_A)y_C+(y_A-y_B)x_C$ 最小，直接让第一维权值乘上 $y_A-y_B$，第二维乘上 $x_B-x_A$，然后就是一维的权值了。 时间 $O((na)^{\frac{2}{3}}m\log m)$，本题貌似 $O(n^{\frac{8}{3}}a^{\frac{2}{3}})$ 的 prim 要快一点。 ### P3236 [HNOI2014] 画框 一样的，只是 MST 换 KM，不会 KM 怎么办，原始对偶复杂度也是对的只是常数大亿点。 时间 $O(Tn^3\times (na)^{\frac{2}{3}})=O(Tn^{\frac{11}{3}}a^{\frac{2}{3}})$。 ### P10175 「OICon-02」Subtree Value 很有启发性的题。 两种做法： 1. 考虑 $x^{\underline{pk}}\bmod p^k=0\to F(x)\equiv F(x)\bmod x^{\underline{pk}}\pmod {p^k}$，所以答案可以保留为 $pk-1$ 次多项式，于是只用对每种大小的连通块求 $x=1\sim pk$ 的点值然后还原回去，最后 CRT。 2. $\prod(a_i+x)$ 可以写成 $\prod(Ux+y+a_i)$ 的形式，$y$ 只和 $x\bmod U$ 有关，$Ux$ 的话只会选最多 $V-1$ 个。 于是对每个 $|S|\bmod U$ 直接枚举后 DP，只用关心当前连通块大小对 $U$ 取模后的值，然后再枚举选了 $V$ 个未知数。 就设 $f_{i,j,k,l}$ 表示以 $u$ 子树为根，当前选了 $j$ 个点，系数选了 $k$ 次 $Ux$，钦定的 $|S|\bmod U=l$ 的权值之和，然后带入算就完了。 前者更优，思想来自今年论文集，于是今天愚人节的 T3 可以秒了。 ### U548164 牢帽 考虑做法 1，直接维护点值模质数幂，于是就可以还原多项式然后代入 $x$ 求，先把 $U^V$ 分解了，设 $C=\sum p_ik_i$。 加删边，修改点权，可以询问分块，询问之前先把 $O(B)$ 个修改结算了。 合并的时候可以只维护 $C$ 个点值的乘积，然后考虑怎么不带 $\log$ 维护连通性，使用第二层并查集即可，这样只用修改 $O(B)$ 个点顺便直接覆盖不用撤销。 这样复杂度是 $O(qBC+\frac{n^2}{B})=O(n\sqrt{qC})$ 的，注意到 $C$ 顶天不会超过 $28$。 但是还是不够快，直接分块改成线段树分治就行了，这样就是 $O(n\log^2n+n\log nC)$。 ### P4218 [CTSC2010] 珠宝商 感觉题目形式很经典，就是树上所有路径子串在一个模式串的 $occ$ 之和。 首先无脑套个点/边分治，然后两个串拼起来怎么搞，这个 SA 不用想。 我们既然是拼起来，就可以枚举断点，在前后看分别能匹配多少串，这样保底有个 $O(m)$ 的枚举。。 所以根号分治一下，$<B$ 的分治位置就直接暴力 $O(nB)$，否则是 $O(\frac{mn}{B}+B)$ 的，最后大概是 $O(n\sqrt m)$ 加一车玩意。 小串部分定位子串的话直接枚举一个点在 SAM 上跑就均摊线性了，不用定位，SA 又又又又被薄纱了。 回忆 SAM 怎么写 ing。 ### P7361 「JZOI-1」拜神 子串最长的子串满足在这个子串中至少出现了两次。 在后缀树上预处理一下最靠近的两个点，就是支配对。 然后二分答案一下，就变成求一个区间内的最大支配对，这可以对 $l$ 扫描线，然后查询 $l\leq L,R\leq r$ 的支配对 $[L,R]$ 的最大值，可以线段树实现。 在线做法就直接记录每种长度的 $nxt$ 就好了，然后就是主席树上查询区间最小值。 反正两个 $\log$ 的。 ### P8368 [LNOI2022] 串 有个 $\lfloor\frac{n}{2}\rfloor$ 的构造就是开始空串，$l=0,r=-1$，然后每次 $l\to l+1,r\to r+2$。 猜想最优解一定从 $\epsilon$ 出发但是正着不好想，反着变成删。 考虑一个 $[l,r]$ 没法变空串的话一定有：$l<r-l+1$，如果存在和 $[l,r]$ 一样的串 $[L,R]$ 满足 $L>l$ 分讨一下： 1. $L>r$ 这样无交，一定能缩成空串； 2. 否则还是缩减，然后注意到在 $L$ 变成 $l$ 之前会成为 $[l,r]$ 的子串，此时这个对应了一个 $[L,R]$ 的一个后面的子串，于是又可以往后跑。 于是只要存在 $[l,r]$ 有相同的串，就能消到空串，然后一定是从能消的最大的串开始消到 $[l,r]$，于是这样一个 $[l,r]$ 的答案为： $$ (r-l+1)+\lfloor\frac{n-r}{2}\rfloor $$ 最后记得对 $\lfloor\frac{n}{2}\rfloor$ 取 $\max$。 直接 SA 一下，就是在排序后相邻的位置找答案，贡献为：$height_i+\lfloor\frac{n-\min(sa_{i-1},sa_{i})-height_i+1}{2}\rfloor$。 ### 23P6029 [JSOI2010] 旅行 有黑我倒立洗头。 交换 $k$ 次边，如果最短路径距离 $\leq k$ 就做完了。 否则距离的边数 $\geq k$，此时一定不会操作边权前 $ k$ 小的边，剩下的就是前面的边权。 直接设 $f_{i,j,t}$ 表示走到了 $i$，当前动用了 $i$ 次交换，走过了 $t$ 个前 $k$ 小的边，剩下边的最短距离，然后就是简单图上 DP 了。 时间复杂度 $O(k^2m\log mk^2)$。 ### CF1037H Security 哪里复杂度带 $|\Sigma|$ 了，不要乱搞好不好？ 字典序贪心往 SA 想是好的，子串匹配往 SAM 上想是好的。这题既然可以离线就先把询问串也连一起跑 SA。 贪心是一定的，就是让 LCP 尽量长，然后再跟一个大的字符，直接枚举，然后可以定位区间，在这个区间内看看有没有 $[l,r]$ 的子串，可以用主席树。 然后就是暴力枚举了哈，按 LCP 倒着枚举找到区间，然后再二分找到区间，接着就是找到里面 $[l,r-LCP]$ 这个区间的后缀中字典序大于询问串的最小子串，直接主席树维护后缀区间最小值即可。 直接就是 $O(n\log n)$ 的，强制在线就多个 $\log$ 定位子串。 ### CF1063F String Journey 显然 $k$ 有个上界是 $O(\sqrt n)$，而且此时长度一定是 $1\sim k$。 有一个简单根号做法是正着 DP，每个串下一个位置显然只会转移到最近的减一子串处，用哈希处理一下即可。 直接设 $f_{i,j}$ 表示倒数第 $i$ 个位置，此时以 $i$ 开头长 $j$ 的串能否加进去，此时一定合法的 $j$ 是一个前缀，所以暂时只用记录最大合法的 $j$ 了。 你的转移有两种： $$ \min (f_{i},LCP(suf_i,suf_j))+1\to f_{j-1},\min (f_{i},LCP(suf_i,suf_j))+1\to f_{j} $$ 第一种转移可以从 $f_{i}$ 打个标记延时转移到 $f_{i-1}$，所以只用考虑转移给第二种的。 在后缀树上 LCP 就是子树深度，所以直接链分治一下，对轻链其他子树取 $\min$，其他点过来的时候也可以查询一下，这样是两个 $\log$，考虑优化。 首先对 $f_{i}$ 取 $\min$ ，发挥效果的 $f_{i}$ 可以看做是对一个子树操作，然后剩下的就只和祖先的点自己有关了，于是你知道了显然每个点只会触发一次，于是你就在树剖的时候在前缀暴力弹没出发的点把它触发了，此时发现也可以看作子树取 $\max$。 于是就是单 $\log$ 了，一个观察是 $f_{i+1}\geq f_{i}-1$，就是下一个最多比你大 $1$，否则你可以和它一样的后缀，然后有个常数小更好写的单 $\log$ 做法，就是均摊枚举串，查询区间内最大值的最大位置，单点修改，简简单单。 ### CF1340F Nastya and CBS 著名题目了。 如何分治判断括号序列？首先不断消除相邻的匹配括号，最后删空的就是合法括号序列。 一个区间最后合并完剩下了一段右括号连着一段左括号，合并的时候左边的左括号和右边的右括号要恰好消完。 怎么判断消没消完？就是分治下去匹配，类似线段树单侧递归，不过这个是双侧递归吧…… 就每次一边不合法就跳过，否则递归左边区间，每次右边剩的右括号都要消，此时右区间要递归凑左括号。 区间查询也是同理，递归回去。 时间复杂度 $O(n\log^2 n)$。 还有分块做法。 ### CF757F Team Rocket Rises Again 等价于从 $s$ 出发的最短路，考虑最短路 DAG。 然后就是删掉一个点使得最多点不联通，考虑 DAG 支配树，等价于找一个除了 $s$ 以外子树大小最大的点即可。 ### P10176 「OICon-02」Native Faith 一眼数据分治。 1. 首先 $|s_k|\leq B$ 的话就枚举断点然后求和，可以离线一下。 预处理每个前后缀在其他串出现的数量，这可以 AC 自动机，然后求一个区间内的串的子串出现次数。 区间出现次数可以差分成前缀和相减，每次求子树内点的数量和，等价于单点修改区间求和，修改只有 $m$ 次但是询问有 $O(qB)$ 次，用分块平衡到 $O(m\sqrt m+qB)$。 2. 否则 $s_k$ 的数量不多只有 $O(\frac{n}{B})$ 个，考虑对每个串单独考虑。 从上个询问回来，如果分割分位置有一边长度 $\leq B$ 可以直接套用上边的做法。 否则考虑这一定是某两个 $O(\frac{n}{B})$ 中的大串拼一起的，直接 $O(\frac{n^3}{B^2})$ 得到每个三元组贡献。 平衡一下是 $O(n^\frac{5}{3})$ 的。 ### [AGC027E] ABBreviate 一类题，生成答案，要么考虑唯一构造或者某种充要条件刻画。 首先一个看做 $1$，一个看做 $2$ 的话，和模 $3$ 不变的。 一段合并为一个字符，考虑怎么合并，发现只要不是 `ababab` 或者 `bababa` 都能合并到一个字符。 于是找到最近的包含两个相同的位置或者长度为 $1$ 的同余位置即可 那些平均 3000+ 的网络流就不是人做的。 ### P9726 [EC Final 2022] Magic 只和颜色段数有关，每个断点处能成为一段的充要条件是两侧端点对应颜色段大于覆盖这个位置的所有段。 无交区间是不影响的，然后包含区间自然小的后选不劣。 所以只有两段单增的区间有影响，此时大的的左端断点和小的的右端断点只能选一个，这是一个最大独立集的问题，主要是证明是二分图。其实你发现没有环，所以是对的。 二分图最大独立集=点数-最大匹配，所以求最大匹配就行了。 直接暴力连边空间是不够的，除非匈牙利+bitset，更权威的做法是 $l_i$ 向所有 $r_{j}\in [l_i,r_i],l_{j}<l_i$ 的 $r_j$ 连边，用主席树就好了，这样边数 $n\log n$，也不用担心空间爆炸，确定是哪一边的话看作为 $l$ 还是 $r$。 ### CF704D Captain America 那个数量差可以写成某个子集内某一种的数量不能超过一个值。 关键是两种属性很难绷，等价的肯定尽量涂便宜的那个。 先全部涂成贵的，然后某个横纵的点有便宜的流量限制 $[l,r]$，然后一个点能给两边当流量匹配，于是 $(S,i,[l,r])$ 表示一行，$(j,T,[l,r])$ 表示一列，$(i,j,[0,1])$ 表示一个点的贡献，求一个上下界最大流。 大概是 $O(m\sqrt m)$ 的？反正是个玄学的能过复杂度了。 ### P2304 [NOI2015] 小园丁与老司机 第一问可以直接 DP，对于每个点，先在斜线和竖线方向更新，然后再横线方向前后扫两遍。 输出方案就记录决策点转移即可。 最后一问要注意同一行不超过 $1000$ 颗树，这是关键？没啥用。 我们很快就知道哪些斜线是可能转移的位置，然后都要扫了，因为横线不可达，可以建出一个DAG，然后是最小链覆盖，直接上下界网络流**清理雪道**。 ### UVA1104 芯片难题 Chips Challenge 先不管 $\frac{A}{B}$ 那个限制，怎么保证行列数量相等，然后呢就是某行选的和某列选的相差若干，然后矩阵若干位置不能选。 然后选完后选的边一定构成若干环，环的表示就是**P6061 [加油武汉] 疫情调查**，然后某些是必选边就钦定下界变成上下界网络流即可。 然后 $\frac{A}{B}$ 的限制的话就是枚举每行列的上届再看选到的数量能不能支持上界即可，可以二分一下。 大概是 $O(n\times Flow(n^2))=O(n^5)$，但是常数小到起飞。 ### P8215 [THUPC 2022 初赛] 分组作业 既然不好直接搞选择状态和合作的关系，直接暴力枚举四种状态选不选，限制就有选一种其他都不能选，但是又有必须选一个的限制，于是再加上每个人的选择状态，于是六种状态相互约束，一定有选的？ ### CF235D Graph Game 怎么都没有低于 $O(n^2)$ 的做法。 认为的同一颗树是指的把环断开后的若干颗树，根为环上的那个点。 先想想都在同一颗树的部分： 考虑点对的贡献，那一个点 $u$ 做点分治的时候 $v$ 如果在子树内说明 $(u,v)$ 路径上的点都在 $u$ 的后面，概率就是 $\frac{1}{dis(u,v)}$，实际上直接点分治+FFT 就能做到 $O(n\log^2 n)$ 了。 然后是不在同一颗树的贡献，此时要考虑到环上不同两条路径的贡献，那至少存在一条 $(u,v)$ 路径使得上面的点顺序都不大于 $u$ 的顺序，有两条路径，直接做不好做，可以考虑容斥，设环上两条路长度为 $x,y$，$(u,v)$ 到自己树根的距离为 $d_u,d_v$，那贡献就是 $\frac{1}{d_u+d_v+x}+\frac{1}{d_u+d_v+y}-\frac{1}{d_u+d_v+x+y}$。 三个式子的话最后一个是容易的因为 $x+y$ 是个定值，所以直接随便卷一下就行了。 前面两个的话考虑断环为链，那么上面两个就正好一个会经过被断的那条边，一个不经过，计算一下不经过的那些的话可以直接分治+FFT计算一下跨过中点的链的贡献，否则就改变一下每个根在环上的距离，依旧可以分治+FFT 做到，反正三个卷积的部分都是 $O(n\log^2 n)$ 的。 但是 FFT 时代的眼泪了，谁爱写谁写，反正 $O(n^2)$ 能过。 感觉仙人掌的复杂度计算是不是也能类似 LOJ 花朵的做法，先建出圆方树，然后重剖一下，对轻子树，可以直接 FFT 算出点对贡献，然后挂到父亲点上面算和重链其他树点对的贡献，对于重链直接先把方点也就是每个环处理了，然后分治 FFT，类似最大子段和处理是否能贴左右边的单向点贡献算一下顺便把容斥系数加上，感觉胡得很对（只是口胡，有错指出一下谢谢），如果这是对的的话是 $O(n\log n\log_{\sqrt 2}n)\sim O(n\log^3n)$ 的，但是不想实现（~~因为忘了 FFT 怎么写了）~~。 ### CF1060F Shrinking Tree 如果某条边到 $u$ 的链上边的操作顺序都比这条边的顺序早的话，这条边有且仅有一种合并方式，否则可以任意合并，在固定根的时候可以直接认为是点的操作顺序，此时这个点的操作顺序是到根点的最大值。 但是我们的问题是怎么知道顺序大小？ ### CF1239E Turtle 考虑调整法，固定下面一行，剩下的想要尽量小肯定是越小越往前面，所以第一行单调不降的，第二行类似的单调不升的。 第二个同样能证明最大值只有两种可能：要么是一开始就拐下去，要么就到最后才拐，这两种也是等价的，证明考虑反证，在中间拐的话交换两列后面的就答案不变但最大就是上面情况了。 第三可以调整得到起点和终点取值一定是前两小的数，还是调整法，于是剩下 $2n-2$ 个数，分成两组使得差的绝对值最小，直接 DP 就好了，时间 $O(\frac{n^3a}{w})$。 ### CF1221G Graph And Numbers $n\leq 40$，应该是什么 meet-in-middle。 假设图是联通图，否则直接乘起来。 容斥一下，算没有边为哪些值。 1. 没有 $1$，说明 $0,1$ 之间没有边，只有全 $0$ 或全 $1

相应的 0,1 和 2,1 和 0,1,2 也是一样的了。

  1. 没有 2 或者没有 1，就是独立集计数，O(n2^\frac{n}{2}) 是弱智，O(2^{\frac{n}{2}}) 可以直接暴力 DP，依次枚举编号最大的点：f_{S-v}+f_{S-v-N(v)}\to f_{S}，然后编号最大改成度数最大就飞快，用哈希表压状态还挺快，好像就是 wjq 的做法？

  2. 没有 1,2，只有二分图。