cqyz oj | 单峰排列

Description

　　一个 1~n 的全排列 A[i] 是单峰的，当且仅当存在某个x使得：

　　　A[1] < A[2] < ... < A[x] > A[x+1] > ... > A[n]

　　例如，对于9的全排列，125798643是单峰排列，123456789也是单峰排列，但356298741就不是。

　　试求n的单峰全排列的个数。

Input

　　输入一个数n。

Output

　　输出n的全排列中单峰排列的个数。由于这个数可能很大，因此你只需要输出它mod 1234567的值。

Sample Input 1 

3

Sample Output 1

4

Hint

n<=2 000 000 000

 

---

发现一种快得多的思路：f[i]表示1~i的单峰排列数，因为i可以插入到前i-1个数形成的单峰排列的峰顶左侧或右侧，

所以f[i]=f[i-1]*2

f[1]=1

所以f[n]=2^(n-1)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define mo 1234567
using namespace std;
typedef long long ll;
int qkpow(int a,int p){
    ll r=1,t=a;
    while(p){
        if(p&1) r = (r*t)%mo;
        t=(t*t)%mo;
        p>>=1;
    }
    return (int)r;
}
int main() {
    int p;
    scanf("%d",&p);
    printf("%d",qkpow(2,p-1));
    return 0;
}