【JZOJ4742】单峰【数论，数学】

题目大意：

题目链接：https://jzoj.net/senior/#main/show/4742

---

思路：

显然最高点只能是$n$。
接下来可以想象成从$n-1$开始放，每次可以放左边或者右边。所以方案数就是$2^{n-1}$。
用快速幂即可。时间复杂度$O(log n)$

---

代码：

#include <cstdio>
using namespace std;
typedef long long ll;

const ll MOD=1e9+7;
ll n;

ll mul(ll x,ll m)
{
	ll ans=1;
	while (m)
	{
		if (m&1) ans=ans*x%MOD;
		x=x*x%MOD;
		m>>=1;
	}
	return ans%MOD;
}

int main()
{
	scanf("%lld",&n);
	printf("%lld",mul(2,n-1));
	return 0;
}