제출 #1188366

#제출 시각아이디문제언어결과실행 시간메모리
1188366pcheloveksBrperm (RMI20_brperm)C++20
100 / 100
550 ms162708 KiB
#include "brperm.h" #include <iostream> #include <vector> #include <string> #include <map> #include <set> #include <cmath> #include <fstream> #include <climits> #include <queue> #include <algorithm> #include <stdint.h> #include <stack> #include <iomanip> #include <unordered_set> #include <unordered_map> #include <cstring> // Для memset using namespace std; int n; const long long MOD = 1e9 + 9; long long p[530005], invp[530005]; long long put(long long a, long long exp) { if (exp == 0) return 1; if (exp % 2 == 0) return put(a * a % MOD, exp / 2); else return put(a * a % MOD, exp / 2) * a % MOD; } int rev(int x, int k) { int aux = 0; for (int i = 0; i < k; i++) if (((1 << i) & x)) aux += (1 << (k - i - 1)); return aux; } long long hsh[500005][19]; long long normal[500005][19]; long long sump[500005]; void init(int copn, const char s[]) { n = copn; p[0] = 1; p[1] = 31; for (int i = 2; i <= (1 << 19); i++) p[i] = (p[i - 1] * p[1]) % MOD; for (int i = 0; i <= (1 << 19); i++) invp[i] = put(p[i], MOD - 2); for (int i = 0; i < n; i++) { hsh[i][0] = normal[i][0] = s[i]; } for (int k = 1; k < 19; k++) { for (int i = 0; i + (1 << k) - 1 < n; i++) { hsh[i][k] = (hsh[i][k - 1] + hsh[i + (1 << (k - 1))][k - 1] * p[(1 << (18 - k))]) % MOD; //for(int j=0;j<(1<<k);j++) normal[i][k] = (normal[i][k] + s[i+j]*p[j*(1<<(18-k))])%MOD; } long long pref = 0; long long prod = 1; for (int i = 0; i < n; i++) { pref = (pref + 1LL * s[i] * prod) % MOD; sump[i] = pref; prod = prod * p[(1 << (18 - k))] % MOD; } prod = 1; for (int i = 0; i + (1 << k) - 1 < n; i++) { normal[i][k] = sump[i + (1 << k) - 1]; if (i > 0) normal[i][k] = (normal[i][k] + MOD - sump[i - 1]) % MOD; normal[i][k] = normal[i][k] * prod % MOD; prod = prod * invp[(1 << (18 - k))] % MOD; } } } int query(int i, int k) { if (i + (1 << k) - 1 >= n) return 0; return hsh[i][k] == normal[i][k]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...