Jzoj4742 单峰

扩展的灰

于 2017-10-23 18:40:51 发布

阅读量501

点赞数

分类专栏： OI 数学 ----组合数学 Jzoj 文章标签：组合数学快速幂扩展的灰

本文链接：https://blog.csdn.net/JacaJava/article/details/78321763

版权

OI 同时被 3 个专栏收录

321 篇文章

订阅专栏

Jzoj

227 篇文章

订阅专栏

数学

105 篇文章

订阅专栏

博客探讨了如何确定单峰数列的数量。内容指出，当指定一个峰值为n时，其余数字分布于n左侧或右侧的情况对应了一种单峰排列。因此，解决方案是2的(N-1)次方。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

很明显，山峰一定是n

那么无论其他的数在n的左边还是右边都对应一种单峰数列

ok，答案就是2^(N-1)

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define L long long
#define M 1000000007
using namespace std;
L pow(L x,L k){
	L S=1;
	for(;k;x=x*x%M,k>>=1)
		if(k&1) S=S*x%M;
	return S;
}
int main(){
	L n;
	scanf("%lld",&n);
	printf("%lld\n",pow(2,n-1));
}