[Codeforces Round #323(Div.1)] 582C-Superior Periodic Subarrays

一道有趣的数学题

题目链接(582C)

来说说这个题吧~

首先在纸上画画可以知道:对于一个数 $a_i$,如果其在 Superior Periodic Subarrays 内(以下简称SPS),那么他要作比较的数与这个 SPS 的起始位置 $l$ 是没有关系的,只和 $n$ 与 $s$ 有关。

那么对于这个数,究竟要哪些数作比较呢?实际上,对于这个数而言,以 $gcd(n,s$ 为间隔 $gap$,那么实际上我们每次都往后跳 $gap$ 个数,就是它要比较的数。比如说 1 2 3 4 5 6(​$n=6$),那么设当前 ,那么由于 ​$gap=\gcd(n,s)=\gcd(6,2)=2$,若数字 $3$ 在 SPS 内,那么其要作比较的数就是 $1,2,3$。而显然,因为 $5>3$,所以 $3$ 不可能在 SPS 内。

这就启发我们:我们可以根据一个 $gap$ 对这 $n$ 个数分组,对于每一组都是 $\frac{n}{gap}$ 个数。还是比如说 1 2 3 4 5 6,然后 $gap=2$,那么我们就可以分成 1 3 5 和 2 4 6。因为奇数不可能和偶数作比较。然后对于每一组,显然只有组中最大的数才可能在 SPS 内。于是我们可以将每一组最大的数(可能有多个)设为 $1$,其他的数设为 $0$,这样整个数组转化成了 $01$ 序列,然后就统计连续的 ​$1$ 对答案的贡献即可。

不过要注意一种情况:1 2 1 2,当 $gap=2$ 的时候,整个序列转化成了 1 1 1 1,但显然答案就不是直接统计。我们可以将数组开两倍,然后再分开来统计即可。

综上,由于 $gap$ 可以通过枚举 $n$ 的因子,然后后面每次处理都是 $\mathcal{O}(n)$ 的,那么总的复杂度为 $\mathcal{O}(n\sigma (n))$

 

发表评论