轮廓线 dp 学习笔记
轮廓线 dp 也是一种状压，适用于一维特别大而另一维特别小的情况。 我们来从一道经典例题入手：求 $1 \times 2$ 的骨牌填满 $n \times m $ 的矩形的方案数。 如果 $n,m \leq 11$ 那么当然可以轻松状压了，但是如果 $n = 10^5$ ，我们就要考虑使用轮廓线 dp 了。 设 $f_{i,S}$ 表示我们填到第 $i$ 行，我们在状压的状态中记录下图红线上...
轮廓线 dp 也是一种状压，适用于一维特别大而另一维特别小的情况。 我们来从一道经典例题入手：求 $1 \times 2$ 的骨牌填满 $n \times m $ 的矩形的方案数。 如果 $n,m \leq 11$ 那么当然可以轻松状压了，但是如果 $n = 10^5$ ，我们就要考虑使用轮廓线 dp 了。 设 $f_{i,S}$ 表示我们填到第 $i$ 行，我们在状压的状态中记录下图红线上...
题目大意二分图点有点权，定义点集的权值为点权和，统计二分图中有多少个点集，满足被至少一个匹配覆盖。 $n,m \leq 20$题解首先你要知道一个叫做霍尔定理的东西：设 $G$ 中有一组匹配，一端恰好为组成 $X$ 的点的充分必要条件是： $X$ 中的任意 $k$ 个点至少与 $Y$ 中的 $k$ 个点相邻。（摘自百度百科） 这个告诉了我们如何判断一个点集是否能被一个匹配覆盖，但是暴力枚举+...
题目大意把 $n$ 个数分成 $k$ 个区间，每个区间的价值为区间内不同数字的个数，问价值和最大为多少。题解简单 dp：设 $f_{i,j}$ 表示前 $i$ 个数 分了 $j$ 段的价值和最大是多少。我们记 $cnt_{l,r}$ 表示 $[l,r]$ 的不同的数的数量，那么有转移朴素的转移是 $O(n^3)$ 的，我们观察这个式子，如果固定 $j$ ，我们用线段树维护 $f_k+cn...
题意：给你一个序列s，你把这个序列的所有不同排列按字典序排列后，求s的排名mod m 不保证 $m$ 是质数。 题解：我们记 $cnt_i$ 表示填到当前 $i$ 这个数还有多少个，不难发现题目要求的是： 显然后面的和式可以用树状数组轻松维护。 发现 $m$ 不一定是个质数，我们质因数分解后对于每一个 $p_i^{e_i}$ 分开做就好了。中间要将所有的数的 $p_i$ 因子都提取出来。（感...
CF1097G题意大概是给 $n$ 个点的树，定义 $f(S)$ 表示 $S$ 中所有的点构成的斯坦纳树的大小。求 发现我们只需要算 $\sum_{S} (^{f(S)}_ i)$ 了，这个式子其实计算的是所有点集的斯坦纳树中选择 $i$ 条边的方案数，这个树形背包做就好了。 设 $f_{i,j}$ 表示以 $i$ 为根的子树内选择了 $j$ 条边的方案数，转移时考虑： 1. 不选这个子树...