1 条题解
-
0
#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
- 上传者