【题目描述】
一个n的全排列A[i]是单峰的，当且仅当存在某个x使得A[1]<A[2]<...<A[x]>A[x+1]>...>A[n]。
例如，对于9的全排列，125798643是一个单峰排列，123456789也是一个单峰排列，但356298741就不是。
试求n的单峰全排列的个数。
【输入格式】
一个整数n
【输出格式】
单峰全排列的个数。
因为结果可能很大，请输出结果对1234567取模后的结果。
【样例输入】
3
【样例输出】
4
【数据范围】
1<=n<=2000000000
【分析】
首先明确一点：n必须是“山峰”的最高点，然后依次是n-1，n-2，...，1。其中，n-1这个数可以放在左边的“山”，也可以放在右边的“山”，然后n-2亦是如此……直到1，都有两种放置方案，故最后的结果就是2^n-1。
只知道这一点还不够，如果用循环来求会爆时间，故选用快速幂或者分治法求解，下面的代码是分治的。
var n:longint; function fct(x:longint):qword; begin if x=0 then exit(1); if x=1 then exit(2); fct:=sqr(fct(x div 2)) mod 1234567; if x mod 2<>0 then fct:=fct*2 mod 1234567; end; begin read(n); write(fct(n-1)); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533529.html
