Advertisement
PikMike

Untitled

Jan 2nd, 2016
348
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement