This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "brperm.h"
using namespace std;
const int kN = 5e5;
const int kLog = 19;
const int base[] = {29, 31};
const int mod[] = {(int)1e9 + 7, (int)1e9 + 9};
int N, p[2][1 + kLog];
int hsh[2][1 + kN + 1][1 + kLog];
int brHash[2][1 + kN][1 + kLog];
int add(int x, int y, int mod) {
x += y;
if (x >= mod) {
x -= mod;
}
return x;
}
int mult(int x, int y, int mod) {
return (int64_t)x * y % mod;
}
int getHsh(int i, int len, int k, int t) {
return add(hsh[t][i][k], mod[t] - mult(hsh[t][i + len][k], p[t][kLog], mod[t]), mod[t]);
}
void init(int n, const char s[]) {
N = n;
for (int i = 0; i < 2; ++i) {
p[i][0] = base[i];
}
for (int k = 1; k <= kLog; ++k) {
for (int i = 0; i < 2; ++i) {
p[i][k] = mult(p[i][k - 1], p[i][k - 1], mod[i]);
}
}
for (int k = 0; k <= kLog; ++k) {
for (int i = n; i > 0; --i) {
for (int j = 0; j < 2; ++j) {
hsh[j][i][k] = add(mult(hsh[j][i + 1][k], p[j][k], mod[j]), s[i - 1] - 'a' + 1, mod[j]);
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 2; ++j) {
brHash[j][i][0] = s[i - 1] - 'a' + 1;
}
}
for (int k = 1; k <= kLog; ++k) {
for (int i = 1; i + (1 << k) - 1 <= n; ++i) {
for (int j = 0; j < 2; ++j) {
brHash[j][i][k] = add(brHash[j][i][k - 1], mult(p[j][kLog - k], brHash[j][i + (1 << (k - 1))][k - 1], mod[j]), mod[j]);
}
}
}
}
int query(int i, int k) {
i += 1;
if (k >= 20 || i + (1 << k) - 1 > N) {
return 0;
}
return getHsh(i, 1 << k, kLog - k, 0) == brHash[0][i][k] && getHsh(i, 1 << k, kLog - k, 1) == brHash[1][i][k];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |