結果
| 問題 |
No.515 典型LCP
|
| コンテスト | |
| ユーザー |
 Nguyen Thanh Trung
|
| 提出日時 | 2022-06-26 18:43:45 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 533 ms / 1,000 ms |
| コード長 | 8,378 bytes |
| コンパイル時間 | 3,362 ms |
| コンパイル使用メモリ | 261,528 KB |
| 実行使用メモリ | 35,452 KB |
| 最終ジャッジ日時 | 2024-11-17 05:58:37 |
| 合計ジャッジ時間 | 10,256 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 15 |
ソースコード
#include "bits/stdc++.h"
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,tune=native")
using namespace std;
#define int long long
#define FOR(i, a, b) for (int i = (a), _##i = (b); i <= _##i; ++i)
#define FORD(i, a, b) for (int i = (a), _##i = (b); i >= _##i; --i)
#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)
#define DEBUG(X) { auto _X = (X); cerr << "L" << __LINE__ << ": " << #X << " = " << (_X) << endl; }
#define PR(A, n) { cerr << "L" << __LINE__ << ": " << #A << " = "; FOR(_, 1, n) cerr << A[_] << ' '; cerr << endl; }
#define PR0(A, n) { cerr << "L" << __LINE__ << ": " << #A << " = "; REP(_, n) cerr << A[_] << ' '; cerr << endl; }
#define __builtin_popcount __builtin_popcountll
#define SZ(x) ((int)(x).size())
#define ALL(a) (a).begin(), (a).end()
#define TWO(x) (1LL<<(x))
inline int gcd(int a, int b) {int r; while (b) {r = a % b; a = b; b = r;} return a;}
// For printing pair, container, etc.
// Copied from https://quangloc99.github.io/2021/07/30/my-CP-debugging-template.html
template<class U, class V> ostream& operator << (ostream& out, const pair<U, V>& p) {
return out << '(' << p.first << ", " << p.second << ')';
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator << (ostream& out, const Con& con) {
out << '{';
for (auto beg = con.begin(), it = beg; it != con.end(); it++) {
out << (it == beg ? "" : ", ") << *it;
}
return out << '}';
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
if (i == tuple_size<T>::value) return out << ")";
else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
}
template<class ...U> ostream& operator << (ostream& out, const tuple<U...>& t) {
return print_tuple_utils<0, tuple<U...>>(out, t);
}
// for 64-bit, use mt19937_64
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int get_rand(int r) {
return uniform_int_distribution<int> (0, r-1)(rng);
}
// use shuffle instead of random_shuffle
#define random_shuffle askcjaljc
inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
#ifdef __GNUC__
asm(
"divl %4; \n\t"
: "=a" (d), "=d" (m)
: "d" (xh), "a" (xl), "r" (y)
);
#else
__asm {
mov edx, dword ptr[xh];
mov eax, dword ptr[xl];
div dword ptr[y];
mov dword ptr[d], eax;
mov dword ptr[m], edx;
};
#endif
out_d = d; out_m = m;
}
template<int MOD>
struct ModInt {
unsigned x;
constexpr ModInt() : x(0) { }
constexpr ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
#define COMPAREOP(OP) bool constexpr operator OP(ModInt b) const { return x OP b.x; }
COMPAREOP(==) COMPAREOP(!=) COMPAREOP(<) COMPAREOP(>) COMPAREOP(<=) COMPAREOP(>=)
#undef COMPAREOP
ModInt operator-() const { return ModInt(x ? MOD - x : 0); }
ModInt constexpr& operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt constexpr& operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) {
unsigned dummy;
fasterLLDivMod((unsigned long long)x * that.x, MOD, dummy, x);
return *this;
}
ModInt operator*(ModInt that) const {
ModInt res;
unsigned dummy;
fasterLLDivMod((unsigned long long)x * that.x, MOD, dummy, res.x);
return res;
}
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
// Below: copied from user202729_, not tested.
ModInt inv() const {
int a = x, b = MOD, ax = 1, bx = 0;
while (b) {
int q = a/b, t = a%b;
a = b; b = t;
t = ax - bx*q;
ax = bx; bx = t;
}
assert(a == 1);
if (ax < 0) ax += MOD;
return ax;
}
ModInt& operator /= (ModInt m) { return (*this) *= m.inv(); }
ModInt operator / (ModInt that) const { return ModInt(*this) /= that; }
};
template<int MOD>
ModInt<MOD> power(ModInt<MOD> n, long long k) {
if (k == 0) return ModInt<MOD> (1);
ModInt<MOD> res(1);
while (k > 0) {
if (k & 1) res = res * n;
n = n * n;
k >>= 1;
}
return res;
}
const int MOD = 1e9 + 7;
using modular = ModInt<MOD>;
std::ostream& operator << (std::ostream& cout, const modular& m) {
cout << m.x;
return cout;
}
std::istream& operator >> (std::istream& cin, modular& m) {
cin >> m.x;
return cin;
}
struct Hash {
long long x;
modular y;
Hash operator + (const Hash& a) const { return Hash{x + a.x, y + a.y}; }
Hash operator - (const Hash& a) const { return Hash{x - a.x, y - a.y}; }
Hash operator * (const Hash& a) const { return Hash{x * a.x, y * a.y}; }
Hash operator * (int k) const { return Hash{x*k, y*k}; }
};
bool operator == (const Hash& a, const Hash& b) {
return a.x == b.x && a.y == b.y;
}
struct HashGenerator {
HashGenerator(int maxLen, int base = 311) {
p.resize(maxLen + 1);
p[0] = {1, 1};
for (int i = 1; i <= maxLen; i++) {
p[i] = p[i-1] * base;
}
}
std::vector<Hash> hash(const std::string& s) {
std::vector<Hash> res(s.size());
for (size_t i = 0; i < s.size(); i++) {
res[i] = p[i] * (int) s[i];
}
std::partial_sum(res.begin(), res.end(), res.begin());
return res;
}
// compare [l1, r1] vs [l2, r2]
bool equals(
const std::vector<Hash>& h1, int l1, int r1,
const std::vector<Hash>& h2, int l2, int r2) {
assert(0 <= l1 && l1 <= r1 && r1 < (int) h1.size());
assert(0 <= l2 && l2 <= r2 && r2 < (int) h2.size());
return __getHash(h1, l1, r1) * p[l2] == __getHash(h2, l2, r2) * p[l1];
}
// Returns length of max common prefix of h1[l1, r1] and h2[l2, r2]
// length = 0 -> first character of 2 substrings are different.
int maxCommonPrefix(
const std::vector<Hash>& h1, int l1, int r1,
const std::vector<Hash>& h2, int l2, int r2) {
assert(0 <= l1 && l1 <= r1 && r1 < (int) h1.size());
assert(0 <= l2 && l2 <= r2 && r2 < (int) h2.size());
int len1 = r1 - l1 + 1;
int len2 = r2 - l2 + 1;
auto r = std::views::iota(0, std::min(len1, len2));
auto res = std::ranges::partition_point(
r,
[&] (int mid) {
return equals(h1, l1, l1+mid, h2, l2, l2+mid);
});
return *res;
}
// compare s1[l1, r1] and s2[l2, r2]
int cmp(
const std::string& s1, const std::vector<Hash>& h1, int l1, int r1,
const std::string& s2, const std::vector<Hash>& h2, int l2, int r2) {
assert(0 <= l1 && l1 <= r1 && r1 < (int) h1.size());
assert(0 <= l2 && l2 <= r2 && r2 < (int) h2.size());
int commonPrefixLen = maxCommonPrefix(h1, l1, r1, h2, l2, r2);
char c1 = (l1 + commonPrefixLen <= r1) ? s1[l1 + commonPrefixLen] : 0;
char c2 = (l2 + commonPrefixLen <= r2) ? s2[l2 + commonPrefixLen] : 0;
return (c1 == c2) ? 0 : ((c1 < c2) ? -1 : 1);
}
private:
std::vector<Hash> p;
// DO NOT USE, this doesn't divide by p[l]
Hash __getHash(const std::vector<Hash>& h, int l, int r) {
assert(0 <= l && l <= r && r < (int) h.size());
return h[r] - (l == 0 ? Hash{0, 0} : h[l-1]);
}
};
HashGenerator g(1000111);
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; std::cin >> n;
std::vector<std::vector<Hash>> hs;
for (int i = 0; i < n; i++) {
std::string s; std::cin >> s;
hs.push_back(g.hash(s));
}
int m;
long long x, d, res = 0;
std::cin >> m >> x >> d;
while (m--) {
int i = x / (n - 1);
int j = x % (n - 1);
if (i <= j) ++j;
x = (x + d) % (n * (n-1LL));
res += g.maxCommonPrefix(
hs[i], 0, SZ(hs[i]) - 1,
hs[j], 0, SZ(hs[j]) - 1);
}
std::cout << res << '\n';
return 0;
}