date: 2020.07.12 12:00-17:00

practice link

题目大意：定义一个字符串的 B 函数为字符串到相同长度非负整数序列的映射，第 $i$ 个整数表示字符串中在 $i$ 前面与 $i$ 字符相同的字符之间的最小距离，如果前面没有和自己一样的字符则记为 0。求每个后缀的 B 序列的排名。

题解：由于字符集大小最大为 2，会发现经过函数 B 计算后，最多只会有俩 0。第一个字符对应的 B 必然是 0，接下来与第一个字符不同的位置上对应的 B 也是 0。而且这两个 0 之间也必然都是 1，因为前面只有一种字符。

因此在所有的后缀中，函数值的两个 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)$ 似乎是周期，但是不会证。然后卡常就过了。

题目大意：给个费用流的图，费用知道但是边的容量不知道，不过边的容量都一样。多次询问，问如果边的容量变成了分数 $u_i / v_i$，从源到汇跑一个单位的流量的最小费用是多少。

题解： 由于边的容量是相同的，考虑边的容量确定为 $a$ 后，在图上进行多次增广。容易发现只要能找到一条增广路，必然能跑出恰好 $a$ 份的流量，且是当前能走的增广路中，费用最小的。图没有负边权所以不用担心负环。

那既然每次增广跑走的流量也是相同的，而且等于边的容量，那我们直接以 1 为容量跑跑费用流，记录一下每次增广时的费用。

对于询问 $u_i / v_i$，若大于或等于 $1$ 那我们直接用第一次增广时的费用回答就好；如果为 $0$，那没得跑；如果小于 $1$，那么我们肯定得先增广 $\lfloor v_i / u_i \rfloor$ 次，需要求前面这些增广时的费用和，然后剩下的一点点流量再用劣一点的增广路跑完流量即可。

题目大意：给一个无向图，然后每个点给一个 $1$ 或 $2$ 的数 $d_u$，问有没有办法能干掉若干条边，使得新的图中，每个点的度数和给的数相同。

题解： 最后的图必然是一些链和一些环，链的两端的 $d_u$ 必然都是 $1$，剩下的都是 $2$。

考虑第 $i$ 条边选或不选，即变量 $x_i \in \{0, 1\}$，对于每个点 $u$，我们有 $\sum_{e_i\text{ incident to }u}{x_i} = d_u$。 该方程组有 0/1 的解则意味着原图能有一个方案满足度数的限制。

由于每个变量恰好只会在两个不同的方程中出现，考虑解改方程的过程，若选择了一条边，则说明我们用一个变量，盖住了两个方程右边的某个单位 “1”。每个方程右边的每个单位 “1” 只能被一个变量盖到。该过程实际上就和一般图的匹配很像了。

因此一个建立一般图匹配的方式，即将每个变量看做是匹配中的两个点、每个方程看做是匹配中的 $d_u$ 个点。在第 $i$ 条边不选的情况下，我们让变量 $x_i$ 对应的两个点匹配上；第 $i$ 条边选的情况下，我们让变量 $x_i$ 对应的两个点，分别匹配到两个不同的方程所对应的点上。

为了避免出现变量的两个点均与同一个方程对应的两个点匹配上，我们强制要求其中一个方程的两个点，只与变量的某个点相连，另一个方程的两个点只与变量另一个点相连。

综上，建立的匹配模型为，每条边拆成两个点 $e$, $e'$，每个点拆成 $d_u$ 个点。$e$ 和 $e'$ 建边。对于连接 $u$、$v$ 的边，则让 $u$ 拆的点与 $e$ 建边，$v$ 拆的点与 $e'$ 建边。

这样该匹配模型有完美匹配的情况下，就等价于前面的方程组有一组合法的解，也就等价于有一种删边的方案满足度数限制。

题目大意：求 $\int_{0}^{1} \left(x - x^2\right)^n \mathrm{d}x$。是个有理数，给出模意义下的值。

题解： $\left(x - x^2\right)^n = x^n (1-x)^n$。那我们记 $v_{a,b} = \int_{0}^{1} x^a (1-x)^b \mathrm{d}x$。

$v_{a,0} = \int_{0}^{1} x^a \mathrm{d}x = 1 / (a + 1)$。

\begin{array}{rcl} v_{a,b} &=& \int_{0}^{1} x^a (1-x)^b \mathrm{d}x \\
&=& \left(\frac{1}{a+1} x^{a+1} (1-x)^b\right)\mid_0^1 + \frac{b}{a+1} \int_{0}^{1} x^{a+1} (1-x)^{b-1} \mathrm{d}x \\
&=& \frac{b}{a+1} v_{a+1,b-1} \\
&=& \frac{b! a!}{(a+b)!} v_{a+b,0} \\
&=& \frac{b! a!}{(a+b+1)!} \end{array}

答案即为 $\frac{(n!)^2}{(2n+1)!}$。