1091D.md (1787B)
1 Source: https://codeforces.com/problemset/problem/1091/D 2 3 D. New Year and the Permutation Concatenation 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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!$. 22 23 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$. 24 25 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). 26 27 Input 28 29 The only line contains one integer $n$ ($1 \leq n \leq 10^6$), as described in the problem statement. 30 31 Output 32 33 Output a single integer — the number of subarrays of length $n$ having sum $\frac{n(n+1)}{2}$, modulo $998244353$. 34 35 Examples 36 37 Input 38 39 ``` 40 3 41 ``` 42 43 Output 44 45 ``` 46 9 47 ``` 48 49 Input 50 51 ``` 52 4 53 ``` 54 55 Output 56 57 ``` 58 56 59 ``` 60 61 Input 62 63 ``` 64 10 65 ``` 66 67 Output 68 69 ``` 70 30052700 71 ``` 72 73 Note 74 75 In the first sample, there are $16$ subarrays of length $3$. In order of appearance, they are: 76 77 $[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]$. 78 79 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$.