1284C.md (2979B)
1 Source: https://codeforces.com/problemset/problem/1284/C 2 3 C. New Year and Permutation 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 1024 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Recall that the permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 22 23 A sequence $a$ is a subsegment of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. We will denote the subsegments as $[l, r]$, where $l, r$ are two integers with $1 \le l \le r \le n$. This indicates the subsegment where $l-1$ elements from the beginning and $n-r$ elements from the end are deleted from the sequence. 24 25 For a permutation $p_1, p_2, \ldots, p_n$, we define a framed segment as a subsegment $[l,r]$ where $\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l$. For example, for the permutation $(6, 7, 1, 8, 5, 3, 2, 4)$ some of its framed segments are: $[1, 2], [5, 8], [6, 7], [3, 3], [8, 8]$. In particular, a subsegment $[i,i]$ is always a framed segments for any $i$ between $1$ and $n$, inclusive. 26 27 We define the happiness of a permutation $p$ as the number of pairs $(l, r)$ such that $1 \le l \le r \le n$, and $[l, r]$ is a framed segment. For example, the permutation $[3, 1, 2]$ has happiness $5$: all segments except $[1, 2]$ are framed segments. 28 29 Given integers $n$ and $m$, Jongwon wants to compute the sum of happiness for all permutations of length $n$, modulo the prime number $m$. Note that there exist $n!$ (factorial of $n$) different permutations of length $n$. 30 31 Input 32 33 The only line contains two integers $n$ and $m$ ($1 \le n \le 250\,000$, $10^8 \le m \le 10^9$, $m$ is prime). 34 35 Output 36 37 Print $r$ ($0 \le r \lt m$), the sum of happiness for all permutations of length $n$, modulo a prime number $m$. 38 39 Examples 40 41 Input 42 43 ``` 44 1 993244853 45 ``` 46 47 Output 48 49 ``` 50 1 51 ``` 52 53 Input 54 55 ``` 56 2 993244853 57 ``` 58 59 Output 60 61 ``` 62 6 63 ``` 64 65 Input 66 67 ``` 68 3 993244853 69 ``` 70 71 Output 72 73 ``` 74 32 75 ``` 76 77 Input 78 79 ``` 80 2019 993244853 81 ``` 82 83 Output 84 85 ``` 86 923958830 87 ``` 88 89 Input 90 91 ``` 92 2020 437122297 93 ``` 94 95 Output 96 97 ``` 98 265955509 99 ``` 100 101 Note 102 103 For sample input $n=3$, let's consider all permutations of length $3$: 104 105 * $[1, 2, 3]$, all subsegments are framed segment. Happiness is $6$. 106 * $[1, 3, 2]$, all subsegments except $[1, 2]$ are framed segment. Happiness is $5$. 107 * $[2, 1, 3]$, all subsegments except $[2, 3]$ are framed segment. Happiness is $5$. 108 * $[2, 3, 1]$, all subsegments except $[2, 3]$ are framed segment. Happiness is $5$. 109 * $[3, 1, 2]$, all subsegments except $[1, 2]$ are framed segment. Happiness is $5$. 110 * $[3, 2, 1]$, all subsegments are framed segment. Happiness is $6$. 111 112 Thus, the sum of happiness is $6+5+5+5+5+6 = 32$.