date: 2020.07.12 12:00-17:00

practice link

由于字符集大小最大为 2，会发现经过函数 B 计算后，最多只会有俩 0，第一个字符对应的 B 必然是 0，接下来与第一个字符不同的位置上对应的 B 也是 0。

那么在所有的后缀中，函数值的两个 0 靠的越近，排名越靠前；如果没有第二个零，那可以假装末尾有个零，但是排名的时候要尽可能靠前。

而对于两个 0 之后的序列的字典序大小关系，容易发现由于两个字符都出现过了，那么 0 之后的 B、即相应位置上前面与自己相同的字符的距离，不再会有变化。所以记后缀 $s_{a\ldots n}$ 的 B 序列中两个 0 的距离为 $l$，那么后面的 B 序列与原串的 B 对应的后缀是相同的，即 $B(s_{a\ldots n})_{l+1\ldots n-a} = B(s)_{a+l+1\ldots n}$。

综上，我们首先计算一下原串的 B，然后用后缀数组对 B 序列的后缀进行排序。接下来对于每个后缀 $s_{a\ldots n}$，第一关键字为该后缀中最靠前的两个不同的字符的距离（即对应 B 序列中两个 0 的距离）；第二关键字当后缀全是相同的字符时为 0，否则为 1，用来保证 B 序列实际没有第二个 0 的情况下，让较短的该后缀排名尽量靠前；第三关键字即为 $B(s)_{a+l+1\ldots n}$ 在原串 B 序列的后缀中的排名。排序。

题目大意：在 $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)$ 似乎是周期，但是不会证。然后卡常就过了。