【题目描述】
一个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.