题解 CF1391C 【Cyclic Permutations 】

~~本题有多种推柿子方法，都可以通过本题~~ ### 方法一：暴力+ 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}$ 这个式子和上面找到的通项公式是一致的