codeforces-scrape

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

1391C.md (2260B)


      1 Source: https://codeforces.com/problemset/problem/1391/C
      2 
      3 C. Cyclic Permutations
      4 
      5 time limit per test
      6 
      7 1 second
      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 A permutation of length $n$ 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 Consider a permutation $p$ of length $n$, we build a graph of size $n$ using it as follows:
     24 
     25 * For every $1 \leq i \leq n$, find the largest $j$ such that $1 \leq j \lt i$ and $p_j \gt p_i$, and add an undirected edge between node $i$ and node $j$
     26 * For every $1 \leq i \leq n$, find the smallest $j$ such that $i \lt j \leq n$ and $p_j \gt p_i$, and add an undirected edge between node $i$ and node $j$
     27 
     28 In cases where no such $j$ exists, we make no edges. Also, note that we make edges between the corresponding indices, not the values at those indices.
     29 
     30 For clarity, consider as an example $n = 4$, and $p = [3,1,4,2]$; here, the edges of the graph are $(1,3),(2,1),(2,3),(4,3)$.
     31 
     32 A permutation $p$ is cyclic if the graph built using $p$ has at least one simple cycle.
     33 
     34 Given $n$, find the number of cyclic permutations of length $n$. Since the number may be very large, output it modulo $10^9+7$.
     35 
     36 Please refer to the Notes section for the formal definition of a simple cycle
     37 
     38 Input
     39 
     40 The first and only line contains a single integer $n$ ($3 \le n \le 10^6$).
     41 
     42 Output
     43 
     44 Output a single integer $0 \leq x \lt 10^9+7$, the number of cyclic permutations of length $n$ modulo $10^9+7$.
     45 
     46 Examples
     47 
     48 Input
     49 
     50 ```
     51 4
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 16
     58 ```
     59 
     60 Input
     61 
     62 ```
     63 583291
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 135712853
     70 ```
     71 
     72 Note
     73 
     74 There are $16$ cyclic permutations for $n = 4$. $[4,2,1,3]$ is one such permutation, having a cycle of length four: $4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4$.
     75 
     76 Nodes $v_1$, $v_2$, $\ldots$, $v_k$ form a simple cycle if the following conditions hold:
     77 
     78 * $k \geq 3$.
     79 * $v_i \neq v_j$ for any pair of indices $i$ and $j$. ($1 \leq i \lt j \leq k$)
     80 * $v_i$ and $v_{i+1}$ share an edge for all $i$ ($1 \leq i \lt k$), and $v_1$ and $v_k$ share an edge.