codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.