結果

問題 No.515 典型LCP
ユーザー hitonanodehitonanode
提出日時 2021-03-13 13:53:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,453 bytes
コンパイル時間 1,264 ms
コンパイル使用メモリ 114,068 KB
実行使用メモリ 57,584 KB
最終ジャッジ日時 2024-10-15 05:48:26
合計ジャッジ時間 6,267 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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]
    std::vector<V> power; // power[i] = B^i
    rolling_hash(const std::string &s = "", V b = V::gen_b()) : B(b) {
        N = s.length();
        hash.resize(N + 1), power.resize(N + 1, 1);
        for (int i = 0; i < N; i++) {
            power[i + 1] = power[i] * B;
            hash[i + 1] = hash[i] * B + s[i];
        }
    }
    void addchar(const char &c) {
        V hnew = hash[N] * B + c, pnew = power[N] * B;
        N++, hash.emplace_back(hnew), power.emplace_back(pnew);
    }
    V get(int l, int r) const { // s[l] * B^(r - l - 1) + ... + s[r - 1]
        return hash[r] - hash[l] * power[r - l];
    }
};

// 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;
}

#include <cassert>
#include <iostream>
#include <string>
#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<DoubleHash>> 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;

    for (int k = 0; k < M; k++) {
        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';
}
0