Charles Wu的博客

被这玩意卡了一上午——前天CSP-S模拟的T4需要用到这类问题的转移。为什么题解TMD是错的？

即$g(i,j,k)$表示“每个位置有$i$类元素可选，且序列中必须包含指定的$j$类元素的，长度为$k$的序列的个数”。形式化地讲，我们需要统计满足以下条件的序列的个数：$\forall p \in [1,k], a_p \in S\space(|S|=i); \forall b \in T \subseteq S\space(|T|=j), \exists p \in [1,k], a_p=b$。

通过容斥原理，我们可以计算出至少有$0,1,2,\dots,j$个$T$中的元素没有被包含在序列中的序列的个数，然后乘上容斥系数累加既是答案。也即： $$g(i,j,k)=\sum\limits_{x=0}^{j}(-1)^x\dbinom{j}{x}(i-x)^{k}$$。通俗地讲，我们在 $j$ 个元素中选择 $x$ 个，并强制使得它们不出现在序列中，其余元素任选。除去组合数的预处理时间，复杂度为$\mathrm{O}(j)$。参阅AtCoder ABC 194 F – Digits Paradise in Hexadecimal，可以使用上述计算而非DP求解（虽然DP更加简洁直观）。

（更多…）

考虑一棵无根树的生成方式：需要决定一个好的顺序从而达到不重不漏地生成所有 $n$ 个点的无根树。

类似有向无环图的拓扑排序，可以定义一种无根树的“拓扑排序”：每一轮将当前的叶子删去。这样可以很容易算出直径。设删除的轮数为 $r$，则当最终剩余一个孤点时，直径 $d=2r$，否则直径 $d=2r-1$。为了生成无根树，我们考虑进行逆操作，在当前的树上加叶子。在此之前，为了不重不漏地对无根树进行表示，我们考虑如下的唯一表示方法：设 $\text{dis}(x)$ 为节点 $x$ 在添加叶子过程中第几轮被添加上树的。对于$S=\{x\mid \text{dis}(x)=\text{const}\}$（也即同一层的节点），显然两棵有标号无根树同构但标号不同，当且仅当每个上述节点$x$的叶子节点的标号集合不同。我们总是将 $x$ 标号小的先行添加为其儿子。这样就不会出现因“两棵树本身同构，子节点编号集合相同导致重复计数的问题”。同时，为了方便、准确地计算，我们严格规定，新加入的 $k$ 个叶子节点在新树上就是全部的叶子节点。也即在旧树上的所有叶子节点在新树上至少有一个儿子。 （更多…）

看来脑瓜子还是不够灵活啊。以前看到“matching”、“bipartite”一类的标签，试图二分图时只晓得将题目中同一类的元素转化为点，将相对关系转化为边。但实际上，二分图也可以表示其他的二元逻辑关系，例如包含、排除。

例如[NOIP2010 提高组] 关押罪犯，一个经典做法是将罪犯转化为点集，将冲突关系符合一定条件的相互连边，然后二分答案作二分图匹配。（扩展域并查集实质上也是在贪心的基础上，运用“二分图匹配”的思想检查方案合法性……对吧？）

再例如AtCoder ABC 228 G – Digits on Grid，计数DP的转移也是在行、列元素分别作为左部、右部，以方格中的元素作为边权的二分图上进行的。

这道题则非常精妙——CF1634E – Fair Share。看到“要将所有元素分成两个相等的可重集”时，我认为应当用可重集作为二分图的左部和右部。但是这样一来，如何进行匹配呢？正解则是将数组$i$包含元素$a_i$的逻辑关系转化为边——左部为各个数组，右部为相同的元素。可以发现，能够有解的充分必要条件是“每个元素均统共出现了偶数次”，同时“每个数组含有偶数个元素”，那么该图中每个节点的度数均为偶。记得小学奥数的一笔画问题么？它有一个更专业的术语，曰欧拉回路。事实上，一张无向图存在欧拉回路，当且仅当不存在度数为奇的节点。所以，我们直接求解一条欧拉回路，将从左部到右部遍历的边记作$L$，从右部到左部遍历的边记作$R$，就是一个正确的解。