Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #pragma comment(linker, "/STACK:32000000")
- #pragma GCC optimize("O3")
- #include <stdio.h>
- #include <string.h>
- #include <memory.h>
- #include <stdlib.h>
- #include <iostream>
- #include <time.h>
- #include <algorithm>
- #include <math.h>
- #include <vector>
- #include <set>
- #include <queue>
- #include <stack>
- #include <bitset>
- #include <string>
- #include <cstring>
- #include <cassert>
- #include <fstream>
- #include <map>
- #include <unordered_map>
- #include <deque>
- using namespace std;
- #define inf 1000000007
- #define eps 1e-9
- #define mp(a, b) make_pair(a, b)
- #define llinf 2000000000000000008LL
- typedef long long ll;
- typedef unsigned u;
- typedef long double ld;
- typedef unsigned char uc;
- typedef unsigned long long ull;
- ll c1 = 1999, mod1 = 1'000'000'007;
- int n, m;
- ll arr[200005];
- ll pow1[200005];
- ll h1[200005];
- ll hinv1[200005];
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin.sync_with_stdio(0);
- cout.sync_with_stdio(0);
- cout.precision(8);
- srand(time(0));
- cin >> n >> m;
- for (int i = 1; i <= n; i++) {
- cin >> arr[i];
- }
- pow1[0] = 1;
- for (int i = 1; i <= n; i++) {
- pow1[i] = (pow1[i - 1] * c1) % mod1;
- }
- for (int i = 1; i <= n; i++) {
- h1[i] = (h1[i - 1] + arr[i] * pow1[i - 1]) % mod1;
- }
- for (int i = n; i >= 1; i--) {
- hinv1[i] = (hinv1[i + 1] + arr[i] * pow1[n - i]) % mod1;
- }
- vector <int> ans;
- for (int i = 0; i <= n / 2; i++) {
- ll H1 = h1[i];
- ll H2 = ((hinv1[i + 1] - hinv1[i + 1 + i]) % mod1 + mod1) % mod1;
- int id1 = 1, id2 = n - i - i + 1;
- if (id1 > id2) {
- swap(id1, id2);
- swap(H1, H2);
- }
- H1 = (H1 * pow1[id2 - id1]) % mod1;
- if (H1 == H2) {
- ans.push_back(n - i);
- }
- }
- }
- sort(ans.begin(), ans.end());
- for (auto &i : ans) {
- cout << i << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement