Codeforces Round #663 (Div. 2)　C. Cyclic Permutations　(构造,图?)　　

题意:对于某个序列,若\(1\le i\le n\),\(1\le j\le i\)且\(p_j>p_i\),或者\(1\le i\le n\),\(i<j \le n\)且\(p_j>p_i\),那么就可以在\(i\)和\(j\)之间连一条边,求有多少能够成环的长度为\(n\)的序列.
题解:对于长度为\(n\)的序列,也就是有\(n\)个点,那么要成环的话,边数必须\(\ge n\),所以我们要让能连的边数\(<n\),再思考一下,对于每个数,除了\(n\),对于\([1,n-1]\)范围的数,每个数都有比它大的数,所以最小的总边数一定是\(n-1\),再转换一下,也就是说,假如某个数的两边都有比它大的数,那么就一定会成环.直接求成环数可能不好求,我们用总情况\(n!\)-\(不能成环数\).如果一个序列不能成环,那么所有数的两边不可能有数都比它本身大,也就是不能有波谷,那么我们从\([1,n]\)从小到大依次放(保证两头小,中间大),每个数都有两种选择,放在最左侧或最右侧,最后一定会剩下一个数别无选择,所以总情况是\(2^{n-1}\),那么最后答案就是\(n!-2^{n-1}\)啦～～

代码:

int n;

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);

    scanf("%d",&n);

    ll sum=1;

    for(int i=1;i<=n;++i){

        sum=sum*i%mod;

    }

    ll tmp=1;

    for(int i=1;i<n;++i){

        tmp=tmp*2%mod;

    }

    printf("%lld\n",(sum-tmp+mod)%mod);

    return 0;

}

巴特西

Codeforces Round #663 (Div. 2)　C. Cyclic Permutations　(构造,图?)

最新文章

热门文章

巴特西

Codeforces Round #663 (Div. 2) C. Cyclic Permutations (构造,图?)

最新文章

热门文章

Codeforces Round #663 (Div. 2)　C. Cyclic Permutations　(构造,图?)　　