Salvens

ADSAF

Aug 11th, 2023
1,030
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.69 KB | None | 0 0
  1. #include <map>
  2. #include <set>
  3. #include <cmath>
  4. #include <queue>
  5. #include <stack>
  6. #include <bitset>
  7. #include <cstdio>
  8. #include <random>
  9. #include <vector>
  10. #include <fstream>
  11. #include <iomanip>
  12. #include <numeric>
  13. #include <iostream>
  14. #include <algorithm>
  15. #include <unordered_set>
  16. #include <unordered_map>
  17.  
  18. using namespace std;
  19.  
  20. #define int long long
  21.  
  22. const int C = 20;
  23. const int MAXN = (int)1e6 + 5;
  24. const long long INF = (long long)1e18;
  25. const double PI = 3.1415926535897;
  26. const int k = 1000003, mod = 1e9 + 7, mod1 = 228228227;
  27. vector<int> h(MAXN), h1(MAXN), rh(MAXN), rh1(MAXN), p(MAXN), p1(MAXN);
  28.  
  29. int mul(int a, int b) {
  30.     return a * b % mod;
  31. }
  32.  
  33. int minu(int a, int b) {
  34.     if (a >= b) {
  35.         return a - b;
  36.     } else {
  37.         return a - b + mod;
  38.     }
  39. }
  40.  
  41. int mul1(int a, int b) {
  42.     return a * b % mod1;
  43. }
  44.  
  45. int minu1(int a, int b) {
  46.     if (a >= b) {
  47.         return a - b;
  48.     } else {
  49.         return a - b + mod1;
  50.     }
  51. }
  52.  
  53. int get(int l, int r) {
  54.     return minu(h[r], mul(h[l], p[r - l]));
  55. }
  56.  
  57. int get1(int l, int r) {
  58.     return minu1(h1[r], mul1(h1[l], p[r - l]));
  59. }
  60.  
  61. int rget(int l, int r) {
  62.     return minu(rh[r], mul(rh[l], p[r - l]));
  63. }
  64.  
  65. int rget1(int l, int r) {
  66.     return minu1(rh1[r], mul1(rh1[l], p[r - l]));
  67. }
  68.  
  69. void solve() {
  70.     int n, m;
  71.     cin >> n >> m;
  72.     vector<int> a(n);
  73.     for (int &i : a) {
  74.         cin >> i;
  75.     }
  76.     h1[0] = 0;
  77.     h[0] = 0;
  78.     rh[0] = 0;
  79.     rh1[0] = 0;
  80.     for (int i = 0; i < a.size(); ++i) {
  81.         h[i + 1] = (mul(h[i], k) + a[i]) % mod;
  82.         rh[i + 1] = (mul(rh[i], k) + a[a.size() - i - 1]) % mod;
  83.         h1[i + 1] = (mul1(h1[i], k) + a[i]) % mod1;
  84.         rh1[i + 1] = (mul1(rh1[i], k) + a[a.size() - i - 1]) % mod1;
  85.     }
  86.  
  87.     vector<int> ans = {n};
  88.     for (int i = 1; i <= n / 2; ++i) {
  89. //        cout << i << endl;
  90. //        cout << get(0, i) << ' ' << rget(n - 2 * i, n - i) << '\n';
  91. //        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';
  92.         if (get(0, i) == rget(n - 2 * i, n - i) && get(0, i) == rget(n - 2 * i, n - i)) {
  93.             ans.emplace_back(n - i);
  94.         }
  95.     }
  96.     sort(ans.begin(), ans.end());
  97.     for (int i : ans) {
  98.         cout << i << ' ';
  99.     }
  100. }
  101.  
  102. int32_t main() {
  103. //    freopen("input.txt", "r", stdin);
  104. //    freopen("output.txt", "w", stdout);
  105.     ios_base::sync_with_stdio(false);
  106.     cin.tie(nullptr);
  107.     cout.tie(nullptr);
  108.     p[0] = 1;
  109.     for (int i = 1; i < MAXN; ++i) {
  110.         p[i] = (p[i - 1] * k) % mod;
  111.     }
  112.     int ttt = 1;
  113.     //cin >> ttt;
  114.     while (ttt--) {
  115.         solve();
  116.     }
  117.     return 0;
  118. }
Advertisement
Add Comment
Please, Sign In to add comment