codeforces-#663-C

codeforces-#663-C

八月 11, 2020

C. Cyclic Permutations

题意

给出一个排列p长度为n ,排列指n个数[1,n]每个数出现1次

现在有如下情况会使两点之间存在无向边:

对于一个位置i 找到最大的位置j (1<=j<i) 且pj>pi

对于一个位置i 找到最小的位置j (i<j<=n) 且pj>pi

翻译一下就是对于一个位置i 往两侧找最靠近i且大于pi的数的位置j建立无向边

给出一个排列长度n 问其中有多少种排列情况会出现环

输出mod 1e9+7

​

题解

什么情况会出现环

画几个例子之后就发现 两侧大中间小 (低洼点) 会出现环

于是题目变成了寻找有多少中排列 会出现 先递减后递增的情况

直接求需要考虑重复计算的情况非常复杂

考虑间接求法 :总排列数- 没有低洼的排列(即排列中只有一个极值点)

具体的没有低洼点的排列是:递减排列，递增排列，先递增后递减排列

如何求这种排列的种数呢

一个排列只有一个最大值 依次从大往小放数字(保证排列没有低洼点)

其他数要么在它左边要么在它右边

比如n=5

取4 放在5的左边/右边

取3 放在5的左边/右边

….

一共有$2^{(n-1)}$中排列方式

而总共有$A_n^n$ 个排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e3+5;
const double Pi=acos(-1);

/*
*/
const ll mod=1e9+7;
ll qpow(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1)ans=(ans*x)%mod;
        x=(x*x)%mod;y>>=1;
    }
    return ans;
}
int main(){
    Turnoff;
    //int t;cin>>t;
    ll n;cin>>n;
    ll tot=1;
    for(ll i=1;i<=n;i++)tot=(tot*i)%mod;
    ll temp=qpow(2,n-1)%mod;
    //cout<<tot<<" "<<temp<<endl;
    cout<<(mod+tot-temp)%mod<<endl;
}