对组合计数的理解
组合计数说的是这样一类问题：计算 \(\sum_{x \in S} F(x)[P(x)]\)。
这也指出了组合计数中我们最关注的三个点：主体 \(S\)，判定 \(P\)，贡献 \(F\)。
通常，确定主体后，会有相应的判定和贡献。这一步称为刻画。在一个题中，可能会在不同阶段，使用不同的结构刻画多次。
在每次刻画后，我们会使用一些经典技巧（如容斥），进一步改写判定和贡献的形式，直到可以直接计算，或是可以使用新的结构进一步刻画。这一步被称为统计。
我个人感觉计数题的做题流程就是：(刻画 + 统计)\(^\infty\)。
刻画
刻画有几种方式：
- 在题目中，会有多种伴生的、存在映射的主体，在其中选择合适的；
- 使用和判定、贡献匹配的组合结构，可以从经典的结构里选取，有时候也可以自己造一些简单的；
- 一些零散的，改变主体的技巧。
选择合适的主体
映射
直接把主体定为题目中含有的结构，或是题目中含有的结构之间的简单运算。
- [Petrozavodsk Winter 2022] Two Permutations
选择主体为 \(r = p \div q\)，这样限制变为单个数组上的 \(\sum \max(i, r_i) = k\)，更易处理。最后答案乘 \(n!\) 即可。
- [NOI 2025] 集合
选择主体为 \(f = f(P) = f(Q)\)，并在此基础上研究 \(P\) 和 \(Q\) 的合法选取方案。很容易就能想到容斥。
从上面的例子我们可以隐约感受到一点选取的方向：尽量让需要计数的主体变少 / 变简洁；围绕最难处理的限制进行钦定。
拆分
我们可以把题目中含有的结构不断拆分为更小的结构，最后再使用代数手段计算组合起来的答案。
- [Petrozavodsk Winter 2022] Math String
一个表达式可以看作很多和式的拼接，和式则为乘式的拼接，乘式为数字的拼接，数字为数位的拼接。
因此我们可以从数位开始，不断写出当前结构的 OGF，并通过代数推导去求上一层的 OGF，直到解决整道题。
溯源
有时候题目中对主体的判定条件是类似“可被生成”，然而不同的结构生成的主体可能是相同的。
这个时候有一种方向：考虑对每个主体，在所有生成其的结构中，找到最极端的那个，这样就把主体变成了生成主体的结构。
当然还有比较毒瘤的情况，有可能最极端的不是恰好一个，而是 eps 个，这个时候可以尝试打补丁来解决。
- [EC-Final 2023] DFS Order 4
推导得到一个 dfs 序合法的充要条件后，我们会发现这个判定本身就是极端地构造了一棵树。
因此可以把主体切换为这样的树，判定即需要满足“是被极端地连出来的”。
常见组合结构
相对排名数组
相对排名数组是和排列构成双射的结构。对于一个排列，以某种固定顺序考虑其所有元素，并在考虑一个元素时，往相对排名数组 pushback 其在所有考虑过的元素中的相对排名。
相对排名数组适合刻画的判定是逆序对相关的。因为观察容易得到一个排列的逆序数即其相对排名数组元素和（根据某种顺序的不同，可能需要在定义上做一些简单的代数变换，但不影响取值范围和性质）。
PEO
PEO 是图上的一种序列结构。具体来说，图的 PEO 是一个点的顺序，满足对于每个点，它邻居在 PEO 上比它前的那些构成团。
有定理：一张图是弦图当且仅当它存在 PEO。因此如果我们刻画的时候连出了弦图，则可以考虑它的 PEO。这在限制是一些 NP 问题相关时非常好用。
- [Petrozavodsk Winter 2020] Airplane Cliques
构建一张新图，有边 \((u, v)\) 当且仅当 \(\text{dis}(u, v) \leq x\)。那么相当于在这张图上数大小为 \(k\) 的团数。
这张图显然是弦图，考虑其 PEO，那么我们只需要求每个点在 PEO 上比它前的邻居个数就可以通过 poly 求出最终答案。
最后，可以发现这张图的 PEO 其实就是按原树的深度排序。于是我们只需要对每个点数，深度比它小、距离它 \(\leq x\) 的点数。这是数据结构相关的内容了，不再赘述。
折线
折线通常可以直观的刻画交换邻项、逆序对等信息。
具体来说，对于一个 01 序列，假设画一条 0 右 1 上的折线，那么折线下方面积就是逆序对数。而交换一对相邻 10 相当于“把一个角按下去”，交换相邻 01 同理。
对于非 01 序列，通常的处理方式是 01 原理之后使用折线。
- [JOISC 2023] Chorus
考虑刻画什么样的最终 \(S\) 是合法的。我们的判定过程形如：重复在碰到第一个 B 前取 A，然后删除前相同数目的 B。
考虑在 A 右 B 上折线上刻画这个过程，这相当于从 \((0, 0)\) 开始，重复：不断向右直到撞到折线上，然后向上走到 \(x = y\) 上。
因此我们得到判定：能在 \(x = y\) 下方画 \(k\) 个连续的等腰直角三角形，让折线完全位于这些三角形的下方。
而使得 \(S\) 变成这样的代价也是好刻画的，实际上就是 \(S\) 越过规定的这条线的总面积。
后面的部分就是一些 monge 相关优化了，不再赘述。
事实上可以看出，折线还可以用于非常精确的刻画冒泡。不过这个过于数据结构强相关，在这里就不说了。
折线组
对于满足行递增、列递增的二维数组，值域折线组是和它双射的结构。
具体来说，对于每个 \(i \in [1, v)\)，都画一条分割 \(\leq i\) 部分和 \(> i\) 部分的折线。
那么这些折线满足，每条都是只向上向右的，而且互不越过。反过来，满足这样条件的折线组也唯一对应了一个行列递增的二维数组。
- [Petrozavodsk Winter 2022] Mountains
如上文。接下来平移折线的开头结尾使限制变为互不相交，LGV 引理计算即可。
笛卡尔树
笛卡尔树是刻画区间最值、或最值分治的结构。
它还有一种扩展：斜笛卡尔树。斜笛卡尔树说的是，每个点连向左右第一个比它大的点，组成的结构。
斜笛卡尔树有两种画法，一般对应了不同的做法。第一种是，把连左和连右的边分离，变成两棵树。
第二种是，画成类三角剖分的图：
可以看到，笛卡尔树此时变成了其骨架（红色虚边）。
- [JOISC 2017] Railway Trip
\(a\) 和 \(b\) 一定会在区间 \(\max\) 处会合。考虑让它们分别往上跳。
考虑斜笛卡尔树的第一种画法，那么在到达之前，有用的点一定只有能跳到的，在第一 / 二棵树上最高的点。
倍增跳即可。
合并树
如果判定或主体是一个，类似分治的结构，那么可以考虑直接考察整棵合并树。
- [AGC022F] Checkers
考虑合并树，那么我们关注的就是每个叶子的 (作为左儿子数 mod 2, 作为右儿子数)。
事实上叶子的顺序并不重要，我们可以把主体切换为一个大小为 \(2n\) 的桶 \(c\)，桶里面存了每种状态一共有多少个叶子。判定即为，这个桶能否对应一种合法的合并树。贡献为 \(\frac{n!}{\prod c_i!}\)。
推导如何判定，我们考虑每次把两个叶子合并为它们的父亲，即每次可以删除 \((1 - x, y)\) 和 \((x, y + 1)\)，加入 \((x, y)\)。如果最后能只剩 \((0, 0)\)，则合法。
那么玩一些简单的 pattern 就会贪心的消除了。而且消除只会发生在相邻两层，直接 dp 即可。
动态虚树
动态插入所有点，时刻考虑当前所有点构成的虚树（类似一条链一条链的插入）。
- [NOI 2023] 桂花树
置换环
置换环也是和排列构成双射的结构。
- [Petrozavodsk Winter 2022] Two Permutations
上文已经提到了第一步切换主体的转化。现在考虑 \(\sum \max(i, r_i) = k\) 的限制如何刻画。
考虑其置换环，那么贡献只存在于每条环边上。从而，按下标升序加入点，做类似连续段 dp 状物，记录目前有多少条未封口的链即可。
Ferrers 图
Ferrers 图相当于把集合（以及可重集）直观地画了出来。这个东西的好处在于它可以旋转 90 度，当行列大小严重不均时会给出很好的解决方案。
- [CF2125E] Sets of Complementary Sums
通过一些推导可以把问题归约为：在 \([1, x]\) 不重选择 \(n\) 个数，求凑出 \(1\cdots x\) 的方案数。
首先容易发现 \(n\) 一定至多是根号级别的。那么对于一个方案，把它画到 Ferrers 图上并旋转，就变成：\([1, n]\) 任选可重集，凑出 \(1\cdots x\) 的方案数。完全背包即可。
二维平面
二维平面常用于刻画区间，或二维偏序判定。优点是非常直观，在草稿纸上画或是打表输出都易于发现性质。
- [JOI Open 2022] Seesaw
画成一个二维数组的样子，会发现向下、向右都是递增的。从而，假如我们要判定 \([\ell, r]\) 是否合法，那么相当于有两条向上向右的折线，问中间夹的区域是否连通。
容易发现两条折线是不会互相越过的，因此我们要判定的即为是否贴住了。即合法等价于每一条 \(\ell + r\) 固定的对角线都有点可以通行。
注意到全局的平均值是一定被包含在 \([\ell, r]\) 中的，因此每一条对角线上也一定只有其前驱后继是有用的，这相当于要么对 \(\ell\) chkmin，要么对 \(r\) chkmax。直接扫描线即可。
图
一般来说，如果操作是二元的，那么把操作的两个元素连边生成的图也是可以考虑的。
- [NOI 2025] 序列变换
动态图
有时可以把静态的图用动态的生成过程刻画。
- [Petrozavodsk Winter 2020] Horrible Cycles
杂项技巧
拆贡献
正难则反递归
组合意义
特殊容斥
a + b >= k
充要条件组
得到判定
确定主体后，贡献往往是直接的（或一些代数推导）。而判定有时并不显然。
此时我们可以运用的技巧基本等同于其他题目，比如，找 pattern、调整法、弱化推广、强化推广。下面是一个例子。
- [XX Open Cup, GP of Kazan] Bitwise Xor
容易想到使用 trie 树刻画，此时在 trie 树上调整会得到：如果有违反限制的对，那么一定有相邻的违反限制的对。
也就是说判定为，只需要相邻对都符合限制。这个形式是可以直接对着 dp 解决的。
统计
这一部分基本上分为两类：改造判定和贡献 / 计算技巧。