题目描述

输入

输出

样例输入

2

样例输出

2

数据范围

解法

答案为2^(n-1)，快速幂即可。

证明：显然峰值必定为n，那么对于其他n-1个数，要么放在峰值的左边，要么放在峰值的右边，所以方案数为2^(n-1)。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define ll long long

#define sqr(x) ((x)*(x))

#define ln(x,y) int(log(x)/log(y))

using namespace std;

const char* fin="aP1.in";

const char* fout="aP1.out";

const int inf=0x7fffffff;

const int mo=1000000007;

ll n;

ll ans;

ll qpower(ll a,ll b){

    ll c=1;

    while (b){

        if (b&1) c=(c*a)%mo;

        a=(a*a)%mo;

        b>>=1;

    }

    return c;

}

int main(){

    scanf("%lld",&n);

    ans=qpower(2,n-1);

    printf("%lld",ans);

    return 0;

}

启发

提交时要保证每个变量不会超出int。