#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define rep(i, n) repr(i, 0, n) #define reprrev(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--) #define reprev(i, n) reprrev(i, 0, n) #define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++) #define chmin(mi, val) mi = min(mi, val) #define chmax(ma, val) ma = max(ma, val) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define mp make_pair #define mt make_tuple #define INF 1050000000 #define INFR INT_MAX #define INFL (long long)(4e18) #define INFLR LLONG_MAX #define EPS (1e-10) //#define MOD 1000000007 #define MOD 998244353 #define PI 3.141592653589793238 #define RMAX 4294967295 using vi = vector; using vvi = vector>; using vvvi = vector>>; using vvvvi = vector>>>; using ll = long long; using vll = vector; using vvll = vector>; using vvvll = vector>>; using vd = vector; using vvd = vector>; using vb = vector; using vvb = vector>; using vc = vector; using vvc = vector>; using vs = vector; using vvs = vector>; using Pi = pair; using vPi = vector; using vvPi = vector>; using vvvPi = vector>>; using vvvvPi = vector>>>; using Pll = pair; using vPll = vector; using Pd = pair; using vPd = vector; template using vec = vector; template using pql = priority_queue, greater>; using Comp = complex; // vvvvvvvvvvvvvvvvvvvvvvv debug output vvvvvvvvvvvvvvvvvvvvvvv // vector input template istream &operator>>(istream &is, vector &vec) { for (T &x : vec) is >> x; return is; } // pair template ostream &operator<<(ostream &os, const pair &pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } // vector template ostream &operator<<(ostream &os, const vector &vec) { os << "{"; for (int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); } os << "}"; return os; } // deque template ostream &operator<<(ostream &os, const deque &vec) { os << "{"; for (int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); } os << "}"; return os; } // map template ostream &operator<<(ostream &os, const map &map_var) { os << "{"; repi(itr, map_var) { os << *itr; itr++; if (itr != map_var.end()) os << ", "; itr--; } os << "}"; return os; } // set template ostream &operator<<(ostream &os, const set &set_var) { os << "{"; repi(itr, set_var) { os << *itr; itr++; if (itr != set_var.end()) os << ", "; itr--; } os << "}"; return os; } // multiset template ostream &operator<<(ostream &os, const multiset &set_var) { os << "{"; repi(itr, set_var) { os << *itr; itr++; if (itr != set_var.end()) os << ", "; itr--; } os << "}"; return os; } #define DUMPOUT cerr void dump_func() { DUMPOUT << endl; } template void dump_func(Head &&head, Tail &&... tail) { DUMPOUT << head; if (sizeof...(Tail) > 0) { DUMPOUT << ", "; } dump_func(std::move(tail)...); } #ifdef DEBUG_ #define DEB #define dump(...) \ DUMPOUT << " " << string(#__VA_ARGS__) << ": " \ << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" \ << endl \ << " ", \ dump_func(__VA_ARGS__) #else #define DEB if (false) #define dump(...) #endif // ^^^^^^^^^^^^^^^^^^^^^^^ debug output ^^^^^^^^^^^^^^^^^^^^^^^ string YN(bool y, int id = 0) { if (id) cout << id; return (y ? "YES" : "NO"); } string yn(bool y, int id = 0) { if (id) cout << id; return (y ? "Yes" : "No"); } string ON(bool y, int id = 0) { if (id) cout << id; return (y ? "OK" : "NG"); } int dir4[4][2] = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}}; int dir8[8][2] = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}}; char dirchar[4] = {'<', '^', '>', 'v'}; // [a,b) int irand(int a, int b) { static mt19937 Rand(static_cast(time(nullptr))); uniform_int_distribution dist(a, b - 1); return dist(Rand); } // [a,b) double drand(int a, int b) { static mt19937 Rand(static_cast(time(nullptr))); uniform_real_distribution dist(a, b); return dist(Rand); } // https://qiita.com/IgnorantCoder/items/3101d6276e9bdddf872c template inline auto transform(const A &v, F &&f) { using result_type = decltype(std::declval()(std::declval())); vector y(v.size()); std::transform(std::cbegin(v), std::cend(v), std::begin(y), f); return y; } // generate vector which has multiple dimension template vector make_v(size_t size, const T &init) { return vector(size, init); } template auto make_v(size_t size, Ts... rest) { return vector(size, make_v(rest...)); } template T Max(vector a) { return *max_element(all(a)); } template T Min(vector a) { return *min_element(all(a)); } template T Sum(vector a) { return accumulate(all(a), (T)0); } // for counting using map template void Add(map &m, T item) { if (m.find(item) == m.end()) { m[item] = 1; } else { m[item]++; } } // for counting using map template void Erase(map &m, T item) { if (m.find(item) == m.end()) { } else { if (m[item] == 1) { m.erase(item); } else { m[item]--; } } } // get method for map with default value template U Get(map m, T key, U def) { if (m.find(key) == m.end()) { return def; } else { return m[key]; } } template inline bool Contains(const set &t, const T &key) { return t.find(key) != t.end(); } template inline bool Contains(const map &t, const T &key) { return t.find(key) != t.end(); } template struct Edge { int from, to; T cost; bool operator<(Edge e) { return cost < e.cost; } Edge(int f, int t, T c) : from(f), to(t), cost(c) {} }; template ostream &operator<<(ostream &os, Edge &edge) { os << "(" << edge.from << "->" << edge.to << ":" << edge.cost << ")"; return os; } template class Graph { int n; bool directed; vector>> edges; public: Graph(int n, bool directed) : n(n), directed(directed), edges(vector>>(n)) {} void add_edge(int s, int t, T cost) { edges[s].emplace_back(s, t, cost); if (!directed) { edges[t].emplace_back(t, s, cost); } } Graph() {} vector> &operator[](size_t i) { return edges[i]; } int size() const { return n; } }; //====================================================== template class SegTree { int n; // 葉の数 vector data; // データを格納するvector T def; // 初期値かつ単位元 function operation; // 区間クエリで使う処理 function update; // 点更新で使う処理 // 区間[a,b)の総和。ノードk=[l,r)に着目している。 T _query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return def; // 交差しない if (a <= l && r <= b) return data[k]; // a,l,r,bの順で完全に含まれる else { T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子 T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子 return operation(c1, c2); } } public: // _n:必要サイズ, _def:初期値かつ単位元, _operation:クエリ関数, // _update:更新関数 SegTree(size_t _n, T _def, function _operation, function _update) : def(_def), operation(_operation), update(_update) { n = 1; while (n < _n) { n *= 2; } data = vector(2 * n - 1, def); } // 場所i(0-indexed)の値をxで更新 void change(int i, T x) { i += n - 1; data[i] = update(data[i], x); while (i > 0) { i = (i - 1) / 2; data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]); } } // [a, b)の区間クエリを実行 T query(int a, int b) { return _query(a, b, 0, 0, n); } // 添字でアクセス T operator[](int i) { return data[i + n - 1]; } }; class SuffixArray { static const int L_type = 0, S_type = 1, LMS_type = 2; static void induce_sort(const vector &v, vector &sa, const vector &type, vector start, vector end) { int len = sa.size(); // L-type の要素を各バケットに前から詰める for (int i = 0; i < len; i++) { if (sa[i] == -1) continue; if (sa[i] - 1 >= 0 && type[sa[i] - 1] == L_type) { sa[start[v[sa[i] - 1]]++] = sa[i] - 1; } if (i != 0 && type[sa[i]] == LMS_type) { sa[i] = -1; } } // S-type の要素を各バケットに後ろから詰める for (int i = len - 1; i >= 0; i--) { if (sa[i] == -1) continue; if (sa[i] - 1 >= 0 && type[sa[i] - 1] != L_type) { sa[--end[v[sa[i] - 1]]] = sa[i] - 1; } } } public: vector str; // 入力配列 vector suffix_array; vector order; // SA における添字: order[suffix_array[i]] = i vector lpc; // SA[i], SA[i+1] の LPC 長 SuffixArray(vector &v, int char_num) { str = v; suffix_array = SA_IS(str, char_num); } SuffixArray(const string &s) { str.resize(s.size()); for (int i = 0; i < s.size(); i++) { str[i] = s[i] - 'a' + 1; } suffix_array = SA_IS(str, 26); } static vector SA_IS(vector &v, int char_num) { if (v.size() == 1) { // 再帰の終わり return vector(1, 0); } v.push_back(0); char_num++; int len = v.size(); vector tmp_sa(len, -1); vector type(len); vector start(char_num), end(char_num); // バケットiの注目範囲 vector LMS; // LMS の開始位置 vector LMS_order(len, -1); // LMS のソート順序(非 LMS では -1) // type の判定 type.back() = S_type; end[0] = 1; for (int i = len - 2; i >= 0; i--) { if (v[i] > v[i + 1]) { type[i] = L_type; if (type[i + 1] == S_type) { LMS.push_back(i + 1); type[i + 1] = LMS_type; LMS_order[i + 1] = 0; } } else if (v[i] < v[i + 1]) { type[i] = S_type; } else { type[i] = type[i + 1]; } end[v[i]]++; } // start, end の計算 start[0] = 0; for (int i = 1; i < char_num; i++) { end[i] += end[i - 1]; start[i] = end[i - 1]; } // Induce Sort の準備 for (int i = 0; i < len; i++) { if (LMS_order[i] != -1) { tmp_sa[--end[v[i]]] = i; } } // end の復元 for (int i = 0; i < char_num - 1; i++) { end[i] = start[i + 1]; } end[char_num - 1] = len; // Induce Sort で LMS-substring をソートする induce_sort(v, tmp_sa, type, start, end); // LMS のみからなる数列を作成する // LMS のソート順序を調べる int counter = 0; int prev_lms = -1; // 1 つ前の LMS の先頭 for (int i = 0; i < len; i++) { if (LMS_order[tmp_sa[i]] != -1) { LMS_order[tmp_sa[i]] = ++counter; if (prev_lms == -1) { prev_lms = tmp_sa[i]; continue; } // 1 つ前の LMS と同じか判定 bool different = false; for (int j = 0; j < len; j++) { // j 文字目(prev_lms+j と tmp_sa[i]+j)をチェック if (prev_lms + j >= len || tmp_sa[i] + j >= len || (j != 0 && (LMS_order[prev_lms + j] != -1 || LMS_order[tmp_sa[i] + j] != -1))) { break; } if (v[prev_lms + j] != v[tmp_sa[i] + j]) { different = true; break; } } if (!different) { LMS_order[tmp_sa[i]] = --counter; } prev_lms = tmp_sa[i]; } } vector new_v; // v での出現順に LMS-substring の順位が並ぶ vector position(len, 0); // 各 LMS の開始位置 counter = 0; for (int i = 0; i < len; i++) { if (LMS_order[i] != -1) { new_v.push_back(LMS_order[i]); position[counter++] = i; } } // SA-IS を再帰適用して LMS をソートする vector lms_sa = SA_IS(new_v, new_v.size()); // Induce Sort の準備 fill(tmp_sa.begin(), tmp_sa.end(), -1); for (int i = lms_sa.size() - 1; i >= 0; i--) { if (LMS_order[position[lms_sa[i]]] != -1) { tmp_sa[--end[v[position[lms_sa[i]]]]] = position[lms_sa[i]]; } } // end の復元 for (int i = 0; i < char_num - 1; i++) { end[i] = start[i + 1]; } end[char_num - 1] = len; // Induce Sort で saffix array を完成させる induce_sort(v, tmp_sa, type, start, end); tmp_sa.erase(tmp_sa.begin()); // 先頭の空文字列を削除 v.pop_back(); // 末尾に足した 0 を削除 return tmp_sa; } void calc_lpc() { if (lpc.size() != 0) return; int len = str.size(); lpc.resize(len); order.resize(len); for (int i = 0; i < len; i++) { order[suffix_array[i]] = i; } int h = 0; for (int i = 0; i < len; i++) { // str[i..] と SA でその前にある接尾辞の LPC を求める if (order[i] == 0) { h = 0; continue; } int j = suffix_array[order[i] - 1]; if (h > 0) h--; while (i + h < len && j + h < len) { if (str[i + h] != str[j + h]) break; h++; } lpc[order[i] - 1] = h; } } }; int main() { ll N; cin >> N; string S; vi start(N); rep(i, N) { start[i] = S.size(); string s; cin >> s; S += s; } dump(S); dump(start); ll M, x, d; cin >> M >> x >> d; SuffixArray SA(S); dump(SA.suffix_array); SA.calc_lpc(); dump(SA.lpc); SegTree st(SA.lpc.size(), INF, [](int a, int b) { return min(a, b); }, [](int a, int b) { return b; }); rep(i, SA.lpc.size()) { st.change(i, SA.lpc[i]); } ll ans = 0; rep(k, M) { int i = (x / (N - 1)) + 1; int j = (x % (N - 1)) + 1; if (i > j) swap(i, j); else j++; x = (x + d) % (N * (N - 1)); i--, j--; dump(i, j, start[i], start[j], SA.order[start[i]], SA.order[start[j]]); ans += st.query(SA.order[start[i]], SA.order[start[j]]); } cout << ans << endl; return 0; }