#include "brperm.h" #include "bits/stdc++.h" namespace { using i64 = long long; template<typename T> T power(T a, i64 b) { T res = 1; while(b) { if(b & 1) { res *= a; } a *= a; b >>= 1; } return res; } constexpr int md = 998244353; struct MInt { int val; MInt() : val(0) {} template<typename T> MInt(T v) { if(-md <= v && v < md) { val = v; } else { val = v % md; } if(val < 0) { val += md; } } int operator() () { return val; } MInt operator+= (MInt rhs) { if((val += rhs.val) >= md) { val -= md; } return *this; } MInt operator-= (MInt rhs) { if((val -= rhs.val) < 0) { val += md; } return *this; } MInt operator*= (MInt rhs) { val = (int)(1LL * val * rhs.val % md); return *this; } MInt inv() { return power(*this, md - 2); } MInt operator/= (MInt rhs) { return *this *= rhs.inv(); } bool operator== (MInt rhs) const { return val == rhs.val; } bool operator!= (MInt rhs) const { return val != rhs.val; } }; MInt operator+ (MInt lhs, MInt rhs) { return lhs += rhs; } MInt operator- (MInt lhs, MInt rhs) { return lhs -= rhs; } MInt operator* (MInt lhs, MInt rhs) { return lhs *= rhs; } MInt operator/ (MInt lhs, MInt rhs) { return lhs /= rhs; } std::ostream& operator<< (std::ostream& os, MInt v) { return os << v(); } std::string to_string(MInt x) { return to_string(x()); } using Z = MInt; constexpr int base = 31; int N; int LG; std::string str; std::vector<Z> powb; std::vector<std::vector<Z>> pre; std::vector<std::vector<Z>> f; }; void init(int n, const char s[]) { str = s; N = n; LG = std::__lg(N); powb.resize(LG + 1); powb[0] = base; for (int i = 1; i <= LG; ++i) { powb[i] = powb[i - 1] * powb[i - 1]; } pre.resize(LG + 1); for (int j = 0; j <= LG; ++j) { pre[j].resize(N + 1); for (int i = 0; i < N; ++i) { pre[j][i + 1] = pre[j][i] * powb[LG - j] + (s[i] - 'a' + 1); } } f.resize(LG + 1); f[0].resize(N); for (int i = 0; i < N; ++i) { f[0][i] = s[i] - 'a' + 1; } for (int j = 1; j <= LG; ++j) { int m = N - (1 << j) + 1; f[j].resize(m); for (int i = 0; i < m; ++i) { f[j][i] = powb[LG - j] * f[j - 1][i] + f[j - 1][i + (1 << (j - 1))]; } } // for (int j = 0; j <= LG; ++j) { // int m = N - (1 << j) + 1; // for (int i = 0; i < m; ++i) { // std::cerr << f[j][i] << " \n"[i == m - 1]; // } // } return; } int query(int i, int k) { if (i + (1 << k) - 1 >= N) { return 0; } Z sh = pre[k][i + (1 << k)] - pre[k][i] * powb[LG]; // Z sh = 0; // for (int j = 0; j < (1 << k); ++j) { // sh = sh * powb[LG - k] + str[i + j] - 'a' + 1; // std::cerr << sh << ' '; // } // std::cerr << '\n'; Z rh = f[k][i]; // std::cerr << "[sh, rh]: " << sh << ' ' << rh << '\n'; return sh == rh; }