This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define debug(...) 42
#include "bits/stdc++.h"
using namespace std;
#ifndef LOCAL
#include "brperm.h"
#else
void init(int n, const char s[]);
int query(int i, int k);
#endif
struct mint {
static constexpr int mod = 998'244'353;
int value = 0;
mint() = default;
mint(int value) : value(value) {}
mint& operator+=(const mint &other) {
value += other.value;
if (value >= mod) {
value -= mod;
}
return *this;
}
mint operator+(const mint &other) const {
mint result = *this;
return result += other;
}
mint& operator-=(const mint &other) {
value += mod - other.value;
if (value >= mod) {
value -= mod;
}
return *this;
}
mint operator-(const mint &other) const {
mint result = *this;
return result -= other;
}
mint& operator*=(const mint &other) {
value = 1ll * value * other.value % mod;
return *this;
}
mint operator*(const mint &other) const {
mint result = *this;
return result *= other;
}
mint power(int k) const {
mint result = 1;
mint current = *this;
while (k) {
if (k & 1) {
result *= current;
}
current *= current;
k >>= 1;
}
return result;
}
mint& operator/=(const mint &other) {
return this->operator*=(other.power(mod - 2));
}
mint operator/(const mint &other) const {
mint result = *this;
return result /= other;
}
bool operator==(const mint &other) const {
return value == other.value;
}
};
mint P[21];
mint A[21][500500];
mint B[21][500500];
int n;
void init(int N, const char S[]) {
n = N;
for (int i = 0; i <= 20; i++) {
P[i] = mint(31).power(1 << (23 - i));
}
for (int i = 0; i < N; i++) {
A[0][i] = P[0] * (S[i] - 'a' + 1);
}
for (int j = 1; j <= 20; j++) {
for (int i = 0; i + (1 << j) <= N; i++) {
A[j][i] = A[j - 1][i] + A[j - 1][i + (1 << (j - 1))] * P[j];
}
}
for (int j = 0; j <= 20; j++) {
for (int i = 0; i < N; i++) {
if (i > 0) {
B[j][i] = B[j][i - 1];
}
B[j][i] += P[j].power(i) * (S[i] - 'a' + 1);
}
}
}
mint getA(int i, int k) {
return A[k][i];
}
mint getB(int i, int k) {
int l = i;
int r = i + (1 << k) - 1;
if (l == 0) {
return B[k][r];
} else {
return (B[k][r] - B[k][l - 1]) / P[k].power(l);
}
}
int query(int i, int k) {
if (i + (1 << k) > n) {
return 0;
}
return getB(i, k) == getA(i, k);
}
#ifdef LOCAL
char __s[(int)5e5 + 10] = {};
int main() {
cin >> __s;
init(strlen(__s), __s);
int __x, __y;
while (cin >> __x >> __y)
cout << query(__x, __y) << '\n';
return 0;
}
#endif
# | 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... |