260512 - 260518
P16433 [APIO 2026 中国赛区] 上升
肯定是考虑从前往后的插入 dp，但是这样插入到前面 \(<pre_i\) 的部分可能会出锅。于是对 \(\le pre_i\) 下面的部分进行插空 dp（不知道排名），对 \(>pre_i\) 的部分进行插入 dp（会改变前面的部分）。走到一个 \(p_i\) 已知的地方需要对上面部分根据 \(p_i\) 的排名乘一个组合数来确定具体的值。时间复杂度 \(O(n^3)\)。
P16435 [APIO 2026 中国赛区] 集宝
首先有显然的贪心策略。然后考虑经过两个相邻的圆会发生什么，如果两个圆不相交，那么显然路径是容易被确定的；否则两个圆相交部分形成一个新圆，容易分析得到我们肯定是要走到两圆的交集上也就是新圆上。于是直接用线段树维护这个，需要支持快速求 \(k\) 级祖先，用倍增重链即可，时间复杂度 \(O(n\log \log n+q\log n\log \log n)\)，不很卡常，正常写能过。
AT_abc313_h [ABC313Ex] Group Photo
充要条件是显然的，计数也是显然的。
CF1844H Multiple of Three Cycles
把链按照长度模 \(3\) 进行分类，首先模 \(3\) 余 \(0\) 的链可以随意插到其他的环上，或者自己成一个环，因此可以乘以一个下降幂转化成没有模 \(3\) 余 \(0\) 的环。
设 \(a\) 个 \(1\) 链，\(b\) 个 \(2\) 链，设 \(f(a,b)\) 表示方案数。考虑找出一些递推式，我们拿出一条 \(1\) 链，分讨它的下一条是 \(1\) 还是 \(2\)；拿出 \(2\) 链同理：
为了便于计算，我们从小往大递推，显然每次我们去掉一条边可能会变为 \((a,b),(a+1,b+1),(a-1,b+2),(a+2,b-1)\)，上面的递推式变为 \(?f(a+1,b+1)=?f(a-1,b+2)+?f(a,b)\) 和 \(?f(a+1,b+1)=?f(a+2,b-1)+?f(a,b)\)，我们记录 \(f(a,b)\) 和 \(f(a+1,b+1)\)，先求出 \(f(a-1,b+2)\)，然后代入第二个式子，可以得到 \(f(a,b+3)\)，从而向前递推。
P6295 有标号 DAG 计数
只需要算出不要求连通的方案数，然后 \(\ln\) 一遍即可。
组合数直接用 EGF 消掉，后面那个连边方案数考虑 \(j(i-j)=\binom{i}{2}-\binom{j}{2}-\binom{i-j}{2}\) 这样就分离了。
CF1515I Phoenix and Diamonds
考虑对重量和容量进行倍增分块，设容量为 \(c\)，所在块为 \([2^{k-1},2^k)\)。如果取了一个当前块的物品，或者有一种 \(<2^{k-1}\) 的物品没有被取完，那么 \(c\) 就会立即下放，我们希望求出所有发生下放的位置。
用线段树维护贪心的顺序，问题转化为快速判断能否在当前区间取走一个重物品，或者是不是不能取走全部的轻物品。我们维护取走一个重物品所需的容量，以及轻物品的容量之和，这是容易判断的。注意取走一个重物品需要把它右边的轻物品都取走。push_up 一次是 \(\log V\) 的。
260514 模拟赛 A 取模吗
有一个正整数 \(a\)，有 \(m\) 次操作，第 \(i\) 次操作你可以选择将 \(a\) 对 \(m-i+1\) 取模或者不操作，让你对 \([0,m)\) 内的所有数求出最终得到该数的方案数。
\(m\le a\le 2\times 10^5\)
余数可以按照 \(\lfloor\frac{a}{p}\rfloor\) 划分成 \(\sqrt a\) 个等差数列，每个等差数列的贡献是一个等比数列，对不超过根号的间距开根号个数组维护，否则直接更新。
260514 模拟赛 B 树链剖分
给定一棵 \(2^k-1\) 个节点的树，你需要将它剖分成 \(k\) 条链，每条链的长度都为 \(2\) 的幂并且两两不同，求方案数。由于树可能很大，所以只输入它的一棵 \(m\) 个节点的虚树。
\(k\le 60\)
首先注意到缩完二度点之后只能有不超过 \(4k\) 个节点（\(2k\) 个叶子）。但是直接 dp 的话仍然需要记录链的长度，是跟 \(n\) 相关的。发现如果两条链首尾相接，那么可以合并成一条考虑，这样链不会终结于一条边的中间，此时我们只需要记录链的下端位于子树的哪个节点即可。
如果链的端点已经位于三度点，就不能合并，因为可能有多个端点会算重。这个地方需要一些单步容斥。时间复杂度 \(O(m+k^2)\)。
P4916 [MtOI2018] 魔力环
利用 Burnside 引理，转化成对每个 \(n\) 和 \(m\) 的因数的子问题。我们可以 \(O(k)\) 枚举两端点处总共的黑球数量，然后剩余的部分形如若干个球放到若干个盒子里，一个盒子不能放超过 \(k\) 个，可以用一个 \(O(\frac{m}{k})\) 的容斥做，时间复杂度 \(O(n+\sigma(m))\)。
P8554 心跳
solution
尝试对一个 \(a\) 构造一个 \(p\)。发现前缀最大值的数量 \(k\) 非常关键，但我们还不会确定，所以先假定我们知道。考虑将 \(a\) 全部减小 \(k\) 得到 \(a'\)，那么非前缀最大值的地方都是 \(0\)，前缀最大值是 \([-1,n-1]\)。然后发现如果一个位置 \(i\) 是前缀最大值，那么后面至少要有 \(a'_i+1\) 个 \(0\) 作为删掉之后产生的前缀最大值。显然我们可以选取紧邻的 \(a'_i+1\) 个 \(0\) 作为备用前缀最大值，这里产生一个边界：开头不能是 \(-1,0\)。
现在我们说明 \(k\) 的唯一性，首先不难发现 \(k\in\{\min a_i,~\min a_i+1\}\)。假如 \(k=k_0\) 时 \(a'\) 合法，即说明 \(k=k_0-1\) 时不合法，首先 \(k_0\) 时 \(a'\) 中不能有 \(>1\) 的数，不能有 \(-1\)，所以只有 \(0,1\)。而且显然开头必须是 \(0,0\)，这里就会增加一个，然后第 \(3\) 个数无论填什么都会增加至少一个，所以炸了。事实上 \(n=2\) 时有反例 \(1,1\) 可以构造出两个 \(k=1\) 或 \(k=2\)。
直接对这个结构计数，将 ABC 填入序列，分别表示前缀最大值、备用前缀最大值和其他。要求：B 必须紧跟 A，开头只能是 AB 或 AA。由于 AB 对应两个 \(0\)，和 C 不能区分，因此钦定 AB 贪心的靠前，这里用一些小容斥即可。
可以设 \(dp[i][j][0/1][0/1]\) 表示前 \(i\) 个字符，放了 \(j\) 个 A，有没有孤立 A（\(-1\)），有没有 CC（后面不能有 AB[^B]），直接转移即可。
P5417 [CTSC2016] 萨菲克斯·阿瑞
已知一个 SA，我们可以得到一条由 \(<\) 和 \(\le\) 构成的不等式链，符合这个不等式链的字符串都能得到这个 SA。考虑对不等式链计数，发现钦定一个位置到底是 \(<\) 还是 \(\le\) 是困难的，因为关心两个位置的后一个位置。
发现 \(\le\) 号的方向本质上只是跟随它后一个位置的符号，所以最终都会推到一个 \(<\) 或者跟空串比较，二者的符号都是显然的，也就是说只需要确定 \(\le\) 形成的若干条链所在的位置以及之间的顺序即可，也就是说方案数是一个多重集排列，这样我们就能自然的确定 \(\le\) 的方向使得 \(\le\) 不会变成 \(<\)。
但是反之不亦然，可能会把 \(<\) 变成 \(\le\)，于是简单反演即可。不能直接用上面的方法确定 \(<\) 方向的原因是，如果不知道 \(<\) 的方向会影响链的构造。
P4221 [WC2018] 州区划分
模板 半在线子集卷积
P6672 [清华集训 2016] 你的生命已如风中残烛
所有和为 \(1\) 的整数序列，恰好有一个循环移位的所有非空前缀和都是正整数，所以给末尾添加一个 \(-1\) 然后反过来考虑后缀和，应用刚刚的结论即可。不能添加 \(1\) 是因为 \(1\) 不一定在循环移位中被放到最前面。
CF908H New Year and Boolean Bridges
其实一个节点的 SCC 可以直接独立出来，这样只有 \(23\) 个 SCC，问题转化为用给定集合幂级数的最少次幂覆盖全集，其实只需要做一次 \(fwt\) 和 \(n\) 次单点求值，复杂度 \(O(n^22^n)\)。
P4497 [WC2011] 拼点游戏
结构和策略是显然的，需要用一棵线段树或者平衡树维护第二问的答案，难点在于实现。
P9330 [JOIST 2023] JOI 国的节日 2 / Festivals in JOI Kingdom 2
最优策略其实可以看成是从右往左贪心选。考虑正难则反，那么根据最优性：
- 笨蛋策略的左端点一定在最优策略的右边；
- 笨蛋策略和最优策略的两个区间一定有交；
可以归纳成
- 最优策略的左端点一定落在笨蛋策略的区间内；
根据两个策略：
- 笨蛋策略的空隙中不能有左端点；
- 最优策略的两个相邻区间的左端点之间不能有完整区间；
我们容易通过若干 \(0/1\) 来记录当前是否在笨蛋策略的区间内，以及是否已经放置了最优策略的左端点。枚举当前放置的左端点对应的右端点插入在哪里，需要用第二个维度记录能够插入右端点的位置数量。
P6137 [IOI 2012] 理想城
将纵向和横向的贡献分开统计，把每行的极长连续段拿出来，两行相邻的段之间连边，显然形成一棵树，贡献就是 \(\sum sz(n-sz)\)。
qoj18206 Guess the Permutation
维护一个当前见过的最小值 \(x\) 和链上一个点 \(y\)，每次求出 \(y-x\)，标记 \(y=(y-x)+x\)，然后特判 \(y-x\) 比 \(x\) 更小的情况，可以通过大力分讨在两次询问内得到一个 \(\le \frac{x}{2}\) 的数字，所以额外花费 \(2\log n\) 的询问次数，是对的。