2021-03-24 18:23 已编辑中山市中山纪念中学 Java

关注

【题解】牛客挑战赛48

谢罪谢罪谢罪

A, B 题的题面都出现了一些小错误，C 题题面出现了一点歧义，谢罪（
C 题题面的 $n \ge m$ 其实是笔误，但是确实不影响答案。
非常庆幸的是数据并没有锅，尽管 G 题最后其实没有人验题。

A

考虑直接预处理出 $x = 1,2,\dots,n$ 的答案。设 $f_i$ 表示前 $i$ 个数中的最大值， $g_i$ 表示前 $i$ 个数中的次大值。
一开始时令 $f_0 = g_0 = -\infty$ 。
我们考虑分类讨论 $a_i$ ：

若 $a_i \ge f_{i-1}$ ，那么令 $f_i = a_i,g_i = f_{i-1}$ 。
若 $g_{i-1} \le a_i < f_{i-1}$ ，那么令 $f_i = f_{i-1},g_i = a_i$ 。
若 $a_i < g_{i-1}$ ，那么令 $f_i = f_{i-1},g_i = g_{i-1}$ 。

询问时输出 $g_x$ 即可。

出题人题解：

【天使果冻题解】
解法1：用一个multiset<int>s维护前缀里有哪些数，那么s.end()指针往前两位则是次大值。
复杂度O(nlogn)

解法2：用两个变量分别维护最大值和次大值，在遍历的过程中更新这两个变量即可。
复杂度O(n)

B

事实上，不难发现要想最后 $1,2,\dots,n$ 都出现，当栈顶为 $i$ 时只能入栈 $i$ 或 $i+1$ 。
证明不难，考虑到如果入栈了 $j$ ，其中 $j > i+1$ ，那么此后将不再有可能入栈 $i+1$ 。

另一方面，注意到栈内的状态是不重要的，我们只关心栈顶，设它为 $i$ 那么同时只需要保证 $1,2,\dots,i$ 都在栈中即可。
这时我们的 DP 方程已经呼之欲出了。
根据套路，考虑倒序 DP，设 $f_i$ 表示当前栈顶为 $i$ ，停止时栈中包含 $i,i+1,\dots,n$ 的概率。
考虑入栈的是 $i$ 还是 $i+1$ ，则易得
$f_i = \frac{w_i f_i + w_{i+1} f_{i+1}}{\sum_{k=i}^n w_k}$

移一下项，可以得到
$f_i = \frac{w_{i+1} f_{i+1}}{\sum_{k=i+1}^n w_k}$

$O(n \log p)$ 或 $O(n)$ DP 即可，其中 $p = 10^9+7$ 。

C

注意到给 $n$ 个点连 $n-1$ 条边，若连通则必然是树。且最少连接 $n-1$ 条边才能使它们连通。
所以容易发现这张图相当于构造一片 $n$ 个结点 $n-m$ 棵树的森林。
证明可以考虑反正，如果有一个连通块大小为 $x$ ，但连接了超过 $x-1$ 条边，那么必然会有另一个大小为 $y$ 的连通块连接不到 $y-1$ 条边，从而推出矛盾。

我们注意到，给一棵无根树赋上其点数的贡献，组合意义上可以看做选定一个根（事实上这正对应了组合结构符号化中的 Pointing 构造）。
从而答案就转化为了 $n$ 个点 $n-m$ 棵有根树的森林个数。

考虑构造一个虚根 $0$ ，强制其度数为 $n-m$ 。问题就变成了钦定根且根有度数限制的有标号树个数。
根据 Prufer 序列相关结论，若 $0$ 的度数为 $n-m$ ，则 $0$ 在 Prufer 序列中出现的次数为 $n-m-1$ 。
因此首先考虑从长度为 $n+1-2=n-1$ 的 Prufer 序列中选出 $n-m-1$ 个位置为 $0$ （这等于 $\binom{n-1}{n-m-1} = \binom{n-1}m$ ），然后令剩下的 $(n-1)-(n-m-1)=m$ 个位置在 $1,2,\dots,n$ 中任意选择。根据乘法原理，将两步的结果结合起来，即为
$\binom{n-1}{m} n^m$

我们知道 $\binom{n-1}m = \frac1{m!} (n-1)^{\underline m}$ ，下降幂可以 $O(m)$ 计算，逆元也可以 $O(\log (10^9+7))$ 算出，加上一个快速幂计算 $n^m$ ，总时间复杂度为 $O(m)$ 。

D

首先使用 Floyd 预处理出全源最短路。设 ${\rm dis}(i,j)$ 表示 $i$ 到 $j$ 的最短路长度。
为了计算出牛奶结点，我们考虑计算 $h_{i,S}$ 表示 $\sum\limits_{j \in S} {\rm dis}(i,j)$ 。
这个可以简单地 $O(2^n n^2)$ 算出，当然结合一些位运算也可以做到 $O(2^n n)$ 。
然后我们需要计算出 $g_S$ 表示 $S$ 的权值。这个比较简单，此处不再赘述。

然后考虑最后一步 DP，设 $f_S$ 表示目前划分出的集合的并为 $S$ 时所有方案的权值之和。
列出转移式，会得到一个子集卷积的形式。考虑通常处理子集卷积的过程，由于我们以集合大小为阶段，所以可以同时处理这样的半在线卷积。

复杂度 $O(n^2 2^n)$ 。

当然我们容易发现问题相当于求一个集合幂级数 ${F}$ 的 $\frac1{1-F}$ 。可以直接使用经典的集合幂级数求逆做法或是直接套用形式幂级数复合集合幂级数的方法解决。题解区有朋友提到了这种做法。

E

基础比较扎实的同学应该能一眼看出来这是一个二分答案板题的加强版（

若 $l = 1,r = n$ ，则不难想到用权值线段树维护 $S(x)$ 并使用线段树上二分求答案。
扩展到一般情况，可以直接在内层套上一棵线段树维护下标。

当然并没有这么简单。线段树套线段树空间会超出限制。以下是几种可行的解决方案：

改为分块套线段树，也许能过但是极不优美，出题人并不推崇这种做法。如果没有脑子，时间复杂度为 $O(\sqrt n \log n)$ ；正常时间复杂度为 $O(\sqrt{n \log n})$ 。
改为分块套值域分块，那么根据复杂度的平衡，需要做到 $O(\sqrt n)$ 单点修改， $O(1)$ 查询前缀和。
改为树状数组套线段树，并在内层维护值域，那么查询时需要做多树二分，时间复杂度仍然为 $O(\log^2 n)$ 。
改为树状数组套线段树，并在外层维护值域，那么查询时可以使用树状数组上二分或倍增的技巧，稍微好写一些，常数可能也小一些，时间复杂度仍然为 $O(\log^2 n)$ 。
改为整体二分，也比较好写，因为需要维护的信息比较简单，这个做法唯一的弊端是离线，时间复杂度仍然为 $O(\log^2 n)$ 。

复杂度 $O((n+m)\log^2 n)$ 。

F

令 $n=|S|$ 。
显然对任意整循环串都恰好存在一个本原平方串前缀。
注意到与 $[1,r]$ 相交意味着左端点不超过 $r$ 。而若提取本原平方串后缀则字典序更小且显然也满足条件，故仅需要考虑本原平方串的贡献。

考虑枚举每个 run 中所有本质不同的本原平方串，根据 Three Squares Lemma，这样的本原平方串共有 $O(n)$ 个。

容易知道每个本质不同的本原平方串仅需要考虑第一次出现的位置即可。
于是可以将这 $O(n)$ 个本原平方串排序得到其排名，容易发现我们需要查询任意两个后缀的 LCP 长度。使用二分 + 哈希，可以做到 $O(n \log^2 n)$ ，常数优秀可能可以通过。而通过后缀数组 + ST 表可以做到 $O(n \log n)$ 。

从而对于询问就不难处理了。
可以使用并查集简单处理区间覆盖，尽管垃圾标算写了线段树。

复杂度 $O((n+m) \log n)$ 。

G

注意到 $p \equiv 1 \pmod k$ ，这提示我们考虑单位根反演。
进一步地，容易发现若能求出
$F(x) = \sum\limits_{i=1}^n x^{c(i)} \left\lfloor\frac ni\right\rfloor$

在 $\omega_k^0,\omega_k^1,\dots,\omega_k^{k-1}$ 处的值，则可直接 $O(k^2)$ 计算出答案。

事实上，若构造

$f_n(x) = \sum\limits_{d|n} x^{c(d)}$

则容易发现 $F(x) = \sum\limits_{i=1}^n f_i(x)$ 。

有趣的是，若对 $n$ 分解质因子得到 $n = \prod p_i^{c_i}$ ，则有
$f_n(x) = \prod\sum\limits_{j=0}^{c_i} x^j = \prod \frac{x^{c_i+1}-1}{x-1}$

若代入具体的一个值 $x=x_0$ ， $f_n(x_0)$ 便可以视为一个关于 $n$ 的积性函数。
使用 Min_25 筛 / 洲阁筛计算即可。
复杂度 $O\left(\frac{kn^{3/4}}{\log n}\right)$ 。

当然也存在更显然的直接计算 $O(k\sqrt n)$ 处前缀和的做法，不予赘述。

之所以说没有 $k \mid (p-1)$ 也能做，是因为你完全可以直接代入 $\left\lfloor\log_2 n\right\rfloor+1$ 个 $x$ 之后插值。加入这个条件纯粹是为了减小常数。

题外话

这个 B, C 本来是反的，朋友验了题之后建议我 swap（事实上从内测成员的表现来看，这个 C 放到 D 甚至 E 可能都不过分）。
另外其实很可能这个 G < F，不过 F 的难度全在科技，事实上几乎并没有什么思维难度。
事实上最开始的 F 也是个较为简单的偏向科技（拉格朗日反演）的多项式题，但是被吐槽数学题太多就换掉了（
另外虽然可能有些人知道我非常喜欢多项式，但是可以注意到这场的多项式浓度和难度都极低！！！我是不是很良心（