Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <map>
- #include <set>
- #include <cmath>
- #include <queue>
- #include <stack>
- #include <bitset>
- #include <cstdio>
- #include <random>
- #include <vector>
- #include <fstream>
- #include <iomanip>
- #include <numeric>
- #include <iostream>
- #include <algorithm>
- #include <unordered_set>
- #include <unordered_map>
- using namespace std;
- #define int long long
- const int C = 20;
- const int MAXN = (int)1e6 + 5;
- const long long INF = (long long)1e18;
- const double PI = 3.1415926535897;
- const int k = 1000003, mod = 1e9 + 7, mod1 = 228228227;
- vector<int> h(MAXN), h1(MAXN), rh(MAXN), rh1(MAXN), p(MAXN), p1(MAXN);
- int mul(int a, int b) {
- return a * b % mod;
- }
- int minu(int a, int b) {
- if (a >= b) {
- return a - b;
- } else {
- return a - b + mod;
- }
- }
- int mul1(int a, int b) {
- return a * b % mod1;
- }
- int minu1(int a, int b) {
- if (a >= b) {
- return a - b;
- } else {
- return a - b + mod1;
- }
- }
- int get(int l, int r) {
- return minu(h[r], mul(h[l], p[r - l]));
- }
- int get1(int l, int r) {
- return minu1(h1[r], mul1(h1[l], p[r - l]));
- }
- int rget(int l, int r) {
- return minu(rh[r], mul(rh[l], p[r - l]));
- }
- int rget1(int l, int r) {
- return minu1(rh1[r], mul1(rh1[l], p[r - l]));
- }
- void solve() {
- int n, m;
- cin >> n >> m;
- vector<int> a(n);
- for (int &i : a) {
- cin >> i;
- }
- h1[0] = 0;
- h[0] = 0;
- rh[0] = 0;
- rh1[0] = 0;
- for (int i = 0; i < a.size(); ++i) {
- h[i + 1] = (mul(h[i], k) + a[i]) % mod;
- rh[i + 1] = (mul(rh[i], k) + a[a.size() - i - 1]) % mod;
- h1[i + 1] = (mul1(h1[i], k) + a[i]) % mod1;
- rh1[i + 1] = (mul1(rh1[i], k) + a[a.size() - i - 1]) % mod1;
- }
- vector<int> ans = {n};
- for (int i = 1; i <= n / 2; ++i) {
- // cout << i << endl;
- // cout << get(0, i) << ' ' << rget(n - 2 * i, n - i) << '\n';
- // cout << mul(get(0, i), p[n - i]) << ' ' << mul(rget(n - 2 * i, n - i), p[i]) << ' ' << mul1(get1(0, i), p[n - i]) << ' ' << mul1(rget1(n - 2 * i, n - i), p[i]) << '\n';
- if (get(0, i) == rget(n - 2 * i, n - i) && get(0, i) == rget(n - 2 * i, n - i)) {
- ans.emplace_back(n - i);
- }
- }
- sort(ans.begin(), ans.end());
- for (int i : ans) {
- cout << i << ' ';
- }
- }
- int32_t main() {
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- p[0] = 1;
- for (int i = 1; i < MAXN; ++i) {
- p[i] = (p[i - 1] * k) % mod;
- }
- int ttt = 1;
- //cin >> ttt;
- while (ttt--) {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment