参考大佬的博客写的很好https://blog.csdn.net/qq_43627087/article/details/107927412?biz_id=102&utm_term=Codeforces%20Round%20#663%20Div.%202&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduweb~default-1-107927412&spm=1018.2118.3001.4187
传送门 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).
Consider a permutation p of length n, we build a graph of size n using it as follows:
For every 1≤i≤n, find the largest j such that 1≤jpi, and add an undirected edge between node i and node j For every 1≤i≤n, find the smallest j such that i<j≤n and pj>pi, and add an undirected edge between node i and node j 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.
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).
A permutation p is cyclic if the graph built using p has at least one simple cycle.
Given n, find the number of cyclic permutations of length n. Since the number may be very large, output it modulo 109+7.
Please refer to the Notes section for the formal definition of a simple cycle
Input The first and only line contains a single integer n (3≤n≤106).
Output Output a single integer 0≤x<109+7, the number of cyclic permutations of length n modulo 109+7.
输入 4 输出 16 输入 583291 输出 135712853
题意：给出一个数n，将1~n，n个数进行全排列形成数组a，每次连接第i个位置和左边第一个大于a[i]的位置，第i个位置和右边第一个大于a[i]的位置，问有几个排列满足条件
思路：对于n=4,我们列出不能形成环的排列 1234 4321 1342 2431 1243 3421 1432 2341 发现只有两个固定格式…1…4…和…4…1…形成对称，所以我们可以先计算一个格式再乘以二即可，对于…1…n…，1~n之间的数字必须是升序，n之后的数字必须为降序并且1-n之间的数字个数取值【0，n-2】所以不符合条件的排列有2*[C(0,n-2)+C(1,n-2)+C(2,n-2)…C(n-2,n-2)]=2*2的n-2次方=2的n-1次方,这里贴出排列求和公式C(0,n)+C(1,n)+C(2,n)…C(n,n)=2的n次方所以满足条件的排列有n！-2的n-1次方
