#pragma GCC optimize ("O3") #include using namespace std; struct iostream_init_struct { iostream_init_struct() { std::cin.tie(0); std::cin.sync_with_stdio(false); } } iostream_init; // thank you, tookunn // http://tookunn.hatenablog.com/entry/2016/07/13/211148 #include #include #ifndef _WIN32 #include #endif class RMQ_SparseTable { public: // table[k][i] means minimum value in [i, i + 2^k) std::vector> table; RMQ_SparseTable(int* A, size_t N) { table = std::vector>(log(N) + 1, vector(N)); for (int i = 0; i < N; ++i) { table[0][i] = A[i]; } for (int k = 1; (1 << k) <= N; k++) { for (int i = 0; i + (1 << k) <= N; ++i) { table[k][i] = min(table[k - 1][i], table[k - 1][i + (1 << (k - 1))]); } } } // returns min value in [s, t) inline int getMin(int s, int t) { int range = t - s; int k = log(range); int value1 = table[k][s]; int value2 = table[k][t - (1 << k)]; return min(value1, value2); } inline static int log(int n) { //int ret = 0; //while (n = n >> 1) //{ // ret += 1; //} //return ret; #ifndef _WIN32 return std::__lg(n); #else if (n >= (1 << 16)) { return 16; } else if (n >= (1 << 15)) { return 15; } else if (n >= (1 << 14)) { return 14; } else if (n >= (1 << 13)) { return 13; } else if (n >= (1 << 12)) { return 12; } else if (n >= (1 << 11)) { return 11; } else if (n >= (1 << 10)) { return 10; } else if (n >= (1 << 9)) { return 9; } else if (n >= (1 << 8)) { return 8; } else if (n >= (1 << 7)) { return 7; } else if (n >= (1 << 6)) { return 6; } else if (n >= (1 << 5)) { return 5; } else if (n >= (1 << 4)) { return 4; } else if (n >= (1 << 3)) { return 3; } else if (n >= (1 << 2)) { return 2; } else if (n >= (1 << 1)) { return 1; } else { return 0; } #endif } }; #include #include int N; string s[100000]; int si[100000]; int M; long long x, d; int i, j; int index_table[100000]; int LCP_table[100000]; // same as pekempey's submission // http://yukicoder.me/submissions/172137 int di, dj, ii, jj; void next_init() { di = d / (N - 1); dj = d % (N - 1); ii = x / (N - 1); jj = x % (N - 1); i = ii; j = jj; if (i <= j) { ++j; } } inline void next() { jj += dj; if (jj >= N - 1) { jj -= N - 1; ++ii; } ii += di; if (ii >= N) { ii -= N; } i = ii; j = jj; if (i <= j) { ++j; } } int LCP(const char* s1, const char* s2, size_t min_length) { int ret = 0; //const uint64_t* s64i = reinterpret_cast(s1); //const uint64_t* s64j = reinterpret_cast(s2); //while (ret < min_length / 8) //{ // if (s64i[ret] == s64j[ret]) // { // ++ret; // } // else // { // break; // } //} //ret *= 8; while (ret < min_length) { if (s1[ret] == s2[ret]) { ++ret; } else { break; } } return ret; } #ifdef _WIN32 #include DWORD time = GetTickCount(); #define TimePrint(x) cout << x " " << GetTickCount() - time << endl; time = GetTickCount(); #else #define TimePrint(x) ; #endif int main() { TimePrint("(start)"); // get input cin >> N; for (int i = 0; i < N; ++i) { cin >> s[i]; } cin >> M >> x >> d; TimePrint("input"); // sort for (int i = 0; i < N; ++i) { si[i] = i; } sort(si, si + N, [&](int i, int j) { return s[i] < s[j]; }); TimePrint("sort "); // reindex for (int i = 0; i < N; ++i) { index_table[si[i]] = i; } TimePrint("reidx"); // calc LCP for (int i = 0; i < N - 1; ++i) { string& s1 = s[si[i]]; string& s2 = s[si[i + 1]]; LCP_table[i] = LCP(s1.c_str(), s2.c_str(), min(s1.size(), s2.size())); } TimePrint("LCP "); // make Sparse Table RMQ_SparseTable sparse_table(LCP_table, N - 1); TimePrint("SpTab"); // calc ans long long sum = 0; next_init(); for (int indx = 0; indx < M; ++indx) { int i_ = index_table[i]; int j_ = index_table[j]; if (i_ > j_) std::swap(i_, j_); sum += sparse_table.getMin(i_, j_); next(); } TimePrint("clAns"); cout << sum << endl; }