1 条题解

  • 0
    @ 2025-3-24 17:32:21
    #include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 2e5 + 10;
    
    int n, a[N];
    int t[N][2], s[N][2], Mod[2], p[2];
    int rev[N][2], inv[N][2];
    set<int> st[2];
    
    int ksm(int a, int b, int mod) {
        int res = 1;
    
        while (b) {
            if (b & 1)
                res = 1ll * res * a % mod;
    
            b >>= 1;
            a = 1ll * a * a % mod;
        }
    
        return res;
    }
    
    void pre() {
        Mod[0] = 998244353, Mod[1] = 1e9 + 7;
        p[0] = n + 1, p[1] = n + 3;
        int tmp[2] = { 1, 1 };
    
        for (int i = 1; i <= n; ++ i)
            for (int j = 0; j <= 1; ++ j) {
                t[i - 1][j] = tmp[j], s[i][j] = (s[i - 1][j] + 1ll * tmp[j] * a[i] % Mod[j]) % Mod[j];
                tmp[j] = 1ll * tmp[j] * p[j] % Mod[j];
            }
    
        for (int i = n, k = 0; i >= 1; -- i, ++ k)
            for (int j = 0; j <= 1; ++ j)
                rev[i][j] = (rev[i + 1][j] + 1ll * a[i] * t[k][j] % Mod[j]) % Mod[j];
    
        for (int i = 0; i < n; ++ i)
            inv[i][0] = ksm(t[i][0], Mod[0] - 2, Mod[0]), inv[i][1] = ksm(t[i][1], Mod[1] - 2, Mod[1]);
    }
    
    void solve() {
        cin >> n;
    
        for (int i = 1; i <= n; ++ i)
            cin >> a[i];
    
        pre();
        int mx = 0, num = 0;
        vector <int> ans;
    
        for (int k = 1; k <= n; ++ k) {
            if (n / k < mx)
                break;
    
            int cnt = 0;
    
            for (int i = 1; i <= n; i += k) {
                if (i + k - 1 > n)
                    break;
    
                int r[2], rv[2];
    
                for (int j = 0; j <= 1; ++ j) {
                    int res = ((s[i + k - 1][j] - s[i - 1][j]) % Mod[j] + Mod[j]) % Mod[j];
                    res = 1ll * res * inv[i - 1][j] % Mod[j];
                    int res2 = ((rev[i][j] - rev[i + k][j]) % Mod[j] + Mod[j]) % Mod[j];
                    res2 = 1ll * res2 * inv[n - i - k + 1][j] % Mod[j];
                    r[j] = res, rv[j] = res2;
                }
    
                if (st[0].find(r[0]) == st[0].end() || st[1].find(r[1]) == st[1].end()) {
                    ++cnt;
                    st[0].insert(r[0]), st[0].insert(rv[0]);
                    st[1].insert(r[1]), st[1].insert(rv[1]);
                }
            }
    
            st[0].clear(), st[1].clear();
    
            if (mx == cnt)
                ++num, ans.push_back(k);
            else if (mx < cnt) {
                num = 1;
                mx = cnt;
                ans.clear();
                ans.push_back(k);
            }
        }
    
        cout << mx << " " << num << "\n";
    
        for (auto v : ans)
            cout << v << " ";
    }
    
    int main() {
        ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
        solve();
        return 0;
    }
    
    • 1

    信息

    ID
    917
    时间
    1000ms
    内存
    512MiB
    难度
    (无)
    标签
    (无)
    递交数
    0
    已通过
    0
    上传者