PikMike

Untitled

Jan 2nd, 2016
292
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.19 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <set>
  6. #include <string.h>
  7. #include <math.h>
  8. #include <queue>
  9.  
  10. #define pb push_back
  11. #define sz size
  12. #define ll long long
  13. #define fs first
  14. #define sc second
  15. #define mp make_pair
  16. #define bg begin
  17. #define ers erase
  18. #define ins insert
  19. const int INF = 2147483647;
  20. const int MOD = 1000000007;
  21.  
  22. using namespace std;
  23.  
  24. ll base1 = 1000000009, base2 = 1000000007;
  25.  
  26. int main(){
  27.     //freopen("input.txt", "r", stdin);
  28.     freopen("cubes.in", "r", stdin);
  29.     freopen("cubes.out", "w", stdout);
  30.     int n, m;
  31.     ll t;
  32.     scanf("%d%d", &n, &m);
  33.     ll p = m + 1;
  34.     vector<ll> a, po1, po2;
  35.     for (int i = 0; i < n; i++){
  36.         scanf("%lld", &t);
  37.         a.pb(t);
  38.     }
  39.     po1.pb(1);
  40.     po2.pb(1);
  41.     for (int i = 1; i <= n; i++){
  42.         po1.pb(po1[i - 1] * p % base1);
  43.         po2.pb(po2[i - 1] * p % base2);
  44.         //cout << po1[i] << " " << po2[i] << "\n";
  45.     }
  46.     vector<pair<ll, ll> > h1, h2;
  47.     h1.pb(mp(a[0], a[0]));
  48.     h2.pb(mp(a[n - 1], a[n - 1]));
  49.     for (int i = 1; i < n; i++){
  50.         h1.pb(mp((a[i] * po1[i] % base1 + h1[i - 1].fs) % base1, (a[i] * po2[i] % base2 + h1[i - 1].sc) % base2));
  51.         h2.pb(mp((a[n - i - 1] * po1[i] % base1 + h2[i - 1].fs) % base1, (a[n - i - 1] * po2[i] % base2 + h2[i - 1].sc) % base2));
  52.     }
  53.     pair<ll, ll> t1, t2;
  54.     vector<int> ans;
  55.     for (int i = 1; i <= n / 2; i++){
  56.         t1.fs = h1[i].fs;
  57.         t1.sc = h1[i].sc;
  58.         //cout << i << " " << n - i << " " << n - i * 2 << "\n";
  59.         t2.fs = h2[n - i].fs;
  60.         if (n - i * 2) t2.fs -= h2[n - i * 2 - 1].fs;
  61.         t2.sc = h2[n - i].sc;
  62.         if (n - i * 2) t2.sc -= h2[n - i * 2 - 1].sc;
  63.         if (t2.fs < 0) t2.fs += base1;
  64.         if (t2.sc < 0) t2.sc += base2;
  65.         //cout << t1.fs * po1[n - 2 * i] << " " << t2.fs << " " << t1.sc * po2[n - 2 * i] << " " << t2.sc << " " << i << "\n";
  66.         if (t1.fs * po1[n - 2 * i] % base1 == t2.fs && t1.sc * po2[n - 2 * i] % base2 == t2.sc)
  67.             ans.pb(n - i);
  68.     }
  69.     reverse(ans.bg(), ans.end());
  70.     ans.pb(n);
  71.     for (int i = 0; i < ans.sz(); i++)
  72.         cout << ans[i] << " ";
  73.     return 0;
  74. }
Add Comment
Please, Sign In to add comment