Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("03")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <cstdio>
- #include <string>
- #include <vector>
- #include <map>
- #include <set>
- #include <unordered_map>
- #include <unordered_set>
- #include <queue>
- #include <deque>
- #include <cmath>
- #include <numeric>
- #include <algorithm>
- #include <ctime>
- #include <chrono>
- #include <random>
- #include <functional>
- using namespace std;
- using ll = long long;
- using db = double;
- using ldb = long double;
- using pii = pair<int, int>;
- using pll = pair<ll, ll>;
- using vint = vector<int>;
- using vll = vector<ll>;
- #define all(x) x.begin(), x.end()
- #define size(x) int(x.size())
- #define rep(x) for(int rep_i = 0; rep_i < x; ++rep_i)
- #define forp(i, s, f) for(int i = s; i < f; ++i)
- #define form(i, s, f) for(int i = s; i > f; --i)
- #define PB push_back
- #define MP make_pair
- #define F first
- #define S second
- #define elif else if
- #define dprint(x) for (auto now: x) cout << now << " "
- const int MOD = 1e9 + 7;
- const int MOD2 = 998244353;
- const int INF = 2e9 + 7;
- const ll LINF = 1e18 + 7;
- const double EPS = 1e-9;
- const long double PI = acosl(-1.0);
- bool isequal(int from1, int from2, int len, vll& h, vll& x, vll& h2) {
- return (h[from1 + len - 1] + h2[from2 - 1] * x[len]) % MOD ==
- (h2[from2 + len - 1] + h[from1 - 1] * x[len]) % MOD;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- /*cout << setprecision(x)*/
- cout << fixed;
- vector <int> s, s2;
- s.push_back(0);
- s2.push_back(0);
- int n, k;
- cin >> n >> k;
- forp(i, 0, n) {
- int x;
- cin >> x;
- s.push_back(x);
- }
- /*cin >> s;*/
- s2 = s;
- int xx = 257;
- reverse(s2.begin() + 1, s2.end());
- //int n = size(s);
- vll h(n + 1, 0);
- vll h2(n + 1, 0);
- vll x(n + 1, 0);
- x[0] = 1;
- forp(i, 1, n + 1) {
- h[i] = (h[i - 1] * xx + s[i]) % MOD;
- h2[i] = (h2[i - 1] * xx + s2[i]) % MOD;
- x[i] = (x[i - 1] * xx) % MOD;
- }
- int ln = 0;
- vector <int> ans;
- while (ln < n + 1) {
- if (isequal(1, n + 1 - ln, ln / 2, h, x, h2)) {
- ans.push_back(n - ln / 2);
- }
- ln += 2;
- }
- sort(ans.begin(), ans.end());
- dprint(ans);
- //if ((h[1 + 2 - 1] + h2[2 - 1] * x[2]) % MOD ==
- // (h2[2 + 2 - 1] + h[1 - 1] * x[2]) % MOD) {
- // cout << "!!!!!!"; //|12| 212 - 212 |21| //12212
- //}
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement