今天写的很乱。
[HEOI2013] SAO
容斥。因为我们已经知道父亲 \(<\) 儿子时的情况（\(n!/\prod_i siz_i\)，也适用于森林），那么儿子 \(<\) 父亲的情况就容斥掉，无限制的就当作那条边不存在。树上背包，记录当前节点为根的连通块大小和容斥系数的积。
*[ECFinal23A] DFS Order 4
转写为：统计多少个有根树，满足
- 父亲小于儿子；
- 儿子之间有序；
- 节点要比它的上一个兄弟的最后一个儿子小。
显然和 dfn 序形成双射。在边上画不等号，容斥，尝试转化为上一题的 \(n!/\prod_i siz_i\)。钦定一些边断掉，改成根向树拓扑序计数的形式，统计 \(1/\prod_i siz_i\) 带上一堆容斥系数。转移可以按照深度和子树大小转移，由深至浅，由小到大。
[AGC020F] Arcs on a Circle
钦定最长的弧，破环为链。将随机坐标拆开成随机整数部分和随机小数部分，枚举小数部分的大小关系（\((n-1)!\) 种情况出现概率相同），然后状压 DP。因为已经知道小数部分的大小关系，于是可以知道两端弧是否交了。
[AGC036F] Square Constraints
画一个平面直角坐标系，相当于在一个扇形里选出排列。已经知道，如果每个位置能选的是一段前缀 \(a_1\leq a_2\leq\cdots\leq a_n\)，那么答案就是 \(\prod_i (a_i-i+1)\)。所以尝试将排列左半边的区间限制容斥成前缀限制，需要先钦定有多少个被容斥成最长条的，然后就可以知道排名了。\(O(n^3)\)。
*无标题
考虑每一个大于的连续段，被 \(p_i=i\) 的直线切开两半，发现这些数能选的又是一个区间，也可以沿用上一题的套路容斥。大小关系按照从小到大和从大到小同时。同一段的方案数可以选完再除一个阶乘。
好像后面还要优化啊
*[AGC039F] Min Product Sum
先找所有最小值，钦定它们所在的行列，划去它们，递归到子问题。可以 dp。可以对方案数容斥，\((\min=v)=(\min\geq v)-(\min\geq v+1)\)。可以分步 dp，将过程拆成多步。最终可以做到 \(O(n^4)\)。
好像不是这个东西啊
*[UNR #7] 璀璨宝石
UOJ NOI Round #7 题解 - 博客 - qingyu的博客
完全掉线
这里有一个 LGV 题
看成不互穿的路径，这些路径将整个矩形划分，第 \(i\) 条路径和第 \(i+1\) 条路径之间填上权值 \(i+1\)。不互穿路径太草了，第 \(i+1\) 条路径向右上两个方向平移 \(i\) 单位长度，然后就能 LGV Lemma。
[2021 集训队互测 Round 2] Imbalance
\(k\leq 20\) 运行状压 DP。
\(k>20\)，将 \(1\) 当作 \(+1\)，\(0\) 当作 \(-1\)。首先发现如果 \(a[1,k]>0\) 那么以后所有长度为 \(k\) 的区间都有这个性质（否则会跨过去）。转为格路，看作这样的循环路径：
只要这些路径都不交就合法了。枚举起点位置，计算 \(O(k^{n/k})\) 个 LGV Lemma。
集合幂级数但是 mex 卷积
\[\begin{aligned} c_0&=a_1b_1+a_1b_2+a_2b_1+a_2b_2=(a_1+a_2)(b_1+b_2)\\ c_1&=a_0b_0+a_0b_2+a_2b_0=(a_0+a_2)(b_0+b_2)-a_2b_2\\ c_2&=a_0b_1+a_1b_0=(a_0+a_1+a_2)(b_0+b_1+b_2)-c_0-c_1 \end{aligned} \]\[F(a_0, a_1, a_2)\to (a_1+a_2, a_0+a_2, a_2, a_0+a_1+a_2) \]点乘一下再变到答案：
\[\implies G(c_0, c_1+a_2b_2, a_2b_2, c_2+c_0+c_1)\to (c_0, c_1, c_2) \]\(O(4^n)\) 解决。
[2022-2023 集训队互测 Round 8] 环覆盖
欲求
\[[x^0y^k]\prod_{(u, v)\in E}(1+x_ux_vy) \]\(x\) 上做异或的 FMT，已知
\[FMT(A)_i=\sum_{j}(-1)^{popc(i\&j)}a_j \]所以
\[[x^S]FMT(\prod_{(u, v)\in E}(1+x_ux_vy))=\prod_{(u, v)\in E}(1+y(-1)^{|S\cap\{u, v\}|})=\prod_{(u, v)\in E}(1+(-1)^{[u\in S]}(-1)^{[v\in S]}y) \]又已知（\(IFMT(A)=FMT(A)/2^n\)）
\[IFMT(A)_0=\sum_jA_j/2^n \]所以我们最终的答案肯定形如
\[\sum_{t}(1-y)^t(1+y)^{m-t}c_t \]\(c_t\) 这个系数可以 \(O(2^n)\) 求解。然后剩下的东西暴力求解。
标准生成函数题
第一步要容斥，钦定 \(S\) 在某些位置出现。\(S\) 出现以后可能还会有 \(S\) 接着出现，但一定是与 border 有关的。
令 \(|S|=m\)，它有 border \(c_1, c_2, \cdots, c_k\)，令 \(C(z)=\sum_{i=1}^kz^{m-c_i}\) 表示它的 border 的生成函数。
那么答案的生成函数为 \(SEQ(rz-z^mSEQ(-C(z)))\)。\(-1\) 都是容斥系数。直接计算即可。
标签：路径,2024.8,钦定,选讲,容斥,GF,2b,prod,LGV From： https://www.cnblogs.com/caijianhong/p/18338849