日记

神秘稳定婚姻

CA Loves GCD# Link to

神秘小 dp。

设 $dp_{i,j}$ 表示前 $i$ 个数里凑出一个 $\gcd = j$ 的集合的方案数。转移是平凡的，注意预处理 $\gcd$，不然时间复杂度就是 $O(T \cdot nV \log V)$，过不了。预处理就是 $O(V^2\log V + T \cdot nV)$。

DZY Loves Math VI# Link to

孩子们，我又来莫反了。

钦定 $n \le m$，直接开始推式子：

我们发现这一坨：$\sum_{g = 1}^{n}g^g\sum_{d = 1}^{\lfloor \frac{n}{g} \rfloor}\mu(d) \times d^{2g}$ 的复杂度是一个调和级数，所以我们只用考虑如何 $O(1)$ 求解 $\sum_{i = 1}^{n}i^g$ 就是了。由于枚举 $g$ 单增，我们维护一个 $val_i$ 表示当前的 $i^g$，因为 $\lfloor \frac{m}{gd} \rfloor$ 最多就是个 $\lfloor \frac{m}{g} \rfloor$，所以我们只用更新 $i \in [1,\lfloor \frac{m}{g} \rfloor]$ 并求前缀和就行了，也是调和级数，$O(n \log n)$。

烷基计数# Link to

看起来很简单，实则不然。

我们设 $dp_i$ 表示有 $i$ 个点的情况，初始 $dp_0 = 1$，转移就是枚举两颗子树的大小 $x,y$，剩下的 $z = i - 1 - x - y$。我们钦定 $x \le y \le z$。那么有转移：$dp_i \gets dp_x \times dp_y \times dp_z$。蛋柿，我们发现，如果有 $x = y$ 或者别的相等，那么这玩意立马暴毙。

我门发现，当有两个数相等的时候，就例如 $x = y$，那么就相当于在 $dp_x$ 里取两个可重的不做区分的数的方案数。显然不能简单的 $dp_x^2$。这个的方案数是 $\binom{dp_x + 2 - 1}{2}$，具体的自己下来去推。

对于三个相等的，就相当于在 $dp_x$ 里取三个可重的不做区分的数。方案数就是 $\binom{dp_x + 3 - 1}{3}$。那么我们转移就是：

这就很好做了。

Tree Colorings# Link to

我们发现，如果一个点不是绿色，那么它的子树一定都和它一个颜色。因为根是绿色，所以如果它的子孙要到根，就得经过它，它就只能是绿色或者和它的子孙一个色。

考虑在树的形态固定时怎么做。设 $dp_u$ 表示以这个点为根的方案数。那么显然有 $dp_u = \prod_{v \in son(u)}dp_v + 2$。这个 $dp_v$ 表示 $v$ 还是绿色的方案数，$2$ 表示这个 $v$ 是其他的色的方案数。

我们发现这个方案数一定是很多个数乘起来的，所以我们设 $dp_i$ 表示方案数恰好是 $i$ 时最小的点数。那么我们枚举 $i$ 因数 $d$，注意 $d > 2$。那么就有 $dp_i = \min(dp_{d - 2} \times dp_{\frac{i}{d}}$。时间复杂度 $O(n\sqrt{n})$。

Match, Mod, Minimize# Link to

我们把 $a_i$ 变成 $m - a_i$，那么原式就变成了 $\max((b_i - a_i) \bmod m)$。我们发现，对于 $b_i < a_i$，答案是 $b_i + m - a_i$，那么答案就是把一些 $b_i + m$，使得 $b_i \ge a_i$，求 $\max((b_i - a_i) \bmod m)$。显然我们应该把 $a,b$ 都按升序排序。我们发现加 $m$ 的那些数一定是最小的几个，且加的数应该越小越优。直接二分出最小的加 $m$ 的数的个数能够使得 $\forall i \in [1,n],b_i \ge a_i$，求出答案就是了。

后日谈 # Link to 后日谈

肚子疼。