——忘川风华录《青鸟衔风》
501 CF1882E2 Two Permutations (Hard Version)
想了很久不会，感觉 E1 纯误导。
先考虑一个环的情况，我们尝试更好地刻画操作：
在环上考虑操作，于是连续段之间先后关系并不会改变，我们可以维护一个“开头”，那么操作相当于将开头与当前操作位置 swap（开头只是占位符，表示序列从这里开始）。
将开头记作 \(0\)，枚举最后 \(0\) 所在的位置就能确定最终序列的形态，每个置换环都容易贪心还原。
考虑两个环时只需想怎么将两个方案拼起来，一个显然的构造是若两个方案操作次数奇偶性相等，我们能在较短的方案后不断接 \(1,n,1,n\cdots\)。而手模发现在循环移位后，操作一定会改变逆序对数量的奇偶性，因此只需检查操作次数奇偶性相同的方案拼接即可。
复杂度 \(O(n^2)\)。
502 P9159 「GLR-R4」大暑
对于一种方案，我们考察一个交点的贡献，我们事实上可以任意指定 \(k\) 条入边与 \(k\) 条出边的配对关系，也就是说，如果其为 \(k\) 条线段的交点，会提供 \(k!\) 的系数。
一个暴力的想法是枚举 \(O(n^2)\) 个可能成为交点的位置，假设其可能被 \(t\) 条直线覆盖，那么这 \(t\) 条直线一定不共起点终点，于是可以使用二项式反演枚举方案中用了多少条并计算贡献：
那么转化成两个问题：怎么求被 \(t\) 条直线覆盖的交点数量，以及怎么求后面的式子，先考虑前者：
注意若 \(t\geqslant 2\) 条直线能覆盖某一交点，那么这些直线对应第一排点与第二排点位置均为等差数列，而且左右不能再扩展，先忽略第二个条件，那么式子形如：
莫反容易 \(O(n\log n)\) 求出。若考虑第二个条件，方案数可以使用容斥修正 \(d_t=c_t-2c_{t+1}+2c_{t+2}\)，容易验证正确性。
回到上面的式子，指数上的部分看起来就像关于 \(i,j,t\) 的若干次卷积，我们枚举 \(i\) 并考虑求和所有 \(t\) 对指数的贡献，那么有：
上面对 \(335544323-1=2\times 167772161\) 取模，使用 CRT 拆成对 \(2\) 与对 \(167772161\) 取模。前者由于 \((n-j)!\) 在，需要求和的项数不多，可以暴力；后者为 \(5\times 2^{25}+1\) 是 NTT 模数，原根为 \(3\)，我们可以把上面的式子拆成两次差卷积 NTT 求解（\(t\rightarrow j,j\rightarrow i\)）。
复杂度 \(O(n\log n)\)。
503 P9501 「RiOI-2」likely
和 P9537 [YsOI2023] CF1764B 的变换形式类似，我们也同样期待有类似的结果——
鸽一会儿。
504 P7278 纯洁憧憬 / loj#3397. 「2020-2021 集训队作业」春天，在积雪下结一成形，抽枝发芽 / nowcoder38727I Innocent longing
容斥成所有非平凡连续段长度小于 \(k\)，并令 \(m\leftarrow k-1\)。
考察排列的析合树，那么限制无非——若根为析点，任意儿子大小不超过 \(m\)；若根为合点，第一段与最后一段长度不小于 \(n-m\)，自然地去根据根的类型分类进行 dp：
根为合点，不妨假设儿子连续段上升，最后乘二来统计下降的情况。于是其第一个儿子与最后一个儿子的限制无非：不存在连续的真前缀，这就可以直接容斥了：
其中 \(P(x)=\sum_{i\geqslant 1}i!x^i\)。
于是根为合点的方案数（\(\sum_{i,j\geqslant n-k,i+j\leqslant n}g_ig_j(n-i-j)!\)）易在 \(O(n\log n)\) 内求得。
根为析点，即对于任意 \(n\)，统计长为 \(n\) 的单排列（不存在非平凡连续段的排列）数量 \(f_n\)，那么根为析点的答案即为 \((F-x-x^2)\circ Q\) 的第 \(n\) 项系数，其中 \(Q(x)=\sum_{i=1}^ki!x^i\)。
先尝试求出 \(f_n\)，可以容斥减去根为合点，或是根儿子数量不足 \(n\) 的数量，那么有：
记 \(R\) 为 \(P\) 的复合逆，带入 \(x=R\) 可得：
那么我们只需计算 \(R\)，注意到 ODE \(P=x+xP+x^2P'\)，带入 \(x=R\) 得到：
（\(P'\circ R=\frac{(P\circ R)'}{R'}=\frac{1}{R'}\)，链式法则）
提取 \([x^n]\)：
可以使用分治 NTT 处理。
我们还需计算 \((F-x-x^2)\circ Q\)，将 \(F\) 拆开，难点在于计算 \(S=R\circ Q\) 的第 \(n\) 项，我们在关于 \(R\) 的 ODE 中带入 \(x=Q\)：
仍然使用分治 NTT 处理，细节懒得管了（x
计算 \((F-x-x^2)\circ Q\) 也可以直接拉反，问题变为计算 \(Q\) 的复合逆，也能用类似的方法解决。
复杂度 \(O(n\log^2 n)\)，据出题人说可以全程使用半在线卷积做到 \(O(\frac{n\log^2 n}{\log\log n})\)。
505 P7857 「EZEC-9」Meltel
记有标号有根二叉树的 EGF 为 \(F(x)\)，有标号有根树的 EGF 为 \(G(x)\)，那么答案为（记 \(A(x)=\exp(G(x)-F(x))\)）：
我们写出 \(B(x)=x^sA(H(x))\)（记 \(H(x)\) 为 \(F(x)\) 的复合逆），那么可以施用扩展拉格朗日反演：
\(H(x)\) 易求，其为 \(\frac{x}{1+x+\frac {x^2}2}\)，我们尝试求出 \(A(H(x))\)。
展开 \(A(H(x))=e^{G(H(x))-F(h(x))}=e^{G(H(x))-x}\)，于是只需求得 \(G(H(x))\)，将其带入有标号有根树的方程：
牛顿迭代求解即可，复杂度 \(O(n\log n)\)。