先放题，有时间再整理。 其实也就那回事，理解了思想之后就没啥特殊性了。 luogu6647 [CCC2019] Tourism 不难发现 $t =\lceil \frac{n}{k} \rceil$，然而并没有什么用，我们只要在转移时对取值区间进行限制即可。 具体地，第 $i$ 天的取值左端点是 $L_i = \max(0,i-k)$，右端点是 $…

[ARC101E] Ribbons on Tree 对于以 $x$ 为根的子树，如果 $(x,fa_x)$ 的边没有被覆盖，那么说明子树内没有任何一个点与子树外的点匹配。 把这些没有被覆盖的边看作特殊边，那么整棵树就被若干特殊边划分成了若干连通块。我们要求的是不含任何特殊边的匹配方案。 考虑容斥。钦定一个边集 $S$，表示 $S$ 内的边一定是特殊…

计数杂题。 CF840C On the Bench 先进行一些基本的观察。 $\texttt{Observation}$ ${a_i}$ 中乘积为完全平方数的数集，一定是相对封闭的。因此我们可以将 ${a_i}$ 划分成若干个集合，满足其中两两乘积为完全平方数。 $\texttt{proof}$ 考虑和 $a_i$ 相乘为完全平方数的数集 ${a_…

树形 DP 计数。 luogu8867 建造军营 对于图中一条非割边，看守与否都相同，因此可以用 Tarjan 算法求出边双再缩点，把非树边单独拿出来，讨论每一条树边。 然而貌似不是很好做，子树外是否建造会影响子树内。考虑设 $f_x$ 为军营只在以 $x$ 为根的子树中出现，且至少存在 $1$ 个军营的方案数。 转移时对于边 $(x,y)$，如果…