結果
| 問題 |
No.515 典型LCP
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,165 bytes |
| コンパイル時間 | 1,263 ms |
| コンパイル使用メモリ | 104,028 KB |
| 実行使用メモリ | 96,676 KB |
| 最終ジャッジ日時 | 2025-05-14 13:01:02 |
| 合計ジャッジ時間 | 6,898 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 13 WA * 2 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath> // Use cmath for std::log2 or floor(log2) calculation
#include <vector> // Include vector for std::vector
// Suffix Array structure with efficient O(N log N) construction
struct SuffixArray {
std::string S; // The concatenated string
int N; // Length of the concatenated string S
std::vector<int> SA; // Suffix Array: SA[i] is the starting index of the i-th lexicographically smallest suffix
std::vector<int> LCP; // LCP Array: LCP[i] = LCP(SA[i], SA[i-1])
std::vector<int> rank; // Rank Array: rank[i] is the rank (position in SA) of the suffix starting at index i
std::vector<std::vector<int>> ST; // Sparse Table for Range Minimum Query (RMQ) on LCP array
std::vector<int> Log2; // Precomputed floor(log2) values for fast RMQ calculation
// Constructor initializes the string and builds SA, LCP, and RMQ structures
SuffixArray(const std::string& str) : S(str) {
N = S.length();
buildSA_Efficient(); // Build Suffix Array O(N log N)
buildLCP(); // Build LCP array O(N)
// Precompute floor(log2(i)) for i from 1 to N
Log2.resize(N + 1);
Log2[1] = 0;
for (int i = 2; i <= N; ++i) {
Log2[i] = Log2[i / 2] + 1;
}
buildRMQ(); // Build RMQ structure O(N log N)
}
// O(N log N) Suffix Array construction using prefix doubling and counting sort
void buildSA_Efficient() {
SA.resize(N);
rank.resize(N); // This will store final ranks eventually
std::vector<int> p(N), c(N); // p: permutation array (intermediate SA), c: equivalence classes array
// Initialize counting sort buffer. Size 256 covers ASCII characters. Use N if alphabet size can be larger.
std::vector<int> cnt(std::max(256, N), 0);
// Initial sorting (k=0): based on single characters
for (int i = 0; i < N; ++i) cnt[(unsigned char)S[i]]++; // Use unsigned char to safely handle character codes
for (int i = 1; i < 256; ++i) cnt[i] += cnt[i-1]; // Compute cumulative counts
for (int i = 0; i < N; ++i) p[--cnt[(unsigned char)S[i]]] = i; // Place indices into p based on sorted characters
// Compute initial equivalence classes
c[p[0]] = 0;
int classes = 1; // Number of distinct equivalence classes
for (int i = 1; i < N; ++i) {
if (S[p[i]] != S[p[i-1]]) classes++; // Increment class count if character differs
c[p[i]] = classes - 1; // Assign class ID
}
std::vector<int> pn(N), cn(N); // Temporary arrays for the next iteration steps
// Iteratively refine sorting based on blocks of length 2^k
for (int h = 0; (1 << h) < N; ++h) {
int k_len = (1 << h); // Current block length (power of 2)
// Sort primarily by the second half of the 2*k_len block
// `pn` stores starting indices shifted by -k_len, cyclicly
for (int i = 0; i < N; ++i) {
pn[i] = p[i] - k_len;
if (pn[i] < 0) pn[i] += N; // Handle cyclic shift
}
// Sort `pn` based on the first half classes `c` using counting sort
fill(cnt.begin(), cnt.begin() + classes, 0); // Reset counts for current number of classes
for (int i = 0; i < N; ++i) cnt[c[pn[i]]]++; // Count occurrences of each class
for (int i = 1; i < classes; ++i) cnt[i] += cnt[i-1]; // Cumulative counts
// Place elements into `p` according to sorted order (stable sort)
for (int i = N - 1; i >= 0; --i) p[--cnt[c[pn[i]]]] = pn[i];
// Update equivalence classes `cn` based on the new sorted order `p`
cn[p[0]] = 0;
classes = 1;
for (int i = 1; i < N; ++i) {
// Compare adjacent pairs in `p` based on their two halves' classes
int cur_first = c[p[i]];
int cur_second = c[(p[i] + k_len) % N]; // Class of second half
int prev_first = c[p[i-1]];
int prev_second = c[(p[i-1] + k_len) % N]; // Class of second half
if (cur_first != prev_first || cur_second != prev_second) classes++; // If pair differs, start new class
cn[p[i]] = classes - 1; // Assign new class ID
}
c.swap(cn); // Update `c` with the new classes `cn` for the next iteration
if (classes == N) break; // Optimization: If all suffixes are distinct, sorting is complete
}
SA = p; // The final sorted suffix array is stored in p
// Build the final rank array: rank[i] stores the rank (position in SA) of the suffix starting at index i
for(int i=0; i<N; ++i) {
rank[SA[i]] = i;
}
}
// O(N) LCP array construction using Kasai's algorithm
// Requires SA and rank array (rank[i] = position of suffix i in SA)
void buildLCP() {
LCP.resize(N);
int h = 0; // `h` stores the LCP length of the previous suffix processed
LCP[0] = 0; // LCP[0] is conventionally 0 (for the first suffix in SA)
// Iterate through suffixes in their original text order (index i)
for (int i = 0; i < N; ++i) {
if (rank[i] > 0) { // Check if suffix 'i' is not the lexicographically smallest (rank 0)
int j = SA[rank[i] - 1]; // `j` is the starting index of the suffix preceding suffix `i` in the SA
// Compute LCP between suffix starting at `i` and suffix starting at `j`
while (i + h < N && j + h < N && S[i + h] == S[j + h]) {
h++; // Extend common prefix character by character
}
LCP[rank[i]] = h; // Store the computed LCP length at the rank of suffix `i`
if (h > 0) h--; // Kasai's optimization: LCP for next suffix i+1 is at least h-1
} else {
// If rank[i] is 0 (suffix i is the smallest), LCP[0] is already set. Reset h.
h = 0;
}
}
}
// O(N log N) RMQ precomputation using Sparse Table
void buildRMQ() {
int max_log_N = Log2[N]; // Use precomputed log2 value
ST.assign(max_log_N + 1, std::vector<int>(N));
// Initialize the base level (k=0) of the Sparse Table with LCP values
for (int i = 0; i < N; ++i) {
ST[0][i] = LCP[i];
}
// Build upper levels of the Sparse Table
for (int k = 1; k <= max_log_N; ++k) {
// Compute minimums for ranges of size 2^k
for (int i = 0; i + (1 << k) <= N; ++i) {
ST[k][i] = std::min(ST[k - 1][i], ST[k - 1][i + (1 << (k - 1))]);
}
}
}
// O(1) RMQ query for LCP between suffix starting at i and suffix starting at j
int queryLCP(int i, int j) {
// Based on problem constraints, i != j. If i=j, return maximum possible LCP length.
if (i == j) return N;
int rank_i = rank[i]; // Rank of suffix i
int rank_j = rank[j]; // Rank of suffix j
if (rank_i > rank_j) std::swap(rank_i, rank_j); // Ensure rank_i <= rank_j
// The query range in the LCP array corresponds to ranks from rank_i + 1 to rank_j
int l = rank_i + 1;
int r = rank_j;
int len = r - l + 1; // Length of the query range
if (len <= 0) return 0; // If suffixes are adjacent in SA, range is empty, LCP is LCP[rank_j] if L=R
// Use precomputed floor(log2(len)) for efficient query
int k = Log2[len];
// Query the Sparse Table for the minimum value in the range [l, r]
// The minimum LCP value in this range is the LCP of suffixes i and j
return std::min(ST[k][l], ST[k][r - (1 << k) + 1]);
}
};
// Use unsigned long long for query generation parameters x, d and modulus arithmetic
using ull = unsigned long long;
int main() {
// Faster I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N_int; // Number of strings
std::cin >> N_int;
std::vector<std::string> s(N_int); // Store original strings
std::string T = ""; // Concatenated string with separators
std::vector<int> pos(N_int); // Stores the starting position of each string s_i in T
std::vector<int> lengths(N_int); // Stores the length of each string s_i
int current_pos = 0; // Current position in T while concatenating
char separator = 1; // Use ASCII code 1 as a separator (guaranteed not in 'a'-'z')
// Read input strings and construct the concatenated string T
for (int i = 0; i < N_int; ++i) {
std::cin >> s[i];
pos[i] = current_pos;
lengths[i] = s[i].length();
T += s[i];
T += separator; // Append separator after each string
current_pos += lengths[i] + 1; // Update current position
}
// Initialize the SuffixArray structure with the concatenated string T
SuffixArray sa(T);
int M; // Number of queries
ull x, d; // Query generation parameters (seed and increment)
std::cin >> M >> x >> d;
ull total_lcp = 0; // Accumulator for the sum of LCP lengths
ull N_ull = N_int; // N as unsigned long long for calculations
// Check N_int >= 2 from constraints
ull N_minus_1 = N_ull - 1;
ull modulus = N_ull * N_minus_1;
// Process M queries
for (int k = 0; k < M; ++k) {
// Generate query indices (i', j') based on current x
ull i_prime = (x / N_minus_1) + 1;
ull j_prime = (x % N_minus_1) + 1;
ull final_i, final_j; // Final 1-based indices for the query pair (i, j)
// Apply the transformation rule specified in the problem
if (i_prime > j_prime) { // If i' > j', swap them
final_i = j_prime;
final_j = i_prime;
} else { // If i' <= j', use i' and increment j'
final_i = i_prime;
final_j = j_prime + 1;
}
// Convert final 1-based indices to 0-based indices for array access
int idx1 = final_i - 1;
int idx2 = final_j - 1;
// Get the starting positions of the corresponding original strings in T
int p1 = pos[idx1];
int p2 = pos[idx2];
// Query the LCP using the Suffix Array structure
int current_lcp = sa.queryLCP(p1, p2);
// The computed LCP value must be capped by the minimum of the lengths of the two original strings
current_lcp = std::min({current_lcp, lengths[idx1], lengths[idx2]});
// Add the calculated LCP length to the total sum
total_lcp += current_lcp;
// Update x for the next query generation using modular arithmetic
x = (x + d);
if (modulus > 0) { // Modulus is guaranteed positive since N >= 2
x %= modulus;
}
}
// Output the final total sum of LCP lengths
std::cout << total_lcp << std::endl;
return 0;
}