「Daniel13265 的公开赛」题解【悔改】

这是「Daniel13265 的公开赛」的官方题解。 --- ## 子任务 $1$ 直接枚举配对的木棍即可。 ## 子任务 $2,4,5$ 设长度为 $i$ 的木棍的个数为 $b_i$，那么 $x$ 作为最终的木棍长度最多可能出现的次数 $$f_x=\left\lfloor\frac12\sum_{i+j=x}\min\left(b_i,b_j\right)\right\rfloor$$ 暴力算这个式子即可，算法时间复杂度为 $\mathcal O\left(m^2\right)$。 ## 子任务 $3$ 注意到上式中 $b_i\ne0$ 的 $i$ 的个数最多只有 $n$ 个，于是可以将 $b_i\neq0$ 的 $i$ 的值统计出来，再用这 $\mathcal O(n)$ 个数计算答案。时间复杂度 $\mathcal O\left(\min^2(n,m)\right)$。 ## 子任务 $6$ 发现上面的式子很像卷积，只是要计算 $\min$ 的卷积。 于是考虑将上式转化一下，枚举一下小于等于 $\min\left(b_i,b_j\right)$ 的数： $$\begin{aligned}f_x&=\left\lfloor\frac12\sum_{i+j=x}\sum_{k=1}^{n}\left[b_i\geq k\right]\left[b_j\geq k\right]\right\rfloor\\&=\left\lfloor\frac12\sum_{k=1}^{n}\sum_{i+j=x}\left[b_i\geq k\right]\left[b_j\geq k\right]\right\rfloor\end{aligned}$$ 然后就可以愉快地乘法卷积了~~~ 但是，问题在于这么算的时间复杂度是 $\mathcal O(nm\log m)$ 的。 优化方式也不难：考虑到**子任务** $3$ 的思路，发现对于一个给定的 $t$，大于 $t$ 的 $b_i$ 的 $i$ 的个数只有 $\mathcal O\left(\min\left(\dfrac nt,m\right)\right)$ 个，于是小于等于 $t$ 的部分使用卷积，而大于 $t$ 的部分直接暴力计算即可。 这个算法的总时间复杂度为 $\mathcal O\left(tm\log m+\left(\dfrac nt\right)^2\right)$ ，当 $t=\sqrt[3]{\dfrac{n^2}{m\log m}}$ 时有最小值 $\mathcal O\left((nm\log m)^\frac23\right)$。实际上，由于卷积部分常数较大，当 $t$ 小于该值时程序运行效率更高。