#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; } } // multikey-quicksort // http://d.hatena.ne.jp/echizen_tm/20100815/1281872393 // <- middle ........ large -> int si_temp[100000]; // sort [l, r) void multikey_qsort(int l, int r, int depth) { if (r - l < 2) { //// insertion sort //si[l] = si[l]; //for (int ins_i = l + 1; ins_i < r; ++ins_i) //{ // int ins_v = si[ins_i]; // int i = 0; // for (; i < ins_i; ++i) // { // if (strcmp(s[si[i]].data() + depth, s[ins_v].data() + depth) > 0) // { // for (int j = ins_i; j > i; --j) // { // si[j] = si[j - 1]; // } // si[i] = ins_v; // break; // } // } // if (i == ins_i) // { // si[ins_i] = ins_v; // } //} //return; } else { char pivot = *(s[si[l]].data() + depth); int small = 0; int middle = 0; int large = 0; for (int ins_i = l; ins_i < r; ++ins_i) { int index = si[ins_i]; char c = *(s[index].data() + depth); if (c < pivot) { si[l + small++] = index; } else if (c == pivot) { si_temp[middle++] = index; } else { si_temp[r - ++large] = index; } } memcpy(si + (l + small), si_temp, sizeof(int) * middle); memcpy(si + (l + small + middle), si_temp + (r - large), sizeof(int) * large); multikey_qsort(l, l + small, depth); multikey_qsort(l + small, l + small + middle, depth + 1); multikey_qsort(l + small + middle, r, depth); } } void multikey_qsort() { multikey_qsort(0, N, 0); } 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; } if (N > 10000) multikey_qsort(); else 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; }