30分求调
查看原帖
30分求调
457492
ysl_wf楼主2024/2/27 18:27
#include<bits/stdc++.h>
using namespace std;
const long long N = 2*(1 << 5), p = 10000001087;
int n;
int s[N];
unordered_map<long long, bool> f;
long long pre[N], dre[N], pw[N];
int l, r;
int ans, num;
int ank[N];
void calc(int s[], long long p){
    for(int i = 1; i <= n; i++){
        pre[i] = (pre[i-1] * 233 + s[i] ) % p;
    }
    int st[N];
    for(int i = 1; i <= n; i++){
        st[i] = s[n-i+1];
        //cout<<st[i]<<" ";
    }
    //cout<<endl;
    for(int i = 1; i <= n; i++){
        dre[i] = (dre[i-1] * 233 + st[i] ) % p;
    }
    pw[0] = 1;
    for(int i = 1; i <= n; i++){
        pw[i] = pw[i-1] * 233 % p;
    }
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &s[i]);
    }
    calc(s, p);
    for(int k = 1; k <= n; k++){
        f.clear();
        for(int i = 1; i + k - 1 <= n; i += k){
            l = i, r = i + k - 1;
            long long t = ((pre[r] - pre[l-1]*pw[r-l+1]%p)%p + p)%p;
            r = n - i + 1, l = r - k + 1;
            long long h = ((dre[r] - dre[l-1]*pw[r-l+1]%p)%p + p)%p;
            // if(k == 2){
            //     cout<<s[i]<<" "<<s[i+1]<<":"<<endl;
            //     cout<<t<<" "<<h<<endl;
            // }
            if(f.count(t)||f.count(h)) continue;
            else{
                f[t] = true;
                //if(k == 2) cout<<i<<":"<<s[i]<<endl;
            }
        }
        if(ans < f.size()){
            ans = f.size(), num = 0;
            ank[++num] = k;
        }
        else if(ans == f.size()) ank[++num] = k;
    }
    printf("%d %d\n", ans, num);
    for(int i = 1; i <= num; i++){
        printf("%d ", ank[i]);
    }
    return 0;
}
2024/2/27 18:27
加载中...