date: 2020.07.12 12:00-17:00

practice link

题目大意：在 $N^{+}$ 上定义一棵树，$n$ 的父亲为 $\frac{n}{\min n}$。有一个权值数组 $w$，求 $\min_{u}\sum_{i=1}^{m}w_{i}\cdot\text{dis}(u,i!)$。

题解：$\text{dis}(u,v)=\text{dep}(u)+\text{dep}(v)-2\text{dep}(u,v)$。如果能建出虚树，那么一次 dfs 就能求解。

考虑建虚树的过程，与普通虚树唯一不同的地方在于求 $(i-1)!$ 和 $i!$ 的 lca。将 $i$ 分解，考虑其中最大的质因子，易见在该质因子之后 $(i-1)!$ 和 $i!$ 就分岔了。这样一来，可以用树状数组维护每个质因子的数量，而 lca 的深度即为 $(i-1)!$ 中大于等于 $i$ 最大质因子的数量。

论文题。

题目大意：给出正定矩阵 $A$，求满足 $\boldsymbol{x}^{T}A\boldsymbol{x}\le1$ 的条件下，$\max_{\boldsymbol{x}}\boldsymbol{b}^{T}\boldsymbol{x}$。

题解：注意原问题对称，将其转化为最小值，直接 KKT 条件暴解。需要满足的条件是：

$$ \begin{cases} \nabla f(\boldsymbol{x})+\mu\nabla g(\boldsymbol{x})=\boldsymbol{0}\\ \mu g(\boldsymbol{x})=\boldsymbol{0}\\ \mu\ge0\\ g(\boldsymbol{x})\le0\\ \end{cases} $$

其中 $f(\boldsymbol{x})=\boldsymbol{b}^{T}\boldsymbol{x}$，$g(\boldsymbol{x})=\boldsymbol{x}^{T}A\boldsymbol{x}-1$。

$$ \begin{aligned} \text{tr}(\mathrm{d}g)&=\text{tr}(\mathrm{d}(\boldsymbol{x}^{T}A\boldsymbol{x}))\\ &=\text{tr}(\mathrm{d}(\boldsymbol{x}^{T})A\boldsymbol{x})+\text{tr}(\boldsymbol{x}^{T}A\mathrm{d}\boldsymbol{x})\\ &=\text{tr}((\mathrm{d}\boldsymbol{x})^{T}A\boldsymbol{x})+\text{tr}(\boldsymbol{x}^{T}A\mathrm{d}\boldsymbol{x})\\ &=\text{tr}((A\boldsymbol{x})^{T}\mathrm{d}\boldsymbol{x})+\text{tr}(\boldsymbol{x}^{T}A\mathrm{d}\boldsymbol{x})\\ &=\text{tr}(\boldsymbol{x}^{T}A^{T}\mathrm{d}\boldsymbol{x})+\text{tr}(\boldsymbol{x}^{T}A\mathrm{d}\boldsymbol{x})\\ &=\text{tr}(\boldsymbol{x}^{T}(A^{T}+A)\mathrm{d}\boldsymbol{x}) \end{aligned} $$

而 $\mathrm{d}g=\text{tr}\left(\left(\frac{\mathrm{d}g}{\mathrm{d}\boldsymbol{x}}\right)^{T}\mathrm{d}\boldsymbol{x}\right)$，对比系数有 $\frac{\mathrm{d}g}{\mathrm{d}\boldsymbol{x}}=2A\boldsymbol{x}$。可得 $\boldsymbol{b}+2\mu A\boldsymbol{x}=\boldsymbol{0}$。若 $\mu=0$，那么必然有 $\boldsymbol{b}=\boldsymbol{0}$。除此以外，$\mu>0$。因而 $g(\boldsymbol{x})=\boldsymbol{0}$。又有 $\boldsymbol{x}=-\frac{1}{2\mu}A^{-1}\boldsymbol{b}$。可得

$$ \begin{aligned} &\boldsymbol{x}^{T}A\boldsymbol{x}\\ =&\frac{1}{4\mu^{2}}\boldsymbol{b}^{T}A^{-1}AA^{-1}\boldsymbol{b}\\ =&\frac{1}{4\mu^{2}}\boldsymbol{b}^{T}A^{-1}\boldsymbol{b}=1 \end{aligned} $$

因而，$\mu=\frac{1}{2}\sqrt{\boldsymbol{b}^{T}A^{-1}\boldsymbol{b}}$。代入得极小值为 $-\sqrt{\boldsymbol{b}^{T}A^{-1}\boldsymbol{b}}$。

论文题。

题目大意：给两个字符串，问它们分别无限循环后是否相等。

题解：考虑前 $|a|+|b|$ 个字符，若无失配，显然 $|a|,|b|$ 分别是它的周期，根据弱周期引理，$\gcd(|a|,|b|)$ 也是它的周期，显然永远相等。

$(\text{mod}+1)(\text{mod}-1)$ 似乎是周期，但是不会证。然后卡常就过了。