#line 2 "string/rolling_hash_1d.hpp" #include #include #include #include #include // CUT begin struct DoubleHash : public std::pair { using ull = unsigned long long; using pair = std::pair; static std::pair MODs; DoubleHash(std::pair x) : pair(x) {} DoubleHash(unsigned x, unsigned y) : pair(x, y) {} DoubleHash(unsigned x) : DoubleHash(x, x) {} DoubleHash() : DoubleHash(0) {} static inline DoubleHash mod_subtract(pair x) { if (x.first >= MODs.first) x.first -= MODs.first; if (x.second >= MODs.second) x.second -= MODs.second; return x; } DoubleHash operator+(const DoubleHash &x) const { return mod_subtract({this->first + x.first, this->second + x.second}); } DoubleHash operator+(unsigned x) const { return mod_subtract({this->first + x, this->second + x}); } DoubleHash operator-(const DoubleHash &x) const { return mod_subtract( {this->first + MODs.first - x.first, this->second + MODs.second - x.second}); } DoubleHash operator*(const DoubleHash &x) const { return {unsigned(ull(this->first) * x.first % MODs.first), unsigned(ull(this->second) * x.second % MODs.second)}; } DoubleHash operator*(unsigned x) const { return {unsigned(ull(this->first) * x % MODs.first), unsigned(ull(this->second) * x % MODs.second)}; } static DoubleHash gen_b(bool force_update = false) { static DoubleHash b{0, 0}; if (b == DoubleHash{0, 0} or force_update) { std::mt19937 mt(std::chrono::steady_clock::now().time_since_epoch().count()); std::uniform_int_distribution d(1 << 16, 1 << 29); b = {d(mt), d(mt)}; } return b; } }; std::pair DoubleHash::MODs{1000000007, 998244353}; // Rolling Hash (Rabin-Karp), 1dim template struct rolling_hash { int N; const V B; std::vector hash; // hash[i] = s[0] * B^(i - 1) + ... + s[i - 1] static std::vector power; // power[i] = B^i void _extend_powvec() { while (static_cast(power.size()) <= N) { auto tmp = power.back() * B; power.push_back(tmp); } } template rolling_hash(const std::vector &s, V b = V::gen_b()) : N(s.size()), B(b), hash(N + 1) { for (int i = 0; i < N; i++) hash[i + 1] = hash[i] * B + s[i]; _extend_powvec(); } rolling_hash(const std::string &s = "", V b = V::gen_b()) : N(s.size()), B(b), hash(N + 1) { for (int i = 0; i < N; i++) hash[i + 1] = hash[i] * B + s[i]; _extend_powvec(); } void addchar(const char &c) { V hnew = hash[N] * B + c; N++, hash.emplace_back(hnew); _extend_powvec(); } V get(int l, int r) const { // s[l] * B^(r - l - 1) + ... + s[r - 1] return hash[r] - hash[l] * power[r - l]; } int lcplen(int l1, int l2) const { return longest_common_prefix(*this, l1, *this, l2); } }; template std::vector rolling_hash::power{V(1)}; // Longest common prerfix between s1[l1, N1) and s2[l2, N2) template int longest_common_prefix(const rolling_hash &rh1, int l1, const rolling_hash &rh2, int l2) { int lo = 0, hi = std::min(rh1.N + 1 - l1, rh2.N + 1 - l2); while (hi - lo > 1) { const int c = (lo + hi) / 2; auto h1 = rh1.get(l1, l1 + c), h2 = rh2.get(l2, l2 + c); (h1 == h2 ? lo : hi) = c; } return lo; } // Longest common suffix between s1[0, r1) and s2[0, r2) template int longest_common_suffix(const rolling_hash &rh1, int r1, const rolling_hash &rh2, int r2) { int lo = 0, hi = std::min(r1, r2) + 1; while (hi - lo > 1) { const int c = (lo + hi) / 2; auto h1 = rh1.get(r1 - c, r1), h2 = rh2.get(r2 - c, r2); (h1 == h2 ? lo : hi) = c; } return lo; } #line 2 "number/modint_mersenne61.hpp" #include #line 5 "number/modint_mersenne61.hpp" // F_p, p = 2^61 - 1 // https://qiita.com/keymoon/items/11fac5627672a6d6a9f6 class ModIntMersenne61 { static const long long md = (1LL << 61) - 1; long long _v; inline unsigned hi() const noexcept { return _v >> 31; } inline unsigned lo() const noexcept { return _v & ((1LL << 31) - 1); } public: static long long mod() { return md; } ModIntMersenne61() : _v(0) {} // 0 <= x < md * 2 explicit ModIntMersenne61(long long x) : _v(x >= md ? x - md : x) {} long long val() const noexcept { return _v; } ModIntMersenne61 operator+(const ModIntMersenne61 &x) const { return ModIntMersenne61(_v + x._v); } ModIntMersenne61 operator-(const ModIntMersenne61 &x) const { return ModIntMersenne61(_v + md - x._v); } ModIntMersenne61 operator*(const ModIntMersenne61 &x) const { using ull = unsigned long long; // TODO: factorize ull uu = (ull)hi() * x.hi() * 2; ull ll = (ull)lo() * x.lo(); ull lu = (ull)hi() * x.lo() + (ull)lo() * x.hi(); ull sum = uu + ll + ((lu & ((1ULL << 30) - 1)) << 31) + (lu >> 30); ull reduced = (sum >> 61) + (sum & ull(md)); return ModIntMersenne61(reduced); } ModIntMersenne61 pow(long long n) const { assert(n >= 0); ModIntMersenne61 ans(1), tmp = *this; while (n) { if (n & 1) ans *= tmp; tmp *= tmp, n >>= 1; } return ans; } ModIntMersenne61 inv() const { return pow(md - 2); } ModIntMersenne61 operator/(const ModIntMersenne61 &x) const { return *this * x.inv(); } ModIntMersenne61 operator-() const { return ModIntMersenne61(md - _v); } ModIntMersenne61 &operator+=(const ModIntMersenne61 &x) { return *this = *this + x; } ModIntMersenne61 &operator-=(const ModIntMersenne61 &x) { return *this = *this - x; } ModIntMersenne61 &operator*=(const ModIntMersenne61 &x) { return *this = *this * x; } ModIntMersenne61 &operator/=(const ModIntMersenne61 &x) { return *this = *this / x; } ModIntMersenne61 operator+(unsigned x) const { return ModIntMersenne61(this->_v + x); } bool operator==(const ModIntMersenne61 &x) const { return _v == x._v; } bool operator!=(const ModIntMersenne61 &x) const { return _v != x._v; } bool operator<(const ModIntMersenne61 &x) const { return _v < x._v; } // To use std::map template friend OStream &operator<<(OStream &os, const ModIntMersenne61 &x) { return os << x._v; } static ModIntMersenne61 gen_b(bool force_update = false) { static ModIntMersenne61 b(0); if (b == ModIntMersenne61(0) or force_update) { std::mt19937 mt(std::chrono::steady_clock::now().time_since_epoch().count()); std::uniform_int_distribution d(1, ModIntMersenne61::mod()); b = ModIntMersenne61(d(mt)); } return b; } }; #line 4 "string/test/rolling_hash_lcp_mersenne61.test.cpp" #include #line 6 "string/test/rolling_hash_lcp_mersenne61.test.cpp" #define PROBLEM "https://yukicoder.me/problems/1408" using namespace std; int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N; cin >> N; vector> rhs, rhs_rev; for (int i = 0; i < N; i++) { string s; cin >> s; rhs.emplace_back(s); reverse(s.begin(), s.end()); rhs_rev.emplace_back(s); } int M; long long x, d, ret = 0; cin >> M >> x >> d; while (M--) { int i = x / (N - 1); int j = x % (N - 1); if (i <= j) j++; x = (x + d) % (static_cast(N) * (N - 1)); auto tmp = longest_common_prefix(rhs[i], 0, rhs[j], 0); assert(tmp == longest_common_suffix(rhs_rev[i], rhs_rev[i].N, rhs_rev[j], rhs_rev[j].N)); ret += tmp; } cout << ret << '\n'; }