实在有必要单独拿出来说说，我一直认为我的计数能力相较其他能力是较突出的，但是最近做到的题目让我不得不怀疑我到底会不会做计数题。做计数时还是只能靠灵光一现吗？那这样的题目叫我怎么灵光一现？
所以有必要好好总结计数题的常见技巧。当然因为样本量有限，所以可能会漏掉某些重要的技巧。
从 2024 年 07 月开始，遇到计数题目就会尝试更新本文。
上次更新是 2024年 08 月。
等价关系
如果遇到一个看起来就很难在合法的时间复杂度内通过的限制，那么首先要做的就是找到原题目限制的等价条件。「AHOI2022」山河重整 是典型例子之一，原题目的条件似乎只能二维记录，但是直觉上来说这个条件感觉不满足的情况也比较单一。尝试 \(O(n^2)\) 的 DP 时可以发现等价条件，那么就可以针对不满足的情况容斥就好了。
另一个找等价条件的题目是 「2021 集训队互测」这是一道集训队胡策题。等价条件的妙用是解决这个题目的关键，发现满足原本的条件当且仅当 \(\sum_{i,j} ([a_i=c_{i,j}]+[b_j=c_{i,j}]-[a_i=b_j])=n^2\) 且其他情况一定有小于关系，于是只需要考虑取最大值的个数即可。
因此寻找等价条件的原则应该是让问题更可做。
而等价条件的寻找就要因题而异了，一般来说是对于某个模型或者某种特殊的性质有固定的处理思路，在这些处理上找到题目限制带来的特殊性。
唯一表示/最小表示
如果在条件的限制之下某几种类似的情况只会被计入一次，那么就考虑使用一种唯一的表示方法，比如最小表示，字典序最小，和最小，第一次出现的时候统计等等，因题目而异。
映射（双射）关系
一个问题的方案，可以通过构造或者映射的方式一一对应另一个问题的方案，或者互不相交地拆成几个不同的情况，或者相交的部分可以容斥掉。
典型的例子是通过 dp 的值反推原本的值。
比如如果有 \(f(i,j)=\max\{f(i-1,j),f(i,j-1)\}+a_{i,j}\)，那么就可以通过 \(f(i,j)\) 反推出 \(a\)，对 \(f\) 计数就可以等效于对 \(a\) 计数，而且 \(f\) 一定满足 \(f(i,j)\le f(i+1,j),f(i,j+1)\) 这一良好的性质。
对应的题目是 QOJ #2568. Mountains，是 LGV 引理的经典问题。以及加强版 QOJ #3082. Ascending Matrix 使用插值求出答案。
而且其实很多定理的证明也用到了双射的原理。
就拿 LGV 引理举例子。
针对不同情形的通常处理
对序列个数计数
如果条件只限制在相邻元素之间，那么就可以考虑通过插入并维护状态的方式来计数，通常来说就成了连续段 dp 的板子题目。
但是会存在一些限制，不能轻易地在 dp 上表示。这时可以考虑插入的顺序是否有特殊的地方。
比如 「2020-2021 集训队作业」Tour 此题（\(a_i\ge 0\) 的情况），通过合适的顺序选取，可以使得 \(x\) 被插入时未被插入的元素要么全部能插入在它的旁边、要么全部都不能插在它的旁边。那么对空位计数就可以了。
如果条件没有限制在相邻元素之间，那么如果没有转化成其他类型的问题，那么通常就需要 dp 来解决了。
有时还会考虑单调队列、单调栈等。
对树的个数计数
通常是矩阵树定理吧，但是偶尔会有记录连通块个数和一些信息的 dp 存在，其他情况就只能说是因题而异了（汗）。
棋盘问题
首先应该考虑横纵坐标能否分离。
如果不能将横坐标和纵坐标分离，那么可能思路就会比较有限了。此时就应该考虑棋盘的性质，比如满足相邻连边后为二分图，或者是平面图，以及诸如此类的性质。
计数方式的优化和技巧
动态规划
设计状态
有些时候合理的状态设计可以优化掉很多时间，最简单的比如如果 \(f(i,j,k)\) 中只会用到 \(k-j\)，那么就没必要记录 \(f(i,j,k)\) 而可以只记录 \(f(i,t=k-j)\) 就可以了。更多的例子因题而异
后置计数过程
有时如果说在每个时刻都要要求 \(f(i,\cdots)\) 的值就等于当前状态下的方案数，那么状态数会特别复杂。或者某个时候我们需要直到后续的状态来计算这个位置的贡献，这时会很头痛（当然也可以使用下面的钦定后续来做）。但是如果能够在某个时刻我们再进行“清算”，一般这个时候会比较特殊，可以通过较少的几个状态的值推出方案数，就可以得到较少状态的 dp 转移方程。值得一提的是，如果这个“清算时刻”的量级比通常转移的量级小，那么在这个时刻，我们还可以支持更高时间复杂度的计算和转移。
钦定后续（未来形 dp）
如果依次转移的 dp 计数时会受到后续的影响，可以钦定后续的状态为确定值，在转移途中通过一个个确定的位置对这个值进行回溯，合法的情况最终会回溯到一个合法的初始值（所有不合法的初始值都不能回溯到初始值，否则就要容斥了）。
矩阵树定理
\(D\) 为度数矩阵，\(A\) 为邻接矩阵，\(M_i\) 为 \(D-A\) 去掉第 \(i\) 行第 \(i\) 列的矩阵，记原图生成树个数为 \(C\)。则有：
\[C=\det M_1=\det M_2=\cdots=\det M_n \]某引理优化矩阵树定理
考虑矩阵 \(A\) 可逆时有以下等式：
\[\left[ \begin{matrix} I & 0 \\ V^T & I \end{matrix}\right] \left[ \begin{matrix} A+UV^T & U \\ 0 & I \end{matrix}\right] \left[ \begin{matrix} I & 0 \\ -V^T & I \end{matrix}\right] = \left[ \begin{matrix} A & u \\ 0 & I + V^TA^{-1}U \end{matrix}\right] \]因此得到 \(A\) 可逆时有 \(\det (A+UV^T)=\det A\det (I+V^TA^{-1}U)\) 成立。
那么放在矩阵数定理上容易度数矩阵 \(D\) 和邻接矩阵 \(A\) ，想到如果可以将 \(A\) 表示成 \(UV^T\)，则有 \(\det (D-A)=\det D\det(I-V^TD^{-1}U)\) 成立。
构造更小的 \(U,V\)，尝试缩小 \(V^T D^{-1} U\) 即可。
经典题目：AGC060F
LGV 引理（平面图前提下的组合意义）
如果有 \(n\) 个起点和 \(n\) 个终点各自排成一列为 \(s_i\) 和 \(t_i\)，且整张图为一个有向无环图。
构造矩阵 \(M\) 使得 \(M_{ij}=w(s_i,t_j)\)，其中 \(w(s_i,t_j)\) 表示所有从 \(s_i\) 出发到达 \(t_j\) 的路径上边权乘积之和。
如果原图为平面图，有 \(n\) 条路径 \((s_i\to t_i)\)，每条路径之间没有交，称这个路径组合法，且权值为这些路径上所有边的乘积。\(\det M\) 应该为所有合法路径组的权值之和。
如果不是平面图，则是一个没什么用的图论中的计数意义。
容斥
转移中容斥
这种方式一般会对应较为巧妙的计数题目。比如要求一个位置要么满足 \(A\) 性质，要么满足 \(B\) 性质，那么转移中可以钦定该位置满足 \(A\) ，并转移；钦定该位置满足 \(B\)，并转移。但是发现从这里转移出去的情况中可能会有该位置既满足 \(A\) 又满足 \(B\) 的情况，这时可以钦定该位置同时满足两个性质并转移 \(-2\) 倍。
更多的性质也是同理。
最终清算时容斥
就是最经典的容斥了。很多计数题目都有用。
实际上是反演的容斥
会放在反演类中单独提到。
反演
二项式反演
\[f(n)=\sum_{m\le n} {n\choose m} F(m)\Leftrightarrow F(m) = \sum_{n\le m} (-1)^{m+n} {m\choose n} f(n) \]通常运用于满足以下条件的情况：个体之间独立存在是否满足条件的要求，即一个个体是否满足条件不会影响其他个体是否满足；任意相同个数的个体集合全部满足条件的方案数相等；任意相同个数的个体集合全部不满足条件的方案数 仅有 1 种。比如 \(F(m)\) 的意义是只考虑 \(m\) 个个体，且这 \(m\) 个个体均满足条件的方案数，\(f(n)\) 的意义是只考虑 \(n\) 个个体，不对于这 \(n\) 个个体作其他要求时的方案数。那么显然有 \(f(n)=\sum_{m=0}^n {n\choose m} F(m)\)，反演可得 \(F(m)=\sum_{n=0}^m{m\choose n} (-1)^{n+m} f(n)\)，通常来说 \(f(n)\) 是好求的。
那么问题来了，现在我认为这样一个条件太局限了，显得整个反演很菜，感觉没什么用：“任意相同个数的个体集合全部不满足条件的方案数 仅有 1 种”。假如我认为，一个个体有两种方式不满足条件，也就是说 \(n\) 个个体构成的集合全部不满足条件的方案有 \(2^n\) 种时，二项式反演能否继续给力？实际上是可以的：
\[f(n)=\sum_{m\le n} {n\choose m} F(m)\times 2^{n-m} \\ \Rightarrow\frac{f(n)}{2^n}=\sum_{m\le n} {n\choose m} \frac{F(m)}{2^m} \]这样就皆大欢喜了，把 \(\frac{f(n)}{2^n}\) 和 \(\frac{F(m)}{2^m}\) 当作新的 \(f(n)\) 和 \(F(m)\) 即可。
另外还有三个二项式反演的变体，四者是类似的：
\[f(n)=\sum_{m\le n}(-1)^m {n\choose m} F(m) \Leftrightarrow F(m)=\sum_{n\le m} (-1)^n {m\choose n} f(n) \\ f(x)=\sum_{x\le i\le n} (-1)^{i} {i\choose x} F(i) \Leftrightarrow F(x) = \sum_{x\le i\le n}(-1)^{i}{i\choose x} f(i) \\ f(x)=\sum_{x\le i\le n} {i\choose x} F(i) \Leftrightarrow F(x) = \sum_{x\le i\le n}(-1)^{x+i}{i\choose x} f(i) \]多项式科技优化二项式反演
对于 \(f(x)\) 和 \(F(x)\)，设满足 \(f(n)=\sum_{m\le n} {n\choose m} F(m)\)。
则应该有：
\[\begin{aligned} &F(n)=\sum_{m\le n}(-1)^{m+n}{n\choose m} f(m) \\ &(-1)^xF(x)=\sum_{m\le x}{x\choose m} (-1)^m f(m) \end{aligned} \]我们可以通过 \(f(0),f(1),\cdots,f(n)\) 快速求出 \(F(0),F(1),\cdots, F(n)\) 的值。
因为 \(F(x)\) 在只考虑 \(x=0,1,\cdots,n\) 时等效于一个 \(n\) 次多项式，因此我们可以认为：
\[(-1)^x F(x)=\sum_{m=0}^n \frac{x^{\underline m}}{m!}(-1)^m f(m) \]考虑 \((-1)^x F(x)\) 的下降幂多项式形式其实就是上式。
众所周知，对于多项式 \(g\)：
\[g(x)=\sum_{m=0}^n g_m x^{\underline m} \\ \Rightarrow \mathrm e^x \sum_{m=0}^n g_m x^m=\sum_{m=0}^n \frac{g(m)}{m!}x^m \]注意第二个式子并非下降幂多项式形式，而是把下降幂多项式形式下的系数当作普通多项式形式下的系数进行卷积。那么让 \(g(x)=(-1)^x F(x)\)
而我们发现 \(g_m=\frac{(-1)^m f(m)}{m!}\)。所以直接普通多项式乘法就可以求出 \(g(0),g(1),\cdots,g(n)\)，进而求出 \(F(0),F(1),\cdots,F(n)\)。
目前已知的应用：「2020-2021 集训队作业」Tour
斯特林反演
\[\begin{aligned} &f(n)=\sum_{i=0}^n S(n,i)g(i)\Leftrightarrow g(n)=\sum_{i=0}^n s(n,i)f(i) \\ &f(n)=\sum_{i=0}^n (-1)^{n-i} c(n,i)g(i)\Leftrightarrow g(n)=\sum_{i=0}^n s(n,i)f(i) \\ &f(n)=\sum_{i=0}^n c(n,i)g(i)\Leftrightarrow g(n)=\sum_{i=0}^n (-1)^{n-i} s(n,i)f(i) \end{aligned} \]\(S(n,i)\) 是第二类斯特林数，\(s(n,i)\) 是第一类斯特林数，\(c(n,i)=|s(n,i)|\)。
这两类斯特林数具有优秀的组合意义。
\(c(n,i)\) 是长度为 \(n\) 的排列中轮换个数为 \(k\) 的排列个数，\(S(n,i)\) 是 \(n\) 个互相区分的元素分成 \(k\) 个互不区分的集合的方案数，\(s,c,S\) 都可以递推 \(O(n^2)\) 求出。
举一个最基础的例子，存在不同元素之间的二元等价关系 \(R\)，我们需要求出 \(f(n)\) 表示有多少种长度为 \(n\) 的序列使得两两元素均不满足等价关系 \(R\)。
那可以记 \(g(n)\) 表示有多少种长度为 \(n\) 的序列，并不做其它限制。
而根据等价关系可以对序列的元素划分等价类，因此枚举 \(i\) 表示序列中的元素可以划分成 \(i\) 个等价类，则有：
\[g(n)=\sum_{i=0}^n S(n,i) f(i) \]然后进行反演，得到：
\[f(n)=\sum_{i=0}^n s(n,i) g(i) \]就可以进行计算了。
标签：总结,le,反演,sum,det,计数,choose From： https://www.cnblogs.com/imcaigou/p/18363635