#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 class RMQ_SparseTable { public: // table[k][i] means index of minimum value in [i, i + 2^k) std::vector> table; int * values; RMQ_SparseTable(int* A, size_t N) { table = std::vector>(log(N) + 1, vector(N)); values = A; for (int i = 0; i < N; ++i) { table[0][i] = i; } for (int k = 1; (1 << k) <= N; k++) { for (int i = 0; i + (1 << k) <= N; ++i) { int first = table[k - 1][i]; int second = table[k - 1][i + (1 << (k - 1))]; if (A[first] < A[second]) { table[k][i] = first; } else { table[k][i] = second; } } } } // returns min value in [s, t) inline int getMin(int s, int t) { int range = t - s; int k = log(range); int value1 = values[table[k][s]]; int value2 = values[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; 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; } } }; #include #include int N; pair s[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; } int main() { // get input cin >> N; for (int i = 0; i < N; ++i) { cin >> s[i].first; s[i].second = i; } cin >> M >> x >> d; // sort sort(s, s + N); // reindex for (int i = 0; i < N; ++i) { index_table[s[i].second] = i; } // calc LCP for (int i = 0; i < N - 1; ++i) { string& s1 = s[i].first; string& s2 = s[i + 1].first; LCP_table[i] = LCP(s1.c_str(), s2.c_str(), min(s1.size(), s2.size())); } // make Sparse Table RMQ_SparseTable sparse_table(LCP_table, N - 1); // 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(); } cout << sum << endl; }