Beads 题解_牛客博客

不会算复杂度真是致命，暴力枚举 $k$ 每次计算是 $n/2+n/3+n/4+...+1$ 的，用调和级数算是 $n\log n$ 的...如果写哈希表的话能够 $n\log n$ ，或者直接拿个 $set$ 存就 $n\log n\log n$ 。进制要选好，233不能过，2333过的点会多一点，然后选13131才过了....

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
typedef unsigned long long ull;
const int N = 200010;
const ull base = 13131;
using namespace std;

int Ans, n, a[N], ans[N], cnt = 0;
ull h1[N], h2[N], p[N];
set<ull> st;

ull cal1(int l, int r) { return h1[r] - h1[l - 1] * p[r - l + 1]; }

ull cal2(int l, int r) { return h2[l] - h2[r + 1] * p[r - l + 1]; }

int ins(int x) {
    st.clear();
    for(int l = 1; l + x - 1 <= n; l += x) {
        int r = l + x - 1;
        ull ha = min(cal1(l, r), cal2(l, r));
        st.insert(ha);
    }
    return (int)st.size();
}

int main() {
    scanf("%d", &n); p[0] = 1;
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i) h1[i] = h1[i - 1] * base + a[i], p[i] = p[i - 1] * base;
    for(int i = n; i; i--) h2[i] = h2[i + 1] * base + a[i];
    for(int i = 1; i <= n; ++i) {
        int num = ins(i);
        if(num > Ans) { Ans = num; cnt = 0; }
        if(num == Ans) ans[++cnt] = i;
    }
    printf("%d %d\n", Ans, cnt);
    for(int i = 1; i <= cnt; ++i) printf("%d ", ans[i]);
    return 0;
}