HNOI2019

鱼 \((\texttt{Medium} \ 3 / 7)\)

考虑枚举 \(A\) 和 \(D\)，这样 \(BC\) 和 \(EF\) 就能分开处理了。

• 统计 \(BC\) 的方案数

一对点 \(BC\) 合法的充要条件是 \(AD\) 垂直平分 \(BC\) 且 \(AD \cup BC \ne \varnothing\)，若前者成立，后者等价于 \(BC\) 中点的投影在 \(AD\) 的投影上。这就简单了，我们可以把 \(BC\) 转化为由「中垂线、中点横坐标」描述的二元组，对于每种中垂线维护一个 vector，其内按照中点横坐标从小到大排序。我们枚举 \(AD\) 时，直接在直线 \(AD\) 所对应的 vector 中二分即可。

• 统计 \(EF\) 的方案数

首先对于每个点，把其他点和它的距离离散化，设 \(cnt_{u, i}\) 表示离第 \(u\) 个点的距离离散化后为 \(i\) 的点的数量，那么询问就相当于要维护一个半平面内的 \(cnt_D\)，查询 \(\sum_i \binom{cnt_{D, i}}{2}\)。可以把所有 \(AD\) 按照极角排序，对于每个点维护两个指针即可。

时间复杂度 \(\mathcal{O}(n^2 \log n)\)。

以下是这个题代码难度评 \(7\) 分的理由：

• 本题需要手写分数类，因为斜率的差值最小是 \(10^{-18}\)，超出了 long double 的有效精度范围。
• 本题需要手写分数类，因为斜率的差值最小是 \(10^{-18}\)，超出了 long double 的有效精度范围。
• 本题需要手写分数类，因为斜率的差值最小是 \(10^{-18}\)，超出了 long double 的有效精度范围。
• 分数类需要自动化最简分数，有负数要都放在分子 / 分母上。
• 维护分数类需要非常注意横坐标相等和纵坐标相等的情况，分数类需要注意 \(0\)、\(\infty\) 和 \(0 \times \infty\) 的情况。
• 极角排序也同样需要注意横坐标相等和纵坐标相等的情况。
• 关于统计 \(EF\) 的方案数时两个指针的挪动：不能直接挪，因为可能上一个半平面还没有扫到这个点，这一个半平面直接扫过了这个点。正确的做法是先求出两个指针的目标点再挪动。

JOJO \((\texttt{Medium} \ 5 / 2)\)

首先考虑没有 \(2\) 操作的情况。

我们把 \((x, c)\) 看作一个字符，定义两个字符串 \(s = s_1s_2 \cdots s_n\) 和 \(t = t_1t_2 \cdots t_n\) 匹配当且仅当

1. \(s_1\) 的 \(c\) 和 \(t_1\) 的 \(c\) 一样；\(s_1\) 的 \(x\) 不大于 \(t_1\) 的 \(x\)。
2. 对于 \(\forall i \in [2, n]\)，有 \(s_i = t_i\)。

我们按照这样的匹配方式进行 \(\rm KMP\) 算法，跳 \(\rm fail\) 指针的过程中记录一下最多能匹配多少个字符，比如说已经匹配了 \(x\) 个字符，当前可以匹配 \(y\ (y > x)\) 个字符，当前的长度为 \(len\)，那么当前结点对答案的贡献就是 \(\sum_{i = l + 1} ^ r (len + i)\)。注意根节点如果出边为当前字符的话需要额外处理剩下的匹配，例如 \(\texttt{abaa}\) 中 \(\texttt{aa}\) 可以与 \(\texttt{a}\) 匹配产生 \(1\) 的贡献。

然后考虑 \(2\) 操作，即可持久化，主流的做法有两种。

算法一

考虑用可持久化线段树直接维护出加每个字符最终会跳到哪个点，以及所有匹配的 \(len\) 的贡献。具体地，发现 \(\rm fail\) 树上子节点的长度肯定比父节点长，所以添加 \((x, c)\) 的时候，首先从 \(\rm fail\) 树上父亲继承，然后直接把匹配 \(1 \sim c\) 个 \(x\) 字符的 \(len\) 改为当前的 \(len\) 即可。

算法二

我们有

• 定理：若长度为 \(n\) 的字符串 \(s\) 的最长 \(\rm border\) 长度为 \(m\)，且 \(m > \frac{n}{2}\)，那么 \(s\) 的所有长度 \(> \frac{n}{2}\) 的 \(\rm border\) 长度构成了一个公差为 \(n - m\) 的等差数列。

这也就是说，\(n - m\) 是 \(s\) 的 \(\rm period\)，指针只有跳进这个 \(\rm period\) 才有可能发生答案的改变。于是每次如果 \(\text{fail}_i > \frac{i}{2}\) 可以直接令 \(i \leftarrow (i - 1) \bmod \text(i - \text{fail}_i) + 1\)。这样的话每次长度必然缩小一半，我们用一个 \(\log\) 的代价，把 \(\rm KMP\) 算法变得可持久化了。

两种算法的时间复杂度均为 \(\mathcal{O}(n \log n)\)，第二种算法远好写于第一种算法。

多边形 \((\texttt{Easy} \ 3 / 2)\)

• 观察 \(1\)：\(S_0\) 中每一条多边形内部的边都和 \(n\) 相连。

这个观察比较显然。

• 观察 \(2\)：每次操作必然可以使和 \(n\) 相连的边增加一条。

证明：设除 \(1\) 以外最小的和 \(n\) 相连的点编号为 \(i\)，则 \(1\) 和 \(i\) 之间有连边。那么一定存在唯一的点 \(p \in (1, i)\) 使得 \(p\) 和 \(1, i\) 之间都有连边，那么可以对 \(1, p, i, n\) 进行操作使得 \(p\) 和 \(n\) 相连。

于是我们可以规定每一次操作必须使得一条新的边和 \(n\) 相连。

• 观察 \(3\)：一些点和 \(n\) 相连的顺序构成偏序关系，且偏序关系是二叉树森林。

证明：发现和 \(n\) 相连的点起到了分隔的作用，不妨设 \(l + 1 < r\)，且 \([l, r]\) 内只有两个端点和 \(n\) 相连。容易证明能够进行一次操作使得 \((l, r)\) 中的一个新点和 \(n\) 相连的方式只有观察 \(2\) 的证明中提及的方式。这个点选了以后又会把当前的区间分为左右两个区间，所以形成了二叉树的结构。因为初始可能有很多段，所以是二叉树森林。

• 观察 \(4\)：设对 \((u, v)\) 操作连接的边为 \((x, y)\)，且 \(x\) 是深度较大的那个，那么进行操作以后偏序关系的改变就是二叉树上 rotate(x)。

对于森林中不同位置的点分类讨论一下即可得到该结论。

首先对原本的二叉树森林求出合法的拓扑序数量，记 \(f_u\) 为以 \(u\) 为根的子树的拓扑序数量。

假设 \(x\) 是 \(y\) 的左儿子，\(x\) 的左、右儿子分别是 \(a, b\)，\(y\) 的右儿子是 \(c\)，那么原来的方案数为

\[\frac{(sz_y - 1)! f_af_bf_c}{(sz_a + sz_b + 1)sz_a!sz_b!sz_c!} \]

rotate 后的方案数为

\[\frac{(sz_y - 1)! f_af_bf_c}{(sz_b + sz_c + 1)sz_a!sz_b!sz_c!} \]

所以答案就是原答案乘上 \((sz_a + sz_b + 1) / (sz_b + sz_c + 1)\)。

关于如何找到对 \((u, v)\) 操作连接的边：发现和 \(u, v\) 都相连的点只有恰好两个，而这两个点就是我们要找的点。可以用 bitset 求，需要卡空间，可以暴力求 \(\deg\) 小的点的交集。

时空复杂度均小于 \(\mathcal{O}(n \log n + \frac{n^2}{\omega})\)，可以通过。

\(\texttt{update}\)：我是 sb，最后一步可以直接用 map 存下来，因为操作 \(l, p, r, n\) 的时候 \(l, p, r\) 两两之间的边都没有被动过，所以操作 \((l, r)\) 的时候连接的肯定是 \(p\) 与另一个点，显然 \(p\) 在二叉树上的深度更大。于是时间复杂度直接变为了 \(\mathcal{O}(n \log n)\)。

正确的开题顺序是倒序开题？

校园旅行 \((\texttt{Medium} \ 4 / 2)\)

首先考虑 \(m\) 较小的时候怎么做：我们肯定是设 \(f_{u, v}\) 表示 \((u, v)\) 的答案，那么我们只需要把 \(f_{u, v} = 1\) 的 \((u, v)\) 放在一个队列里，\(\rm BFS\) 更新即可，时间复杂度 \(\mathcal{O}(m^2)\)。

这启示我们可以考虑把边数减少至 \(\mathcal{O}(n)\) 级别。考虑 \(u \to v\) 的一条回文路径，对于其中两段对应的 \(1\)，我们可以任意调整这一段，只需要使得两边 \(1\) 的个数相等即可。

考虑所有标号为 \(1\) 的节点的导出子图的一个连通块，如果这个连通块不是二分图，则如果 \(1\) 的长度足够长（这样就不会被最短路限制），那么这个连通块内两个点之间任意长度的路径都是可以构造出来的，反之则有奇偶的要求。

这样转化的话就只和这个导出子图的连通块是否是二分图有关了。于是对于不是二分图的连通块，我们可以把它变成一棵生成树加一个自环；对于是二分图的连通块，保留一棵生成树即可。还需要考虑标号为 \(0\) 的点和标号为 \(1\) 的点之间的连边。发现这些连边也构成了一张二分图，可以沿用二分图的方法，即保留一棵生成树。

于是我们就在这三张图上跑一下，把最终得到的等价的边加入到新图中，最后在新图上 \(\rm BFS\) 即可。

时间复杂度 \(\mathcal{O}(n^2)\)。

白兔之舞 \((\texttt{Easy} \ 2 / 5)\)

设 \(cnt_m\) 表示走 \(\sum_{i = 1} ^ m x_i \le L\) 的正整数解的数量，可得

\[cnt_m = \sum\limits_{i = 0} ^ L \binom{i - 1}{m - 1} = \binom{L}{i} \]

一个组合解释是，一组 \(\sum_{i = 1} ^ {m + 1} x_i = L + 1\) 的正整数解去掉 \(x_{m + 1}\) 后唯一对应着 \(\sum_{i = 1} ^ m x_i \le L\) 的一组解。

考虑 \(n = 1\) 的情况，设 \(u = w_{1, 1}\)，则

\[ans_t = \sum\limits_{i = 0} ^ L \binom{L}{i} u^i [i \equiv t \ (\bmod k)] \]

式子的形式和 \(k \mid p - 1\) 的条件提示我们单位根反演，设 \(\omega = \omega_k\)，我们有

\[ \begin{aligned} ans_t & = \sum\limits_{i = 0} ^ L \binom{L}{i} u^i [i \equiv t \ (\bmod k)] \\ & = \sum\limits_{i = 0} ^ L \binom{L}{i} u^i \frac{1}{k} \sum\limits_{j = 0} ^ {k - 1} \omega^{j(i - t)} \\ & = \frac{1}{k} \sum\limits_{j = 0} ^ {k - 1} \omega ^ {-jt} \sum\limits_{i = 0} ^ L \binom{L}{i} u^i \omega ^ {ij} \\ & = \frac{1}{k} \sum\limits_{j = 0} ^ {k - 1} \omega ^ {-jt} (1 + u\omega^j) ^ L \\ \end{aligned} \]

令 \(f_i = (1 + u\omega^i) ^ L\)，那么 \(ans_t = (f_{\text{IDFT}})_i\)。

对于 \(n > 1\) 的情况，我们只要把 \(u\) 变为一个矩阵即可，即设转移矩阵为 \(T\)，有 \(f_i = (1 + T\omega^i) ^ L\)，这样我们得到的 \(ans\) 也是一个矩阵，输出其第 \(x\) 行 \(y\) 列的值即可。

这样做的话时间复杂度是 \(\mathcal{O}(n^3 k \log L + n^2 k \log k)\)，实测会被卡。发现 \(\rm IDFT\) 是线性变换，所以直接把所有 \(f_i\) 第 \(x\) 行 \(y\) 列的值拿出来做 \(\rm IDFT\) 即可。

因为模数不是 \(\rm NTT\) 模数，所以需要多模 \(\rm NTT\)。

因为 \(k\) 不是 \(2\) 的幂次，所以 \(\rm IDFT\) 需要 \(\rm Bluestein\) 算法实现。

时间复杂度 \(\mathcal{O}(n^3 k \log L + k \log k)\)，可以通过。

序列

不会。