Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2019
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.81 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #pragma comment(linker, "/STACK:32000000")
  4. #pragma GCC optimize("O3")
  5.  
  6. #include <stdio.h>
  7. #include <string.h>
  8. #include <memory.h>
  9. #include <stdlib.h>
  10. #include <iostream>
  11. #include <time.h>
  12. #include <algorithm>
  13. #include <math.h>
  14. #include <vector>
  15. #include <set>
  16. #include <queue>
  17. #include <stack>
  18. #include <bitset>
  19. #include <string>
  20. #include <cstring>
  21. #include <cassert>
  22. #include <fstream>
  23. #include <map>
  24. #include <unordered_map>
  25. #include <deque>
  26.  
  27. using namespace std;
  28.  
  29. #define inf 1000000007
  30. #define eps 1e-9
  31. #define mp(a, b) make_pair(a, b)
  32. #define llinf 2000000000000000008LL
  33.  
  34. typedef long long ll;
  35. typedef unsigned u;
  36. typedef long double ld;
  37. typedef unsigned char uc;
  38. typedef unsigned long long ull;
  39.  
  40. ll c1 = 1999, mod1 = 1'000'000'007;
  41. int n, m;
  42. ll arr[200005];
  43. ll pow1[200005];
  44. ll h1[200005];
  45. ll hinv1[200005];
  46.  
  47. int main() {
  48. ios_base::sync_with_stdio(0);
  49. cin.tie(0);
  50. cout.tie(0);
  51. cin.sync_with_stdio(0);
  52. cout.sync_with_stdio(0);
  53. cout.precision(8);
  54. srand(time(0));
  55.  
  56. cin >> n >> m;
  57. for (int i = 1; i <= n; i++) {
  58. cin >> arr[i];
  59. }
  60. pow1[0] = 1;
  61. for (int i = 1; i <= n; i++) {
  62. pow1[i] = (pow1[i - 1] * c1) % mod1;
  63. }
  64. for (int i = 1; i <= n; i++) {
  65. h1[i] = (h1[i - 1] + arr[i] * pow1[i - 1]) % mod1;
  66. }
  67. for (int i = n; i >= 1; i--) {
  68. hinv1[i] = (hinv1[i + 1] + arr[i] * pow1[n - i]) % mod1;
  69. }
  70.  
  71. vector <int> ans;
  72. for (int i = 0; i <= n / 2; i++) {
  73. ll H1 = h1[i];
  74. ll H2 = ((hinv1[i + 1] - hinv1[i + 1 + i]) % mod1 + mod1) % mod1;
  75. int id1 = 1, id2 = n - i - i + 1;
  76. if (id1 > id2) {
  77. swap(id1, id2);
  78. swap(H1, H2);
  79. }
  80. H1 = (H1 * pow1[id2 - id1]) % mod1;
  81. if (H1 == H2) {
  82. ans.push_back(n - i);
  83. }
  84.  
  85. }
  86. }
  87. sort(ans.begin(), ans.end());
  88. for (auto &i : ans) {
  89. cout << i << " ";
  90. }
  91. return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement