#802130 (C++23) No.515 典型LCP

• 問題: No.515 典型LCP
• ユーザー: hitonanode
• 提出日時: 2022-09-29 23:42:41
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 8,153 bytes
• コンパイル時間: 1,668 ms
• コンパイル使用メモリ: 138,956 KB
• 実行使用メモリ: 27,420 KB
• 最終ジャッジ日時: 2024-12-22 18:35:19
• 合計ジャッジ時間: 21,935 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 2
other	AC * 4 TLE * 11

ソースコード

#line 2 "string/rolling_hash_1d.hpp"
#include <algorithm>
#include <chrono>
#include <random>
#include <string>
#include <vector>

// CUT begin
struct DoubleHash : public std::pair<unsigned, unsigned> {
    using ull = unsigned long long;
    using pair = std::pair<unsigned, unsigned>;
    static std::pair<unsigned, unsigned> MODs;
    DoubleHash(std::pair<unsigned, unsigned> 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<unsigned> d(1 << 16, 1 << 29);
            b = {d(mt), d(mt)};
        }
        return b;
    }
};
std::pair<unsigned, unsigned> DoubleHash::MODs{1000000007, 998244353};

// Rolling Hash (Rabin-Karp), 1dim
template <typename V = DoubleHash> struct rolling_hash {
    int N;
    const V B;
    std::vector<V> hash;         // hash[i] = s[0] * B^(i - 1) + ... + s[i - 1]
    static std::vector<V> power; // power[i] = B^i
    void _extend_powvec() {
        while (static_cast<int>(power.size()) <= N) {
            auto tmp = power.back() * B;
            power.push_back(tmp);
        }
    }
    template <typename Int>
    rolling_hash(const std::vector<Int> &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 <typename V> std::vector<V> rolling_hash<V>::power{V(1)};

// Longest common prerfix between s1[l1, N1) and s2[l2, N2)
template <typename T>
int longest_common_prefix(const rolling_hash<T> &rh1, int l1, const rolling_hash<T> &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 <typename T>
int longest_common_suffix(const rolling_hash<T> &rh1, int r1, const rolling_hash<T> &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 <cassert>
#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 <class OStream> 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<long long> d(1, ModIntMersenne61::mod());
            b = ModIntMersenne61(d(mt));
        }
        return b;
    }
};
#line 4 "string/test/rolling_hash_lcp_mersenne61.test.cpp"
#include <iostream>
#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<rolling_hash<ModIntMersenne61>> 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<long long>(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';
}