New Year and the Permutation Concatenation
Contest: Good Bye 2018
Difficulty rating: 1700
Tags: combinatorics, dp, math

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 will be $$$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$$$. Its length is defined as the number of its elements, i.e., $$$j - i + 1$$$. Its sum is the sum of all its elements, i.e., $$$\sum_{k=i}^j p_k$$$.

You are given $$$n$$$. Find the number of subarrays of $$$p$$$ of length $$$n$$$ having sum $$$\frac{n(n+1)}{2}$$$. 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 subarrays of length $$$n$$$ having sum $$$\frac{n(n+1)}{2}$$$, modulo $$$998244353$$$.

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

Note:
In the first sample, there are $$$16$$$ subarrays of length $$$3$$$. In order of appearance, they are:

$$$[1, 2, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 3]$$$, $$$[1, 3, 2]$$$, $$$[3, 2, 2]$$$, $$$[2, 2, 1]$$$, $$$[2, 1, 3]$$$, $$$[1, 3, 2]$$$, $$$[3, 2, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 3]$$$, $$$[1, 3, 1]$$$, $$$[3, 1, 2]$$$, $$$[1, 2, 3]$$$, $$$[2, 3, 2]$$$, $$$[3, 2, 1]$$$.

Their sums are $$$6$$$, $$$6$$$, $$$7$$$, $$$6$$$, $$$7$$$, $$$5$$$, $$$6$$$, $$$6$$$, $$$8$$$, $$$6$$$, $$$7$$$, $$$5$$$, $$$6$$$, $$$6$$$, $$$7$$$, $$$6$$$. As $$$\frac{n(n+1)}{2} = 6$$$, the answer is $$$9$$$.

Example input:
3

Example output:
9

Example input:
4

Example output:
56

Editorial:
There are two types of subarrays with length $$$n$$$:
• They are fully formed from one permutations.
• They are a concatenation of a $$$k$$$ long suffix of one permutation, and a $$$n-k$$$ long prefix of the next permutation.
There are $$$n!$$$ such subarrays of the first type, and they all have the the correct sum.
Let's investigate the second type. Recall the algorithm of finding the next permutation in lexicographical order. We find the longest suffix that is in decreasing order, let its length be $$$k$$$. We swap the preceding element $$$x$$$ with the smallest one from the decreasing sequence larger than $$$x$$$, and sort the suffix in increasing order. The prefix of length $$$n - k - 1$$$ is left unchanged, but all longer proper prefixes are different and also change their sum.
Coming back to our problem, if the suffix of length $$$k$$$ is in decreasing order, than the prefix of length $$$n - k$$$ of the next permutation has different sum from the prefix of the same length of the current permutation, hence the subarray has incorrect sum. Conversely, if the suffix of length $$$k$$$ is not in decreasing order, then the prefix of length $$$n-k$$$ of the next permutation equals to the prefix of the current permutation, and its sum is $$$\frac{n(n+1)}{2}$$$.
To find the answer, we must thus subtract the number of suffixes of all permutations that are decreasing. How many of them are there for a fixed $$$k$$$? This is simple – we choose the first $$$n-k$$$ elements freely, and permute them. The rest has to be sorted in a particular way. Hence the number of bad subarrays coming from a suffix of length $$$k$$$ equals $$$\frac{n!}{k!}$$$.
Convince yourself that this approach works correctly even for the last permutation, where there is no next permutation to concatenate its suffixes with.
The answer is:
$$$$$$n \cdot n! - \sum_{k=1}^{n-1} \frac{n!}{k!}$$$$$$
This can be calculated in $$$\mathcal O(n)$$$ without the need of modular division.
There is also a simple recurrence counting the same answer, found by arsijo:
$$$$$$d(n) = \left(d(n-1) + (n-1)! - 1\right) \cdot n$$$$$$