建模问题总结

——删繁就简三秋树,领异标新二月花

一.建立树形模型

​ 对于很大一类问题，若其限制条件通过某种解读，能满足形如：1.不存在环；2.各点之间相互可以到达；3.满足特点的偏序关系，若干节点存在唯一的父亲节点（绝大多数情况下，这个祖先关系是特别抽象的，需要对其进行定义）4.待求问题的权值为若干条件的权值之积(该情况一般会将权值拆为边数，然后再计数，该处理方式同样适用于各种建图问题，并不限于树形问题)…

​ 转换为树形问题之后，通常还需要考虑儿子节点之间是否存在顺序关系。当我们成功对一类定义抽象的题面建立出树形模型之后，很多特殊性质也被同时挖掘出来了，而原问题很可能就被转化为我们较为熟悉的树形问题了：1.无向图/有向图求无根树/有根树；2.树的计数问题；3.树上染色问题…

1.[CTT2020 Day4] 甩锅 (dove)：

Des:

​ $n$ 个点，每个人可以向其他人连边(可以选择不连，其权值为 $1$)，当他和他连边人距离为 $x$ 时，他自己的权值为 $w_x$ ，一种情况其合法，当且仅当图中不存在环，而一个合法图的权值为所有人权值之积。给定 $w_i$，求所有情况的权值之和。($m\le 20,n=2^m$)

Sum:

​ 首先，本题合法图的权值定义为若干权值之积，这就引领我们考虑将权值拆为若干边。拆边之后，该问题可以转化为有向图的森林计数，由于森林不好求，给其加一个超级原点，然后使用矩阵树定理。由于矩阵是循环矩阵，所以可以转为求其系数构成的多项式的 $n$ 次单位根的值。

2.[3.21 Aly] 你的生命已经过加强 (candle)

Des:

​ 给定 $n$ 个数 $a_i$，表示一个长度为 $a_i$ 的左括号序列，该序列不能被拆分，将这些左括号序列组合起来，并配上右括号（不能在一个完整的左括号序列之间）保证其合法，定义其权值为所有相邻的完整左括号序列 $(a_i*a_j+1)$ 之积，求本质不同的所有情况的权值之和，这里的本质相同定义为：可以通过交换两个完整且合法的一段括号序列（左括号序列不能被拆分）。($n\le 5e6$)

Sum:

​ 由于题目给出的括号序列之间的关系特别难描述，却又似乎存在某种偏序关系，同时，这个题目关于一种情况的权值也定义为若干权值之积，这两点都指向我们要将原问题仍到树上。考虑将问题仍到树上之后：相当于一棵树，$a_i$ 为长度为 $a_i$ 的链，相邻链之间两点之间相互连边，求该无向图构成的有根树个数。

3.[集训队作业2018] 普通的计算题

Des:

​ 有一个 $0/1$ 序列，初始时为空，接下来可以进行两种操作：

​ 1.在序列末尾插入 $0$ ；

​ 2.在序列中删去一个子序列，并在序列末尾插入一个 $1$ ，该操作有一定限制(设选定子序列有 $x$ 个 $0$ ，$y$ 个 $1$)：1).子序列非空，即 $x+y>0$ ；2).当 $y>0$ 时，$x\in A$ ，$A$ 为给定集合；3).当 $y=0$ 是，$x\in B$ ，$B$ 为给定集合。

​ 求 $n$ 次操作后，序列只剩下 $1$ 的方案数，答案对 $998244353$ 取模。 ($n\le 1e5$)

Sum:

​ 如果只考虑原问题，我们会深陷一个无法优化的 $dp$ 的泥潭中，这个时候就得考虑一下它额外的性质。通过观察两种操作以及对目标问题，我们会发现：1.我们一定会出现 $n$ 个不同的 $0/1$ ；2.除了最后一个 $1$ 之外，每个点都会被删除，且删除时对应的添加了一个 $1$ 。这两条描述就非常满足树的性质：固定点数，存在根节点，各点之间存在一定的偏序关系（定义删除时加入的 $1$ 为该点父亲）。

​ 那么，原问题就转化为：

​ $n$ 个点，其权值为 $0/1$， 每个权值为 $1$ 的点的儿子有如下限制：1).若存在权值为 $1$ 的点，那么其权值为 $0$ 的点个数在集合 $A$ 中出现；2).若不存在权值为 $1$ 的点，那么其权值为 $0$ 的点个数在集合 $B$ 中出现。

​ 将该问题用生成函数描述后，解微分方程即可。

4.[UOJ Round #3] 链式反应

Des:

​ $n$ 个原子，由编号为 $1$ 的原子开始反应，每次会照射 $a(a\in A)$ 个编号比其大的原子使其无法反应，再让还能且还未反应的编号比其大的两个原子开始反应，求对于 $1-n$ 所有情况下的方案数。 ($n\le2e5$)

Sum:

​ 题目关于反应的描述指向性特别的强，它给出了很多偏序关系，将其描绘成树形问题：有标号有根树，其编号满足堆性质，其中有两个儿子有子树，求方案数。使用生成函数描述该问题，再使用分治 $FFT$ 求解即可。或者解微分方程。

二.建立路径模型

​ 对于某些求值问题，各值之间存在明显的递推关系，且这个递推关系固定（可以存在微小差异），通常转化为路径模型，然后通过统计路径来获得答案。特别的，路径数一般与组合数联系。

1.[3.24 lk ] Fibonacci’s Nightmare

Des:

​ 设 $a_0=1$ ，对于其后每一个 $n$ ，等概率从 $[0,n-1]$ 中选 $K$ 个数 $i_1,i_2…i_K $ ，令 $\displaystyle a_n=\sum a_{i} $ 。求 $\mathbb E(a_n^K)$ 对 $998244353$ 取模。($n\le1e5,K\le 10$)

Sum:

​ 由于这个递推关系存在随机，并且相互之间存在依赖，所以使用单纯的概率论特别不好做 $K$ 较大的情况，我们考虑根据这个递推关系，挖掘其特殊性质。

​ 考虑 $\mathbb E(a_n)$ 的组合意义：点 $n$ 对于 $[0,n-1]$ 随机连 $K$ 条边， $0$ 点向外流 $K$ 条流量的方案数。那么同理 $\mathbb E(a_n^K)$ 的组合意义就是将 $K$ 条边和 $K$ 条流量打上标记，求方案数。

2.[CTT 2019 day2] 序列 (array)

Des:

​ 有一个从 $0$ 开始，无限长的序列 $a_i$ ，定义变换为：将所有 $a_i$ 赋值为 $a_i+a_{i+1}$ ，接下来 $q$ 次询问，每次给出 $n,m,K,x,v,mo$ ，求将 $pos \equiv x(\mod n)$ 的位置设置为 $v$ 后，经过 $K$ 次变换位置 $m$ 的值对 $mo$ 取模后的结果。($\sum n\le 1e6$)

Sum:

​ 题面给出的 $v$ 显然只是常数，抹去 $v$ 之后继续考虑本题。本题依旧是存在确定的递推关系，而这个递推关系也非常的简洁，任意让人联想到路径数（组合数），但由于远端不止一个起点且各点之间可以认为是互不影响，所以是多条路径的路径数之和。即 $\displaystyle \sum_{i=0}^K \binom{K}{i} [i\equiv m(\mod n)]$ ，用单位根反演求得即可。

3.[1.29 WC模拟] 雪中送温暖 (warm)

Des:

​ $K$ 维空间中每个整点有一个信号灯，我们规定 $K$ 维数字全部都为 $1$ 的信号灯为红色；存在一维数字为 $0$ 的信号灯为绿色；对于其他的信号灯，定义它的 $K$ 个前驱为恰好有一维比其小 $1$ 的信号灯，其颜色由所有前驱中的红灯个数 $x$ 决定，若 $x$ 为偶数，则为绿色，反之为红色。接下来给出一个 $K$ 维矩阵 ${l_x},{r_x}$ ，求其中红灯个数，答案对 $998244353$ 取模。$(K\le 9,l_x,r_x\le1e18)$

Sum:

​ 由于 $K$ 很小，首先想到要容斥。接下来就是考虑如何快速求从原点开始的一个 $K$ 维矩阵里的 $ 0/1$ 个数。而贸然统计奇偶对于本题不太适应，我们首先放开奇偶这个条件，让其前驱的值直接加到自己身上，可以发现奇偶性是不变的。

​ 由于前驱的转移固定，所以原问题能很轻易地转化为路径问题。对于两维的情况，问题就是我们熟悉的组合数，再根据 $lucas$ 定理：$\binom{x+y}{x}=x\& y(\mod 2)$ ，扩展到 $K$ 维就是 $\frac{(\sum x_i) !}{\prod x_i!}$ ，其取奇数的条件为：对于任意 $x_i,x_j$ 都有 $x_i\& x_j=1$ 。然后再数位 $dp$ 即可。

三.建立线规模型

​ 对于某些求最值问题，其含有较多考虑对象，即含有较多变量，且各变量之间只有线性关系（保证线规的合理性），不方便进行正常求解，我们通常会尝试对其进行线规描述。由于线规的适用性很强，绝大多数问题都能被成功表述出来，但线规过后的求解过程才是难点。通常的，我们使用对偶来简化问题，简化后的问题可能为：二分图匹配问题；最小费用流；$dp$ 模型。

​ 先给出最经典的最小费用流模型：

​ 目标函数： $\displaystyle \min( b_up_u+\sum_{uv} c_{uv} \max(0,p_u-p_v-w_{uv}) ) $

​ 其中，$b_u$ 为点 $p_u$ 的流量需求，$c_{uv}$ 是边 $uv$ 的流量上限，$w_{uv}$ 是边 $uv$ 的权值。

​ 对偶问题通常非常需要技巧，同时也非常依赖于模型的建立，若方向错误就很难对偶出性质优秀的形式。所以找出优秀的模型并进行适当的对偶至关重要。特别的，对于最小生成树、最短路这类天然带有比较性质的问题，线规都会非常适用。

1.[SHOI 2004] 最小生成树

Des:

​ 给出一个 $n$ 个点 $m$ 条边的简单图，边有边权，钦定一棵生成树，我们希望通过修改某些边的边权，让我们选定的生成树为原图的最小生成树，求最少需要修改的边权和。($n\le 50,m\le 1500$)

Sum:

​ 题目中给出的变量为边权，但这个变量数量过于庞大且不具备优秀的性质，所以绝大多数方法都在本题失效了。同时，题目给出的 $n,m$ 都不是特别大。这就引导我们往线规上想，事实上，本题的线规描述也特别的优美。

​ 我们记边权的改变量为变量，设 $u$ 为树边，$v$ 为非树边，那么

​ 目标函数：$\displaystyle \min(\sum x_{u}+x_v) $

​ 约束条件：$ x_u-w_u \le x_v+w_v $ （非树边 $v$ 在树边 $u$ 的路径上）

​ 甚至不需要什么对偶，直接套用最小顶表标和即可（最大权匹配）。

2.[ZJOI 2013] 防守战线

Des:

​ 长度为 $n$ 的序列，在第 $i$ 个位置建一座塔的代价为 $c_i$ 。有 $m$ 个区间 $[L_i,R_i]$，要求在 $[L_i,R_i]$ 之间有至少 $d_i$ 座塔。求最小代价。($n\le 1000,m\le 10000$)

Sum:

​ 由于每个点建多少个塔为变量，且每个变量还配了一个权值，这就导致题目变得异常棘手，这个时候，我们考虑建立线规模型。当然，我们不能无脑线规，因为 $[L_i,R_i]$ 的限制不太好通过单点来描述，所以我们考虑用前缀和来描述，用 $s_i$ 表示前 $i$ 个位置建塔数量，然后再把限制拖到目标函数中，就能写出很规整的最小费用流模型。

3.[ZJOI 2020] 序列

Des:

​ 给定一个长度为 $n$ 的序列 $a_i$ ，每次可以选择一段区间的全部值、下标为奇数的值、下标为偶数的值减 $1$ 。求最少需要多少次将整个序列 $a_i$ 归零。($n\le 2e5$)

Sum:

​ 本题可以通过贪心处理，但是贪心的想法有点困难，我们考虑使用万能的线规来处理这道题。先考虑只有操作一的情况，可以发现答案为 $\sum\max(0,a_i-a_{i-1})$ ，当我们有操作二和操作三之后，我们操作的情况就不那么确定，但贪心的策略不变，所以这里关于操作一的使用就是变量，感觉贪心策略可以写成其他两种操作的情况，然后列出线规方程。值得注意的是，该题的 $n$ 较大，显然不能只通过最小费用流来得到答案。所以我们要使用对偶来简化问题，这里的对偶比较需要技巧：要先使用换元，再进行对偶才能方便地得到更为优秀的形式。再根据得到的式子列线性 $dp$ 即可。

四.贡献转化模型

​ 对于某些求和类问题，其题面给出的贡献描述不足以让我们进行很好地统计答案（答案的形式一般为全局总和类问题），这个时候，我们通常需要给原贡献赋以新的解释，即寻找它的组合含义或寻找其本质含义，以方便我们更换考虑方向。对于这类问题，我们需要不少的积累来开阔我们的视野，以方便我们快速地识别问题的本质。

​ 常见贡献转化的思路：重新考虑贡献的形式，深入分析贡献的由来，更换枚举贡献的方式，更换产生贡献的对象。通常还会配合经典的正难则反，求其反命题。排列类问题也通常需要用到贡献转化。

1.[11.22 cj_noip] color

Des:

​ 一颗 $n$ 个节点的树，每个节点可以被染成 $c$ 种颜色之一，但是相邻两个点颜色不能相同。给出一个大小为 $m$ 点集 $S$ ，求所有方案中，不同颜色个数之和，答案对 $1e9+7$ 取模。($n\le1e5,c\le1e9$)

Sum:

​ 若我们执着于思考原问题“不同颜色个数之和”，我们会陷入 $O(n^2)$ 的泥潭，我们考虑从其他角度来思考，不执着于每种方案，而考虑每种颜色：“不同颜色个数之和” 等价于 “每个颜色总出现次数之和” 。该命题的正面依旧不好求得，我们考虑将其转化：对于每种颜色，求其在总方案中没出现的次数。然后 $O(n)$ 做 $dp$ 即可。

2.[ARC 114] Sequence Scores

Des:

​ 一个长度为 $n$ 的序列 $A$，初始时所有元素都是 $0$ ，接下来进行若干次操作：选定一个 $v$ ($1\le v \le m$)，将 $[l,r]$ 的元素 $X_i$ 变成 $\max(X_i,v)$ 。对于所有 $A$ 能到达的状态 $B$ (不存在元素 $0$)，记 $f(B)$ 为从 $A$ 操作得到 $B$ 的最少操作次数。求对于 $A$ 能到达的所有 $m^n$ 种状态的 $f(B)$ 之和。($n,m\le 5000$)

Sum:

​ 如果我们仅考虑从正面分析每一种状态的贡献，很难逃脱 $O(n^3)$ 的泥沼。我们注意到题目要求的答案是全局总和，这就引领我们重新选择产生贡献的对象，一个可行的想法是考虑每个值的贡献。我们可以选择考虑某一个选定的值，其在序列中不同位置产生的贡献，依此法我们可以将时间复杂度降至 $O(n^2)$ 。

3.[lk] 序排速快 (tros)

Des:

​ 给定一个 $n$ ，定义 $n$ 的一个排列 $p$ 中的分割点为：任意在该点前面的数都小于在该点后面的数。规定快速排序为：每次判定是否存在分割点，1.若存在则按照分割点将排列分割开，递归做每一个部分，直到有序；2.若不存在分割点，则进行一次冒泡排序，并产生当前排列大小的贡献。求对于 $n$ 的所有排列，其贡献之和，答案对 $998244353$ 取模。($n\le 1e7$)

Sol:

​ 本题依旧是给出令人眼花缭乱的统计贡献方式，正面设计 $dp$ 来就解似乎不太可能：我们不太能维护一个排列的状态，也就不太好实现状态之间的转移。那么，我们深入分析贡献的产生。由于一次贡献是由一次冒泡的排列大小决定，而排列的大小由排列的所有元素贡献，这里我们可以考虑将贡献的产生归咎于各个元素。这样，我们需要求的就是每个元素会产生多少次贡献，而贡献的产生次数又等价于该元素被固定的时间。

​ 我们考虑一个元素被固定时的状态：元素 $i$ 在位置 $i$ 且小于该元素的元素全部在其前面。考虑描述这个末尾状态：设 $t_i$ 表示位置 $i$ 成为分割点。那么元素 $i$ 的贡献即为 $\max(t_{i-1},t_i)$ ，这样就保证了固定时需要的状态。

​ 现在我们仍然需要思考 $t_i$ 应该怎么计算。我们考虑对于元素 $i$ ，若其想成为分割点，那么小于等于它的值必须在它前面，显然，这些小于等于它的值我们只需要考虑位置最大的即可。那么，我们记 $p_i$ 表示小于等于 $i$ 的最大位置。因为一次冒泡一定会使 $p_i$ 减一，而结束状态就是 $p_i\le i$ ，那么 $t_i=p_i-i$ ，所以，原贡献即为 $\max(p_{i-1}-(i-1),p_i-i)$ 。

​ 接下来考虑如何计算即可，在此不深入讨论。

五.重定向模型

​ 对于某些人类智慧题，题面给出了很强/有规律的限制条件，但是其条件很难使用线规描述、且答案也很难通过简单的转化对象来求得，这个时候，我们可能需要将题目的条件进行重定向（可能与原条件有着天差地别），以方便我们深入挖掘其特性，然后再套用上述所总结的线规、转化对象、正难则反等做法来进一步简化问题。特别的，当题面给出的操作为多元操作时，由于多次多元操作可能会使问题变得越来越繁琐，所以我们考虑得考虑将操作重定向，使多元操作变成二元操作/一元操作。

​ 常见的重定向：点拆/化边，边拆/化点，前缀和，差分。常见的重定向条件：操作方式为多元操作。核心思想：变化之中寻找不变。

1.[AGC 052] Tree Edges XOR

Des:

​ 给定一个大小为 $n$ 的树（保证 $n$ 为奇数），边有两个边权 $w_1$ 和 $w_2$ ，定义一次操作为：选择一条边 $e(u,v)$，将与 $u,v$ 相连的其他边的 $w_1$ 全部异或上该边的 $w_1$ 。求通过操作，能否让每条边的两个权值相等。($n\le 1e5,w_1,w_2\le 2^{30} $)

Sum:

​ 题面给出的操作方式非常的有规律，但由于每次操作为多元操作，过于繁杂，导致根本无从下手。考虑到边权的变换是围绕点的，而且若答案是合法的，那么 $w_1$ 和 $w_2$ 应该是本质相同的，可能存在某种特殊的描述使其方便判定等价。这就引导我们往边权化点以及从 $w_1$ 和 $w_2$ 两面出发来考虑这道题。

​ 我们给每个点设一个点权 $f(x)$

​ 使得 $f(u) \bigotimes f(v)=w(u,v)$

​ $f(1)\bigotimes f(2) \bigotimes f(3)…=0 $

​ 那么，一次操作就相当于交换一条边的 $f(u)$ 和 $f(v)$ 。对于求 $f(u)$，我们拆位判定每一位选 $0/1$ 是否可行即可。接下来我们只用判定 $w_1$ 和 $w_2$ 的点权设出来是否相等。

2.[CTT 2019 day3] 数圈 (circle)

Des:

​ 给定 $n$ 个数 $a_i$ ，它们构成一个环，每次选环上一个值 $a_i$ 使：

​ $a_{i-1}’=a_{i-1}+a_i,a_i’=-a_i,a_{i+1}’=a_{i+1}+a_i $

​ 求最少需要多少次才能将所有数变成非负，无解输出 $-1$。($n\le 1e5$)

Sum:

​ 题面给出的操作性质非常好，但由于其操作为三元操作，多次操作后问题可能会变得异常繁杂，因此我们考虑将其变为一元操作。不考虑环的情况，我们会发现每次操作过后，全局的总和没变，甚至发生改变的那三个值的总和都没变。

​ 我们考虑设 $s_i$ 为 $a_i$ 的前缀和，那么每次操作就是交换相邻两个前缀和。而目标状态的前缀和中不存在逆序对，而一次操作一定可以删去一个逆序对，那么原问题就变成了统计逆序对个数，总和 $<0$ 无解。由于原问题为环，所以我们把定义广义的前缀和以及逆序对，再统计逆序对个数即可。

3.[PYY] 小跳蛙 (leapfrog)

Des:

​ $n$ 个点构成一棵树，给定 $1$ 号点的点权 $x$，定义一个合法方案为：将树含根划分为一个连通块，该连通块中父亲节点的点权大于等于其儿子点权之和。求方案数，答案对 $998244353$ 取模。($n\le 1e5,x\le 1e9$)

Sol:

​ 由于 $x$ 给的实在是太大了，在树上做背包是显然不可能的。我们大胆猜测答案应该跟 $x$ 关系不大，或者说答案的多项式次数肯定跟 $x$ 无关。同样的，由于每次的比较涉及二元或三元，这显然是我们所不能接受。由于树的点权和发生了变化，我们不会往前缀和上想。我们着重分析这个比较操作，一个显然的想法是，我们把比较看做作差，这样我们依旧保持了比较的性质，同时还强调了每个值本身的性质。

​ 通过父亲与儿子作差，原限制条件中的比较就变成点值大于 $0$ 。现在我们需要考虑根节点的点权 $x$ 对于限制的影响。这个时候我们再来求和就会发现，所以差分值之和即为 $x$ 。限制条件就变得特别宽松了，接下来我们只需要求得与 $1$ 相连各个连通块的贡献即可。使用重剖+分治 $FFT$ 优化求值即可。

六.建立数学模型

​ 对于某些设计巧妙的题目，题目给出精心设计的条件。而这些条件通常极其具有规律性（或者出题人刻意描述得没有规律）。这时，我们应发散思维，充分发挥自己的数学直觉，通过题目条件的蛛丝马迹，联想到自己掌握的数学模型。再通过高效数学模型求解方式对原问题进行求解。

​ 常见的数学模型：行列式，循环矩阵，单位根，高维 $FWT$ ，循环卷积。

1.[THU 2016 day3] 石家庄的工人阶级比较坚强 (stein)

Des:

​ $3^m$ 个人玩 $K$ 轮石头剪刀布，每轮进行 $m$ 次，第 $i$ 个人他在一轮中的 $m$ 次中游戏中，他所出的恒定，即他出的是他编号的三进制数，具体的，$0$ 为剪刀，$1$ 为石头，$2$ 为布。我们定义 $b_{uv}$ 表示 $i$ 比 $j$ 赢 $u$ 次，输 $v$ 次的权值，给定 $f_{0i}$ ，之后的每轮的 $f_i(x)=\sum f_{i-1}(y)\ b_{uv}$ 。求最后的结果，答案对 $998244353$ 取模。($m\le 12$)

Sum:

​ 本题给出的矩阵显然是不能用来转移的（它实在是太大了），我们考虑从这个诡异的石头剪刀布入手。由于石头剪刀布的规则是轮转对称的，其必然拥有较好的性质。一般这种轮转对称的东西会让我们想到对称差，而由于状态有 $3$ 种，那么显然不能使二进制对称差，所以我们考虑使用三进制对称差。而 $x$ 和 $y$ 进行比赛的结果中：赢的场次就是 $bit1(x-y)$ ，输的场次就是 $bit2(x-y)$ 。我们就能设 $B(i)=b_{bit1(i)\ bit2(i)}$ ，那么原递推式就变成了 $\displaystyle f_i(x)=\sum_{y+z=x} f_{i-1}(y)B(z)$ ，然后使用三进制 $FWT$ 来做即可。（由于$k$ 进制 $FWT$ 就相当于在做 $k$ 阶单位根的 $NTT$，而 $3$ 在 $998244353$ 下不存在二次剩余）

2.[lk] 石头剪刀布(rps)

Des:

​ 给出 $n$ 个长度为 $K$ 的字符串，字符串仅由 $RPS$ 组成，分别表示石头剪刀布，若两个字符串以任何任意起点作为开始进行 $K$ 轮石头剪刀布的胜负情况完全相同，则在代表这两个字符串的点之间连边。求最终图的团个数。($n\le 1e5,K\le 18$)

Sum:

​ 本题本质上与字符串没有什么关系，难点在于如何判断两个字符串的连通。通常我们认为求一个图的团个数是 $npc$ 问题，所以显然题面会给出某些限制来约束这个团，至少是约束团的大小。而这个 $K$ 的大小暗示了团的大小。接下来，就该考虑判断字符串之间的关系。

​ 看到石头剪刀布，我们本能往 $3$ 进制、$3$ 次单位根上想。本题也确实需要使用 $3$ 次单位根。由于比赛的形式类似一种循环比较，类似于[AH2017/HNOI2017]礼物，我们会往卷积上想。事实上，其确实也要用到卷积。而卷积我们的处理方式为 $DFT$ ，考虑 $DFT$ 的本质，相当于带入 $K$ 次单位根的点值，然后再点乘。而题目给出的限制要求该 $DFT$ 后除常数项各项点乘积为 $0$ ，这就告诉我们该如何判断两个点是否连通。再设计状压 $dp$ 即可。

3.[CTT 2020 day3] 计数鸡 (count)

Des:

​ 给一个 $n$ 的排列 $q$ ，以及一个长度为 $n$ 的序列 $h$ ，定义 $n$ 的排列 $p$ 的优美度为 $\displaystyle \sum_{i=1}^n \sum_{j=i+1}^n [p_i \ge p_j]+[p_i+h_i\ge q_j]$ ，求 $n$ 的所有排列 $p$ 中，优美度为偶数的个数，答案对 $998244353$ 取模。($n\le300$)

Sum:

​ 当题目要求关于排列的贡献时，由于排列的性质过于差，状态极难描述，所以我们通常需要转化贡献。我们深入分析原问题的特殊性：其只要求值为偶数的个数。对于奇偶类问题，我们会很自然地想到将其等价或相互取反来求解。不过本题正反难度几乎一致，那么我们就考虑作差。我们设偶数贡献 $1$ ，奇数贡献 $-1$ ，再以此求得所以排列的贡献就可以很容易得到答案了。

​ 接下来再来考虑原式。对于形如 $\displaystyle \sum[p_i \ge p_j]$ 的问题，这一看就是求逆序对，而联系到排列的逆序对，我们常常会联想到行列式。而由于行列式的秩 $\displaystyle \sum(-1)^{s(p)}\prod a_{ip_i}$ ，我们现在仅考虑了前面一部分，对于后面的行列式 ${a_{ij}}$ ，我们还完全没有考虑。现在我们就考虑将后式的贡献，由于 $a_{ip_i}$ 表示排列的第 $i$ 个位置为 $p_i$ ，那么其产生的贡献显然就是 $(-1)^{\sum_{j=i+1}^n [p_i+h_i\ge q_j]}$ 。这样就可以用高斯消元过掉本题。

七.建立等价模型

​ 对于某些计数问题，题面给出的统计条件特别的严苛，合法条件难以快速检验，这个时候，我们就要考虑转化一下检验方式，或者通过某种等价关系修改/略去部分检验以到达快速检验的效果，从而优化计数。

​ 常见的判定条件：大小关系；包含关系；正反关系；合并与拆分。一般遇到这些情况，我们就要考虑各个关系之间的相互转化、相互等价。

1.[PKU 2018 day1] esperar (esperar)

Des:

​ 给出 $n$ 个数 $a_i$ ，$b_i$ 是 $a_i$ 的因子，$c_i$ 是 $b_i$ 的因子，求 $\Pi c_i^2 \ge \Pi b_i$，答案对 $998244353$ 取模 。($n\le 100,a_i\le 1e9$)

Sum:

​ 题目给出了很是令人讨厌的比较大小，我们简单估算一下 $\prod c^2$ 和 $\prod b$ ，这两个值怎么说都到达了 $1e100$ 的程度，对于这种程度的数字进行比较，我们完全没有任何办法。若我们真的去比较了这两个数的大小，似乎就无视了题目给出的很多条件。

​ 观察题目给出的条件，我们简单认为第一个条件在比较大小不存在多大影响，所以我们深入分析第二个条件。由于 $c_i$ 是 $b_i$ 的因子，那么我们可以设 $c_i*d_i=b_i$ ，这里 $c_i$ 和 $d_i$ 都是 $b_i$ 的因子。若 $\prod c_i^2\ge\prod b_i$ ，那么 $\prod d_i^2\le b_i$ 。我们将其两两等价，那么我们就只需要求 $\prod c_i^2=\prod b_i$ 的情况即可。接下来使用 $dp$ 求解即可。

2.[CEOI 2019] amusement

Des:

​ $n$ 个节点 $m$ 条边的有向图，每次可以选择若干条边进行翻转，求所有翻转后为有向无环图的情况中翻转边的数量之和。($n\le 20,m\le \frac{m*(m-1)}{2} $)

Sum:

​ 由于求贡献时，我们既需要判定是有向无环图，又要统计翻转的边数。这显然就是我们无法接受的事。现在我们考虑挖掘有向无环图，这个东西的性质。由于其为环，且边有向，所以每种情况一定存在一个反状态。而这两种情况翻转的边数之和恰好为 $m$ ，所以，我们事实上只需要求原图的有向无环图个数。套用子集卷积求逆即可。

八.小结

​ 很多时候，当我们遇到很棘手的限制或很复杂的贡献形式，应该优先考虑转化模型，直到所有的技巧穷尽之前尽量不要硬着头皮 $dp$ （当然，有时我们也不得不采取得分优先的策略，此时也得当机立断写更为容易的 $dp$）。

​ 贡献转化相对来说是最为常见的做法，拿到题目的第一时间就得考虑转化一下贡献。

​ 当题目给出操作十分复杂时，我们得考虑重定义操作，而我们这时秉持的思想为：“变化中寻找不变”。通常的，对于总和不变的问题，我们应该尝试求和；对于差值不变的，我们作差（通常还要考虑 $xor$）；对于图论问题，分析清楚边与点之间的变化与不变。

​ 此外，数学模型的引入也非常重要。题目通常不会直接给出浅显易套用的模型，这需要我们深入分析、发散思维，寻找题目条件与数学模型之间的联系，再考虑套用模型。

​ 树形模型与路径模型问题通常也极其具有特性，遇到相似问题时应该考虑往这些模型上思考。

​ 建立等价模型启发我们常常去思考一种状态的对立状态，通过两个对立状态的交叉来求解。

​ 在所以办法穷尽之前，我们还有一招万用药：线性规划（通常用于求解最优性问题）。通常而言，适用性越广的方法，其效率会相对较低。所以，在使用线规之前我们也得观察数据范围斟酌一下（当然也存在线规转 $dp$ 的例子）。