Permutation Concatenation
Contest: Codeforces Global Round 6
Difficulty rating: 3300
Tags: string suffix structures

Let $$$n$$$ be an integer. Consider all permutations on integers $$$1$$$ to $$$n$$$ in lexicographic order, and concatenate them into one big sequence $$$P$$$. For example, if $$$n = 3$$$, then $$$P = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]$$$. The length of this sequence is $$$n \cdot n!$$$.

Let $$$1 \leq i \leq j \leq n \cdot n!$$$ be a pair of indices. We call the sequence $$$(P_i, P_{i+1}, \dots, P_{j-1}, P_j)$$$ a subarray of $$$P$$$.

You are given $$$n$$$. Find the number of distinct subarrays of $$$P$$$. Since this number may be large, output it modulo $$$998244353$$$ (a prime number).

Input format:
The only line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$), as described in the problem statement.

Output format:
Output a single integer — the number of distinct subarrays, modulo $$$998244353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, the sequence $$$P = [1, 2, 2, 1]$$$. It has eight distinct subarrays: $$$[1]$$$, $$$[2]$$$, $$$[1, 2]$$$, $$$[2, 1]$$$, $$$[2, 2]$$$, $$$[1, 2, 2]$$$, $$$[2, 2, 1]$$$ and $$$[1, 2, 2, 1]$$$.

Example input:
2

Example output:
8

Example input:
10

Example output:
19210869

Editorial:
Let $$$LCP$$$ be the longest-common-prefix array associated with a suffix tree of the sequence $$$p$$$. The answer is $$$|p| \cdot (|p| + 1) - \sum_{i=1}^{p} LCP[i]$$$.
Let's calculate $$$c_i$$$ – the number of positions for which $$$LCP[j] = i$$$.
The following holds:
• $$$c_0 = n$$$
• $$$c_i = \frac{n!}{(n-i+1)!} * ((n-i) * (n-i) + 1)$$$ for all $$$i$$$ between $$$1$$$ and $$$n-1$$$
• $$$c_i = n! - c_{i-n}$$$ for all $$$i$$$ between $$$n$$$ and $$$2n-1$$$
• $$$c_i = 0$$$ for all $$$i \geq 2n$$$
Using the above formulas, we can calculate the answer in $$$\mathcal O(n)$$$.
Below follows a proof of the above statement. Beware that it is neither
• complete,
• polished, nor
• interesting
It is just case bashing that I used to convince myself that the pattern I observed during problem preparation is correct, an incomplete transript of my scribbles. Apologies to everybody who expected something nice here.
Proof
Construct the suffix array such that the terminator is strictly larger than $$$n$$$. This doesn't change the answer nor the LCP histogram, and it's easier to reason about.
Here $$$LCP_n[i]$$$ denotes the longest-common-prefix of the suffix starting at position $$$i$$$ with the next suffix in lexicographic order. We will build the knowledge about the LCP values guided by induction over $$$n$$$.
Lemma 1: For every $$$i$$$ between $$$1$$$ and $$$n-1$$$, and for every $$$k$$$ between $$$1$$$ and $$$n!$$$, it holds
$$$$$$LCP_n[k \cdot n + i] = LCP_n[k \cdot n + i - 1] - 1$$$$$$
In other words, the LCP value is largest for the suffix aligned on permutation boundary, and shortening the suffix by one decreases the LCP by one. It is obvious that it can't decrease it more. Why does it always decrease by one? TODO
For the above reason, we only need to consider positions divisible by $$$n$$$ (if we number from $$$0$$$), which we will do in the rest of the text.
Lemma 2: Let $$$i$$$ be between $$$1$$$ and $$$n$$$ and $$$p = [n, n-1, \dots, i+1, i-1, \dots, 2, 1, i]$$$. Then $$$LCP_n[indexof(p)] = n-1$$$. We call such permutation semidecreasing.
Proof: First, let's see that there is no position which has LCP of $$$n$$$ or more (even one that would be lexicographically smaller. Such position needs to have a permutation boundary somewhere, let it be after the number $$$j$$$: $$$[n, n-1, \dots, j] + [j-1, j-2, \dots, 2, 1, i]$$$. Note that the suffix of the left permutation is in decreasing order and it's first element is $$$n$$$. When this happens, the next permutation in must swap $$$n$$$ with the preceding element, and hence the prefix of the right permutation cannot be complemetary to the suffix of the left permutation.
Next, see that there is a subarray of $$$P$$$ that has common prefix of exactly $$$n-1$$$ with this permutation, and the next element is larger. There are two cases:
• $$$i = n$$$, that is, the permutation is $$$[n-1, n-2, \dots, 2, 1, n]$$$. Then there is a suffix $$$[n-1, n-2, \dots, 2, 1, \$]$$$ at the end of $$$P$$$.
• $$$i \neq n$$$, a permutation of form $$$[n, n-1, \dots, i+1, i-1, \dots, 2, 1, i]$$$. Then there is lexicographically larger string with common prefix of length $$$n-1$$$ on the boundary of permutations $$$[i, n, n-1, \dots, i+1, i-1, \dots, 2, 1]$$$ and $$$[i+1, 1, 2, \dots, i-1, i+1, \dots, n-1, n]$$$
Definition (enlarged permutations)
Consider a permutation on $$$n$$$ elements. There are $$$n+1$$$ permutation on $$$n+1$$$ elements that can be obtained from it by prefixing it with a number from set $$$\{0.5, 1.5, \dots, n+0.5\}$$$ and renumbering.
For example, from $$$p = [3,1,2,4]$$$ we obtain $$$q = \{[1,4,2,3,5], [2,4,1,3,5], [3,4,1,2,5], [4,3,1,2,5], [5,3,1,2,4]\}$$$. These enlarged permutations will be of great use within the proofs, as we will see soon. Their LCP values will be closely related.
Lemma 3 (enlarging non-semidecreasing permutations): Let $$$LCP_n[k \cdot n] \geq n$$$. Then $$$LCP_{n+1}[(k + m \cdot n!) \cdot (n+1)] + 2$$$.
In other words, the LCP of enlarged permutations is two more than that of the original permutation, provided the original permutation was having LCP large enough.
Proof: The permutation with corresponding LCP $$$n$$$ and the following one are enlarged with the same number $$$e$$$ (because the last permutation of $$$P_{n-1}$$$ has $$$LCP = n-2$$$ as shown by Lemma 2). The lexicographically following permutation in $$$P_{n-1}$$$ can also be found in $$$P_n$$$, subject to insertion of element $$$e$$$ and renumbering. We will just demonstrate this fact informally.
For example, consider permutation $$$p = [1,2,4,3]$$$. The lexicographically following suffix is on the boundary of permutations $$$q_1 = [3,1,2,4]$$$ and $$$q_2 = [3,1,4,2]$$$. Say we enlarge $$$p$$$ to $$$p' = [3,1,2,5,4]$$$. Then the boundary of permutations $$$q'_1 = [4,3,1,2,5]$$$ and $$$q'_2 = [4,3,1,5,2]$$$ contains the subarray $$$[3,1,2,5,4,3,1]$$$, which is longer than the original LCP by two. Here, we inserted $$$[3]$$$ after the first element and renumbered the old $$$3$$$ to $$$4$$$ and $$$4$$$ to $$$5$$$.
Let's characterize the indices where $$$LCP_n[k \cdot n] < n$$$.
Lemma 4 (enlarging semidecreasing permutations): Let $$$p$$$ be a semidecreasing permutation on $$$n$$$ elements. Consider its enlargement $$$p^{+}$$$ – a permutation on $$$n+1$$$ elements. There are three cases:
• $$$p^{+}$$$ is also semidecreasing. Then $$$LCP_{n+1}[indexof(p^{+})] = n$$$.
• $$$p$$$ is the last permutation and the enlargement element is neither $$$0.5$$$ nor $$$n+0.5$$$. Then $$$LCP_{n+1}[indexof(p^{+})] = n+2$$$.
• Otherwise, $$$LCP_{n+1}[indexof(p^{+})] = n+1$$$.
Proof: The first case is obvious.
In the third case, the enlarged permutation is $$$p^{+} = [i, n+1, n, \dots, i+1, i-1, \dots, 2, 1]$$$. The lexicographically next permutation is on the boundary of $$$[1, i, n+1, n, \dots, i+1, i-1, \dots, 2]$$$ and $$$[1, i+1, 2, 3, \dots, i, i+2, \dots, n, n+1]$$$ and the LCP has length $$$n+2$$$. This is because there is an extra match of $$$i$$$ at the beginning, and $$$1$$$ and $$$i+1$$$ at the end.
The second case is similar to the Lemma 3.
Combined the above and induction on $$$n$$$ yields:
Lemma 5: For all $$$k$$$ it holds $$$LCP_n[k \cdot n] < 2n$$$.
Using induction, we can also count the number of permutations $$$p_n$$$ for which $$$LCP_n[indexof(p_n)] = k$$$. Thanks to Lemma 1 this is extendable to suffices not aligned with a permutation, yielding the $$$c_i$$$ values in the statement.