统计数组 题解

思路

任意数组都能不断删除第一个元素，因此至少有一种删除序列。删除序列唯一，当且仅当在数组尚未变化时，除第一个位置外没有其他可删位置；递归应用这一条件，可得长度为 $k$ 的非模糊数组必须满足第 $i$ 个元素能被每个不超过 $i$ 的质数整除。

令 $P_i$ 为不超过 $i$ 的所有不同质数之积，则第 $i$ 个元素有 $\lfloor m/P_i\rfloor$ 种选择。因此长度为 $k$ 的非模糊数组数为

$$u_k=\prod_{i=1}^k\left\lfloor\frac m{P_i}\right\rfloor.$$

长度为 $k$ 的数组总数为 $m^k$，所以把 $m^k-u_k$ 对所有 $k$ 求和即可。$P_i>m$ 后因子为零，后续 $u_k$ 都为零。

做法

子任务 1 枚举所有数组，并在每个当前状态枚举所有满足最大公约数条件的删除位置，搜索到两条路径即可判为模糊。

子任务 2 对每个 $i$ 从头乘起所有不超过 $i$ 的质数，再按公式更新乘积。

完整做法用筛法判断 $i$ 是否为质数，只有质数出现时才把它乘入 $P_i$。乘法前判断是否会超过 $m$，避免溢出；同时迭代维护 $m^i$ 和 $u_i$。

复杂度

子任务 1 的时间复杂度为 $O(\sum_{k=1}^n m^k k!)$，空间复杂度为 $O(n)$。

子任务 2 的时间复杂度为 $O(n^2\log n)$，空间复杂度为 $O(1)$。

完整做法的时间复杂度为 $O(n\log\log n)$，空间复杂度为 $O(n)$。