結果
| 問題 | No.515 典型LCP |
| ユーザー |
👑  hitonanode
|
| 提出日時 | 2022-09-29 23:42:41 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,153 bytes |
| コンパイル時間 | 1,609 ms |
| コンパイル使用メモリ | 137,260 KB |
| 実行使用メモリ | 35,924 KB |
| 最終ジャッジ日時 | 2023-08-24 05:11:39 |
| 合計ジャッジ時間 | 6,884 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| testcase_02 | TLE | - |
| testcase_03 | AC | 1 ms
4,380 KB |
| testcase_04 | AC | 2 ms
4,376 KB |
| testcase_05 | TLE | - |
| testcase_06 | TLE | - |
| testcase_07 | TLE | - |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | AC | 375 ms
16,056 KB |
| testcase_11 | AC | 349 ms
16,196 KB |
| testcase_12 | AC | 345 ms
16,216 KB |
| testcase_13 | TLE | - |
| testcase_14 | AC | 25 ms
16,648 KB |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
ソースコード
#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';
}