题解 CF1391C 【Cyclic Permutations 】
绝顶我为峰
2020-08-10 15:32:12
~~本题有多种推柿子方法,都可以通过本题~~
### 方法一:暴力+ OEIS
暴力算出前 10 项的值,直接丢进 OEIS 查询,希望能有
~~然后居然真的有~~
[就是这个序列](https://oeis.org/A059204)
发现这个序列通项公式是 $f(n)=n!-2^{n-1}$ ,写出来,没了(
~~但是这个方法的缺点是在考场上并不能使用~~
---
### 方法二:找规律
发现只要找到一组 $i,j,k$,使得 $i<j<k,a_i>a_j,a_k>a_j$,那么序列就是合法的
容易得出如果一个序列是不合法的,当且仅当这个序列是单峰的
序列总数为 $n!$,单峰序列怎么计算呢?
考虑枚举峰值,显然峰值处只能是序列最大值,我们设峰值在第 $i$ 位
然后我们考虑其他数字的位置,显然我们要把剩下的 $n-1$ 个数分成两组,一组有 $i-1$ 个数,另一组有 $n-i$ 个数,那么答案就是 $\tbinom{n-1}{i-1}$
总的不合法序列数: $\sum_{i=1}^n\tbinom{n-1}{i-1}=\sum_{i=0}^{n-1}\tbinom{n-1}{i}=2^{n-1}$
这个式子和上面找到的通项公式是一致的