Advertisement
cyberjab

Untitled

Dec 17th, 2023
38
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.49 KB | None | 0 0
  1. //#pragma GCC optimize("03")
  2. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <string>
  8. #include <vector>
  9. #include <map>
  10. #include <set>
  11. #include <unordered_map>
  12. #include <unordered_set>
  13. #include <queue>
  14. #include <deque>
  15. #include <cmath>
  16. #include <numeric>
  17. #include <algorithm>
  18. #include <ctime>
  19. #include <chrono>
  20. #include <random>
  21. #include <functional>
  22.  
  23. using namespace std;
  24. using ll = long long;
  25. using db = double;
  26. using ldb = long double;
  27. using pii = pair<int, int>;
  28. using pll = pair<ll, ll>;
  29. using vint = vector<int>;
  30. using vll = vector<ll>;
  31. #define all(x) x.begin(), x.end()
  32. #define size(x) int(x.size())
  33. #define rep(x) for(int rep_i = 0; rep_i < x; ++rep_i)
  34. #define forp(i, s, f) for(int i = s; i < f; ++i)
  35. #define form(i, s, f) for(int i = s; i > f; --i)
  36. #define PB push_back
  37. #define MP make_pair
  38. #define F first
  39. #define S second
  40. #define elif else if
  41. #define dprint(x) for (auto now: x) cout << now << " "
  42.  
  43. const int MOD = 1e9 + 7;
  44. const int MOD2 = 998244353;
  45. const int INF = 2e9 + 7;
  46. const ll LINF = 1e18 + 7;
  47. const double EPS = 1e-9;
  48. const long double PI = acosl(-1.0);
  49.  
  50. bool isequal(int from1, int from2, int len, vll& h, vll& x, vll& h2) {
  51. return (h[from1 + len - 1] + h2[from2 - 1] * x[len]) % MOD ==
  52. (h2[from2 + len - 1] + h[from1 - 1] * x[len]) % MOD;
  53. }
  54.  
  55. int main() {
  56. ios_base::sync_with_stdio(0);
  57. cin.tie(0);
  58. /*cout << setprecision(x)*/
  59. cout << fixed;
  60. vector <int> s, s2;
  61. s.push_back(0);
  62. s2.push_back(0);
  63. int n, k;
  64. cin >> n >> k;
  65. forp(i, 0, n) {
  66. int x;
  67. cin >> x;
  68. s.push_back(x);
  69. }
  70. /*cin >> s;*/
  71. s2 = s;
  72. int xx = 257;
  73. reverse(s2.begin() + 1, s2.end());
  74. //int n = size(s);
  75. vll h(n + 1, 0);
  76. vll h2(n + 1, 0);
  77. vll x(n + 1, 0);
  78. x[0] = 1;
  79. forp(i, 1, n + 1) {
  80. h[i] = (h[i - 1] * xx + s[i]) % MOD;
  81. h2[i] = (h2[i - 1] * xx + s2[i]) % MOD;
  82. x[i] = (x[i - 1] * xx) % MOD;
  83. }
  84. int ln = 0;
  85. vector <int> ans;
  86. while (ln < n + 1) {
  87. if (isequal(1, n + 1 - ln, ln / 2, h, x, h2)) {
  88. ans.push_back(n - ln / 2);
  89. }
  90. ln += 2;
  91. }
  92. sort(ans.begin(), ans.end());
  93. dprint(ans);
  94. //if ((h[1 + 2 - 1] + h2[2 - 1] * x[2]) % MOD ==
  95. // (h2[2 + 2 - 1] + h[1 - 1] * x[2]) % MOD) {
  96. // cout << "!!!!!!"; //|12| 212 - 212 |21| //12212
  97. //}
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement