Suffix Arrays, Adjacent LCPs, and Expectation¶
Problem setter's solution: count distinct and unique substrings using a suffix array and LCPs. Codex (GPT-6): integer doubling sort, expectation derivation, 64-bit queries, noninvertible-denominator handling, and verification. The primary program is std.cpp; a complete suffix automaton solution is available as alternative.cpp.
From Counts to Expectation¶
Let \(D\) be the number of distinct nonempty substrings and \(U\) the number occurring exactly once. The whole string occurs once, so \(U\ge1\) . Each trial succeeds with probability \(p=U/D\) .
The number of trials until the next success is geometric with expectation \(1/p\) . The wait for \(N\) successes is the sum of \(N\) such waits. Linearity of expectation gives \(ND/U\) . The final successful trial is included; do not subtract one. For \(N=0\) , the answer is zero.
Two Suffix-Array Formulas¶
Sort all suffixes lexicographically. Let \(L_i\) be the length of suffix \(i\) in this order, and let \(h_i\) be its longest common prefix with its predecessor. Set \(h_0=h_n=0\) .
Suffixes sharing a prefix form a contiguous interval. Thus the prefixes of suffix \(i\) already represented by earlier suffixes are exactly those of length at most \(h_i\) , proving the formula for \(D\) .
To test occurrence at any other position, only the two neighboring suffixes matter. If a farther suffix shares a prefix, the intervening adjacent suffix also shares it. Hence the longest repeated prefix has length \(\max(h_i,h_{i+1})\) . Longer prefixes occur once and cannot be counted at another suffix, proving the formula for \(U\) . Overlapping occurrences still have different suffix starts and are handled normally.
Build the suffix array by integer rank doubling and two stable counting sorts per round. A linear LCP scan computes neighboring common prefixes. Integer ranks provide exact comparisons without floating-point ranking.
Modular Fractions¶
If \(P\nmid U\) , compute \((N\bmod P)(D\bmod P)U^{-1}\bmod P\) .
If \(P\mid U\) , the bound \(1\le U\le n(n+1)/2<P^2\) means the denominator contains exactly one factor \(P\) . If \(P\mid N\) , divide both \(N\) and \(U\) by \(P\) . Otherwise, if \(P\mid D\) , divide both \(D\) and \(U\) by \(P\) . Otherwise the reduced denominator still contains \(P\) , so print \(-1\) . After cancellation the denominator is invertible. Canceling factors other than \(P\) does not change the residue, so the potentially overflowing product \(ND\) is never formed.
This case is reachable: \(S=a^{11879}b^2c^{84166}\) has \(U=1000000007\) and \(D=1000096051\) . For \(N=1\) , output \(-1\) ; for \(N=P\) , output 96044; for \(N=0\) , output zero.
Complexity and Comparison¶
Time is \(O(n\log n+Q+\log P)\) and space is \(O(n)\) . Counts and queries use 64-bit integers; reduce both factors below \(P\) before modular multiplication.
The suffix automaton provides a separate model based on end-position equivalence classes. Construction is linear for the fixed 94-character alphabet, but dense transitions use \(O(94n)\) space. Both implementations pass the complete data. The suffix array follows the setter's counting method and uses less measured memory here, so it remains primary. Shared modular-fraction code is in expectation.hpp.
Validation and Performance¶
Every formal input has five timing runs and a separate peak-memory run. The standard program's slowest median is 0.033904 seconds and its peak memory is 7.22 MiB. Twice the median, rounded up to 0.5 seconds, gives a 0.5-second reference limit. The automaton's slowest median is 0.069435 seconds, with 80.46 MiB peak memory; both pass.
See the test guide, environment, and individual timings and hashes. Recalibrate on other environments.