给定多个字符串，多次询问 $x$ 串在 $y$ 串中出现了多少次。
$x$ 在 $y$ 中的每次出现都恰对应 AC 自动机上的一个节点，使得这个节点为 $y$ 的前缀（在 Trie 树上为 $y$ 的祖先），并且这个节点存在后缀 $x$（在失配树上为 $x$ 的后代），这个点即结尾于该次出现的右端点的前缀。
也即我们需要查询 Trie 树上从根到 $y$ 这一条路径上，有多少在失配树上以 $x$ 为根的子树内。于是用树状数组根据 dfs 序维护子树和，在 Trie 树上 dfs，动态维护当前所在的点到根这一条路径上所有点，在树状数组上做单点加减，区间求和。
对每条线 DP，从上往下安排折线形态。
因为前一条线对当前的线有限制，所以需要计入状态。即状态应与已分配过的线数 $n$、当前线已安排的行数 $i$、左侧第一条线的形态 $T$，当前线已安排的形态 $S$ 有关。
发现状态中存在一些冗余信息：
我们不关心上一条折线 $T$ 第 $i$ 行以上的走势，只关心当前线 $S$ 到 $T$ 在第 $i$ 行上之间的宽度。
再次深入考虑后我们发现 $T$ 的第 $i$ 行一下的某一部分我们也不关心。
如果，我们安排当前线以下部分一直向左直到撞到上一条线，至少一直向左的部分长为 $k$，那么折线 $T$ 的第 $i$ 行一下的 $k$ 段，其形态我们也不关心。
又想到 $S$ 的长度仅为 $i$，$T$ 中我们只关心 $i$ 以下一直向左走多久会被撞到，和撞到的位置以下 $T$ 的形态，我们可以巧妙地设置状态。
这个状态的意义为，第 $i$ 行及以上部分为当前安排的折线形态 $S$，以下为尽量往左走，能够走出的形态。
这样将复杂度优化到 $O(n^22^n)$。
[CF1842D] Tenzing and His Animal Friends
首先以 $m$ 条 special restrictions 为边建一幅无向图，对于某一分钟的选取方案，我们定义关键边为两侧的点一个被选中，另一个未被选中的边。
然后考察任意一条 $1\to n$ 的路径，不难发现，点 $1$ 总需要被选取，点 $n$ 不可以被选取，因此任何一种选取朋友的方案的任意一刻，这条路径上至少有一条关键边。而在一种游戏方案中，每一条边为关键边的时间不超过它的边权。于是游戏时长不可能超过 $1\to n$ 的任意一条路径的长度，也就不可能超过 $1\to n$ 的最短路。
证明了游戏时长存在一个上界，现在需要构造一种方案使得游戏时长能够达到这个上界。记 $d_i$ 为 $1\to i$ 的最短路，点 $i$ 在 $[1,d_i)$ 这个时间段不被选取，在 $[d_i,d_n]$ 的时间段被选取，于是任意一条边权为 $w$ 的边 $(u,v)$ 满足 $|d_u-d_v|\le w$（最短路的性质），而前者即这条边作为关键边的时长，从而保证了题目的 special restrictions 成立。
然后就可以如此构造答案。
物品成序列，每次对其中的一个区间做背包问题。
设一组物品 $S$ 限定体积不超过 $m$ 的情况下能够取得的最大价值为 $f_S(m)$。如果使用线段树维护区间内元素的 $f_S$ 值会带来大量复杂度为 $O(m^2)$ 合并。而插入单个元素时间复杂度为 $O(m)$，所以我们倾向于使用更多的插入操作而非合并操作。
考虑对区间进行分治，将每个询问放到最小的完全包含询问区间的分治区间进行处理。显然询问区间一定跨过该分治区间中点。于是对于每个分治区间，预处理其前半部分的每个后缀的 $f$、后半部分的每个前缀的 $f$，各 $O(nm)$ 的时间复杂度，然后对所有跨过区间中点的询问，进行一次 $O(m)$ 的合并（因为这里只需要算出 $f$ 的一处点值）即可求得答案。
复杂度为 $O(nm\log n+mq)$
一种做法是，为等价类（颜色）寻找代表元，即待统计区间中最靠后者。
然后将询问按照右端点排序，保证统计区间为一个前缀。
如果区间中存在某种颜色，那么这种颜色的代表元一定在区间中，于是用树状数组维护当前前缀代表元数目，单点改、区间求和即可。
另一种做法：区间二维数点
对于数列中某个位置 $i$，记 $p_i$ 为 $i$ 之前最后一个颜色与 $i$ 相同的位置。
于是我们所求的，区间颜色数量，等价于求满足 $i\in[l,r],p_i<r$ 的位置数量。即代表元数量。
直接扫描线。
对图的邻接矩阵应用矩阵乘法，限制路径上的边数做计数/最优化时，相当于每条边的边权为 $1$。但此时图具有边权，所以考虑把每条边拆成一条长为边权的链。这样点最多有 $(w-1)m+n$ 个，无法接受。于是我们考虑把从同一个点出发的边拆成的链进行合并。具体地，从每个点 $u$ 引出一条长为 $w$ 的链，然后从链上相应的节点连向 $u$ 的后继 $v$。
邻接矩阵做矩阵乘法需要记录边权，而此题需要对点权求最值。所以将每条边的边权定义为终点的点权，节点 $1$ 的点权单独统计。
美食节的处理看作点权修改，也即边权修改，快速幂过程中对于具有修改的时刻进行特殊处理即可。
期望 DP，只维护合法的状态。
每次询问暴力做矩阵快速幂会超时，所幸，对于所有询问，要做快速幂的矩阵是相同的，并且我们只需要向量乘矩阵幂后的结果。所以可以预处理出快速幂所需要的中间量，即 $A^{2^k}$ 处的取值，快速幂就只需 $\log n$ 次向量乘矩阵，时间开销由 $O(Tm^3\log n)$ 优化为 $O(m^3\log n+Tm^2\log n)$。