日记

Sat Mar 29 2025

3 分钟

529 字

谁说注定失败？

题意：对于 $[l,r]$ 区间内的每个数，输出它的最小质因子。 $l,r \le 10^{12},r - l + 1 \le 10^6$ 。

首先就想到欧拉筛筛出 $[2,10^6]$ 的质数，然后对于每个暴力判断。但是我还是小看了 $[999 \, 999 \times 10^6,10^{12}]$ 这个区间内的质数数量，不出意外的 T 了。

考虑预处理答案。枚举每个质数 $i$ ，然后枚举 $i$ 在 $[l,r]$ 内的每个倍数，将它的答案置为 $i$ ，时间复杂度 $O(n \ln n)$ ， $n$ 表示区间长度。

大模拟。

多大了还出大模拟？

我们有神秘小结论：我们将每个硝硼铀排序，我们称硝硼铀 $i$ 比硝硼铀 $j$ 小，当且仅当 $\min\{a_i,b_j\} < \min\{a_j,b_i\}$ 。按照这个排序就是了。

然而这个是错误的。cwoi 的数据是真的水。

用心扒题，用脚造数据。~~怎么和 CCF 一样~~

我们需要矩阵优化。

首先一眼 dp 方程：设 $dp_{i,j}$ 表示前 $i$ 个数已经填好，第 $[i - j + 1,i]$ 全是 $\texttt{A}$ 的方案数。有显然的转移：

\begin{aligned} 1 \times dp_{i - 1,0} + 1 \times dp_{i - 1,1} + 1 \times dp_{i - 1,2} & = dp_{i,0} \\ 1 \times dp_{i - 1,0} + 0 \times dp_{i - 1,1} + 0 \times dp_{i - 1,2} & = dp_{i,1} \\ 0 \times dp_{i - 1,0} + 1 \times dp_{i - 1,1} + 0 \times dp_{i - 1,2} & = dp_{i,1} \\ \end{aligned}

可以写成矩阵形式：

\begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \times \begin{bmatrix} dp_{i - 1,0} \\ dp_{i - 1,1} \\ dp_{i - 1,2} \end{bmatrix} = \begin{bmatrix} dp_{i,0} \\ dp_{i,1} \\ dp_{i,2} \end{bmatrix}

直接写矩阵快速幂优化即可。

没啥可谈的。现在似乎只有又臭又长的世界任务能够提起我的兴趣了。