首先很容易想到差分约束

一个条件相当于 $x_i-x_j\le w(i,j)\iff x_i\le w(i,j)+x_j$，考虑从 $j$ 到 $i$ 连边，边权为 $w(i,j)$

考虑某个 $x_i-x_j$ 最小是多少，发现其实就是图中 $i\to j$ 的最短路的相反数。

因此，设 $\text{dis}(i,j)$ 表示 $i\to j$ 的最短路长度，那么我们只需要找到 $\min_{j\neq i}\text{dis}(i,j)$ 即可。

考虑分治。定义 $\text{solve}(l,r)$ 表示计算 $[l,r]$ 内每个点对 $[l,r]$ 内自己的贡献；设 $mid=(l+r)/2$，我们建一个源点 $s$ 并向每个 $x\in[l,mid]$ 连边，从 $s$ 开始跑 SPFA，就算出了 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。

同理也可以算出 $[mid+1,r]$ 到 $[l,mid]$ 的贡献；分治的边界是 $l=r$，此时直接返回即可。可以发现分治完成之后，我们就算出了 $[1,n]$ 中每个点的答案。

代码实现的方式大概是对每一位分 $0,1$ 考虑，和分治本质是等价的。

代码并不难写，不到 100 行，一张图就能截下来

COGS 不支持 Markdown，有些格式用不了，推荐到我的博客阅读。

Observation 1：从大到小，遇到 1 就操作，这样的操作次数最少。

证明：显然。

Observation 2：设上述结论得出的操作序列为 $p_1\sim p_m$，则对于每一次随机操作，如果操作的 $i\in p$，则 $m\gets m-1$，反之 $m\gets m+1$。

证明：因为操作顺序不影响结果，所以若 $i\in p$，则最少操作次数 -1。

反之手动模拟，如果 $i\notin p$，那么操作序列就要新增 $i$，操作次数 +1。

也就是说，答案只和 $m$ 的大小有关。

据此，设 $f_i$ 表示当前状态最少操作次数为 $i$ 时的期望答案。

有：

$$\begin{cases}f_i=i, & i\le k\\f_i=\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1, & \rm Otherwise\end{cases}$$

不知道有没有 MO 大神能解这个函数方程阿，反正我搞不出来这个东西，讲一下在洛谷题解里看到的神奇方法。

（upd：看到一种叫线性高消的神奇做法，算是高斯消元的变种，因为每个方程只有 3 项，所以可以 $\mathcal O(n)$ 算出来方程组的解）

考虑转化为更一般的形式，通常来讲期望递推都可以化简为 $f_i=f_{i-1}+b_i$ 的形式。

那么不妨设 $b_i=f_i-f_{i-1}$ 即 $f_i=f_{i-1}+b_i$，其中 $b_i$ 未知，把它带进方程解出来：

$$\begin{aligned}f_i & =\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1\\& = \frac{i}{n}(f_{i}-b_i)+\frac{n-i}{n}(f_i+b_{i+1})+1\end{aligned}$$

化简得：

$$b_i=\frac{(n-i)b_{i+1}+n}{i}$$

显然，$f_n=f_{n-1}+1$，故 $b_n=1$，先递推出 $b$，然后再推 $f$ 即可。

因为要求 $1\sim n$ 的约数，故时间复杂度为 $\mathcal O(n\ln n)$

感觉是比较基础的多项式题，但我还是因为弱智错误调了一晚上,wtcl。

令 $q$ 的下标为 $0$，以下均在 $(mod\ x^n)$ 意义下运算。

首先构造生成函数，有

\[ \sum_{i \ge 0} { E_i x^i } = \sum_{i \ge 0} { \; \Big[ \; \sum_{j<i}{ \frac{q_j}{(i-j)^2}} - \sum_{j>i}{ \frac{q_j}{(j-i)^2}} \; \Big] \; x^i } \]

\[ \qquad\qquad\qquad\qquad\;\;\, =  \sum_{i \ge 0} { \; \Big[ \; \sum_{j<i}{ \frac{q_j}{(i-j)^2}} \; \Big] \; x^i } - \sum_{i \ge 0} { \; \Big[ \; \sum_{j>i}{ \frac{q_j}{(j-i)^2}} \; \Big] \; x^i }\]

先看前半部分，有

\[ \sum_{i \ge 0} { \; \Big[ \; \sum_{j<i}{ \frac{q_j}{(i-j)^2}} \; \Big] \; x^i } = \sum_{i \ge 0} { \; \Big[ \; \sum_{j+k=i,k \gt 0}{ \frac{q_j}{k^2}} \; \Big] \; x^i } \]

\[ \qquad\qquad\qquad\qquad\qquad\quad\;\; = \Big[ \; \sum_{i \ge 0} { q_i x^i } \; \Big] \; \Big[ \; \sum_{i \gt 0} { \frac{1}{i^2} x^i } \; \Big] \]

对于后半部分，将 $q$ 翻转即可。

使用 $FFT$ 进行卷积，时间复杂度 $O(n \log n)$。

波特题。strong。

首先发现 A,B 之间互不影响，考虑枚举分割线 $i$，定义 $f(i)$ 表示以 $i$ 为结尾的 AA 串个数，$g(i)$ 表示以 $i$ 为开头的 AA 串个数。则答案为 $\sum\limits_{i=1}^{n-1} f(i)g(i+1)$。

然后发现直接 hash $\mathcal O(n^2)$ 求 $f(i),g(i)$ 就能拿 95pts，考场上就不用考虑正解了，直接冲 hash。但是练习还是要学一下的。

观察 AA 串中，两个 A 串的开头距离为 $|A|$。

考虑枚举 $w=|A|$，用一个波特才能想到的技巧：每隔 $w$ 撒一个点。这样每个 AA 串恰经过相邻两点。

设相邻两点分别为 $x,y$，定义 $\mathrm{lcp}(x,y)$ 表示以 $x,y$ 为开头的后缀的最长公共前缀，$\mathrm{lcs}(x,y)$ 表示以 $x,y$ 为结尾的前缀的最长公共后缀。

画个图就会发现，若有 AA 串经过 $x,y$，则必有 $\mathrm{lcp}(x,y)+\mathrm{lcs}(x,y)\ge w$，且这是 AA 串存在的充要条件。

然后又发现，$\mathrm{lcp}(x,y)+\mathrm{lcs}(x,y)$ 可能比 $w$ 大，此时有连续的一段点是 AA 串的开头/结尾，用两个差分数组维护即可。

时间复杂度：$\mathcal O(n(\log n+\ln n))$。

拒绝「命运」的安排。

小清新题。

这题给我最大的启示就是：不要被经验限制，开放思维，尝试不同的角度，一些平平无奇的性质可能就是解题的关键。

首先注意到，题目中的限制很可以容斥的样子。但事实上，如果一直将思维卡在容斥，这题就真的做不出来了。

我的思路比较清奇，我一开始想到的是 dp，将限制条件存入 $u$ 节点的 std::vector，然后一遍 dfs 算出来。

然而这样想同样存在一个问题，就是 $v$ 的分布不好处理。你会发现在这种思路中，我们几乎没办法确定方案。

归根结底是这样的 dp 过程能利用的有效信息太少，状态不好设计和转移。考虑正难则反。

不难发现，对于两组限制 $(u_1,v)$ 和 $(u_2,v)$，不妨设 $\mathrm{dep}(u_1)\le \mathrm{dep}(u_2)$，此时只用考虑 $u_2$ 的限制。

通过这个小思考，我们发现可以将此时还未处理到的最深的上节点的深度存入状态，进行转移。

令 $f(u,i)$ 表示处理了 $u$ 的子树，此时最深的未满足的限制的上节点深度为 $i$ 的方案数。

考虑加入一个子树，枚举 $u\to v$ 这条树边的权值：

权值为 1：则 $v$ 以上的限制全部被满足，最大深度仍由 $u$ 的子树提供，即 $f(u,i)\gets f(u,i)\times \sum\limits_{k=0}^{\mathrm{dep}(u)} f(v,k)$。

权值为 0：此时 $i$ 有可能是由 $u$ 的子树取到，也可能是由 $v$ 的子树取到，故 $f(u,i)\gets f(u,i)\times \sum\limits_{k=0}^{i}f(v,k)+f(v,i)\times \sum\limits_{k=0}^{i-1} f(u,k)$。

其中第二个和式上边界 -1 的原因是 $f(u,i)\times f(v,i)$ 已经在第一个和式中计算过，避免重复。

综上，$f(u,i)\gets f(u,i)\times \sum\limits_{k=0}^{\mathrm{dep}(u)} f(v,k)+f(u,i)\times \sum\limits_{k=0}^{i}f(v,k)+f(v,i)\times \sum\limits_{k=0}^{i-1} f(u,k)$。

直接 dp 可以获得 64pts，发现有效节点不多，把虚树建出来就可以获得 72pts，但我并不会建虚树。

（当然这题数据水，一部分出题人想不到的 $\mathcal O(n^2)$ 解法没被卡，甚至铃酱的 $\mathcal O(n^2\log n)$ 做法被放过去了，这很 CCF）

注意到这个 dp 的状态和深度有关，而且涉及求和，这正是线段树合并擅长的。

综上，使用线段树合并进一步优化 dp，时间复杂度 $\mathcal O(n\log \mathrm{dep})$，其中 $\rm dep$ 为深度最大的节点深度。

神秘链接

首先发现 $f_i=\sum_{j=1}^m f_{i-j}$。

$m\le 5$，所以可以 $\mathcal{O(m^3\log n)}$ 计算 $f(n)$。

以 $m=3$ 为例：

$$\begin{bmatrix}f_n & f_{n-1} & f_{n-2}\end{bmatrix}\times \begin{bmatrix}1 & 1 & 0\\1 & 0 & 1\\1 & 0 & 0\end{bmatrix}=\begin{bmatrix}f_{n+1} & f_n & f_{n-1}\end{bmatrix}$$

撕烤如何计算 $g$。根据矩阵的结合律，先考虑转移矩阵的计算，最后再整体乘上初始矩阵。

考虑这样一个事实：$f(x+y)=G^{x+y}=G^x\times G^y=f(x)\times f(y)$，其中 $G$ 为转移矩阵。

基于此，可以 dp 求解原数字串的划分。

比如：$g(123)=g(12)\times f(3)+g(1)\times f(23)+f(123)$。

这样求解的前提是我们知道原串每个子段的 $f$ 值，这个可以递推求解。

设 $D_{i,j}=f(s_{i\sim j})$，则：

$$D_{i,j}=\begin{cases}f(s_i), & \mathrm{if}\ i=j\\f(s_i\times 10^{j-i})\times D_{i+1,j}, & \mathrm{Otherwise}\end{cases}$$

则有：

$$g_i=\sum_{j=0}^{i-1} g_j\times D_{j+1,i}$$

预处理 $D_{i,j}$ 之前先算出来 $f(c\times 10^k)$，时间复杂度可以做到 $\mathcal{O(n^2m^3)}$，我这里写少了，只处理了 $f(10^k)$，不过开 O2 也可以过。