来说说这个题吧~
，如果其在 Superior Periodic Subarrays 内（以下简称SPS），那么他要作比较的数与这个 SPS 的起始位置 $l$ 是没有关系的，只和 $n$ 与 $s$ 有关。
那么对于这个数，究竟要哪些数作比较呢？实际上，对于这个数而言，以 $\gcd(n,s)$ 为间隔 $gap$，那么实际上我们每次都往后跳 $gap$ 个数，就是它要比较的数。比如说 1 2 3 4 5 6（$n=6$），那么设当前 $s=2$，那么由于 $gap=\gcd(n,s)=\gcd(6,2)=2$，若数字 $3$ 在 SPS 内，那么其要作比较的数就是 $1,3,5$。而显然，因为 $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$
综上，由于 $gap$ 可以通过枚举 $n$ 的因子，然后后面每次处理都是 $\mathcal{O}(n)$ 的，那么总的复杂度为 $\mathcal{O}(n\sigma (n))$
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
using namespace std;
const int N = 400050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
printf("\nTime used: %.6lf(s)\n", ((double)TIME_END - TIME_START) / CLOCKS_PER_SEC);
system("pause");
#endif
}
int n;
int a[N], f[N], h[N];
ll ans;
vector<int> g[N];
inline ll work(int gap)
{
mem(f, 0, (n << 1), int);
mem(h, 0, (n << 1), int);
for (int i = 0; i < gap; ++i)
{
int mx = 0;
for (int j = i; j < n; j += gap)
{
mx = max(mx, a[j]);
}
for (int j = i; j < n; j += gap)
{
if (mx == a[j])
f[j] = 1;
}
}
for (auto i : g[gap])
h[i]++;
for (int i = 0; i < (n << 1); ++i)
h[i + 1] += h[i];
for (int i = 0; i < n; ++i)
f[i + n] = f[i];
for (int i = 1; i < (n << 1); ++i)
if (f[i])
f[i] += f[i - 1];
ll ret = 0;
for (int i = n; i < (n << 1); ++i)
{
ret += h[f[i]];
}
return ret;
}
void solve()
{
cin >> n;
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i < n; ++i)
g[__gcd(i, n)].pb(i);
for (int i = 1; i < n; ++i)
{
if (n % i != 0)
continue;
ans += work(i);
}
cout << ans << endl;
}
int main()
{
TIME_START = clock();
int Test = 1;
// cin >> Test;
while (Test--)
solve();
TIME_END = clock();
program_end();
return 0;
}
Comments NOTHING