当前位置: 代码迷 >> 综合 >> #663 (Div. 2)C. Cyclic Permutations(数学)
  详细解决方案

#663 (Div. 2)C. Cyclic Permutations(数学)

热度:92   发布时间:2024-02-09 00:49:51.0

题目描述

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≤j< i and pj >pi, 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.

Examples

input
4
output
16
input
583291
output
135712853

Note

There are 16 cyclic permutations for n=4. [4,2,1,3] is one such permutation, having a cycle of length four: 4→3→2→1→4.
Nodes v1, v2, …, vk form a simple cycle if the following conditions hold:
k≥3.
vi≠vj for any pair of indices i and j. (1≤i<j≤k)
vi and vi+1 share an edge for all i (1≤i<k), and v1 and vk share an edge.

题目大意

给你一个数n,n的全排列中每一个序列根据如下规则建图:
1<=i<=n,找到最大的j使得1<=j<=i,p[j]>p[i],在i和j之间连一条无向边。
1<=i<=n,找到最小的j使得i<=j<=n,p[j]>p[i],在i和j之间连一条无向边。
问:n的全排列中有多少按照上面的规则建图,图中是有环的。

题目分析

首先我们可以确定:n的全排列一共有n!种情况,也就是说总共有n!种情况。
直接算有多少种情况是有环的不好算,我们可以先算出有多少种情况是没有环的,再用n!减去就行了。
什么样的序列是没有环的呢?根据题意:当一个序列满足先增后减、单调递增或者单调递减时,这个序列构成的图不会含有环。
然后以n(最大的数)为分界线,剩下的n-1个数每个都有两种选择:放在n前面和放在n后面。这样一共就有2n-1种情况,答案即为n!-2n-1

补:对于这n-1个数,我们只能选择它们是放在n前还是n后,因为n前面的数必须满足单调递增,而n后面的数必须满足单调递减。

代码如下
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <iomanip>
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N=1e5+5,mod=1e9+7;
int qmi(int a,int k,int p)		//快速幂模板
{int res=1;while(k){if(k&1) res=(LL)res*a%p;k>>=1;a=(LL)a*a%p;}return res;
}
int f(int x)			//求x的阶乘
{LL res=1;for(int i=2;i<=x;i++)res=res*i%mod;return res;
}
int main()
{int n;cin>>n;cout<<(f(n)-qmi(2,n-1,mod)+mod)%mod<<endl;return 0;
}
  相关解决方案