#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 very much 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) 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); } static int log(int n) { int ret = 0; while (n = n >> 1) { ret += 1; } return ret; } }; #include #include int N; pair s[100000]; int M; long long x, d; int i, j; int index_table[100000]; int LCP_table[100000]; void next() { i = (x / (N - 1)); j = (x % (N - 1)); if (i > j) { //int temp = i; //i = j; //j = temp; } else { j = j + 1; } x = (x + d) % ((long long)(N) * (N - 1)); } 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; for (int indx = 0; indx < M; ++indx) { next(); int smaller_index, bigger_index; if (index_table[i] < index_table[j]) { smaller_index = index_table[i]; bigger_index = index_table[j]; } else { smaller_index = index_table[j]; bigger_index = index_table[i]; } sum += sparse_table.getMin(smaller_index, bigger_index); } cout << sum << endl; }