题目链接：
?pid=5187
题意：
从1~n，有多少种排列
使得a1~ai满足单调递增或者单调递减。
ai~an满足单调递增或者递减。
很明显的组合问题
从n个数种选出i个数剩下的数要满足单调递增或者递减或者递减的规律那么方式唯一
ans =（C(N,0)+C(N,1)+……+C(N,N)） =2^N;
但是这种情况下单调递增和单调递减算了两遍因此要减2
ans= 2^n – 2;
注意n= 1的情况，，由于n比较大，要注意乘法溢出的情况
代码如下：
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>using namespace std;typedef long long LL;LL multi(LL a,LL b, LL c){LL ans = 0;while(b){if(b&1){ans= (ans+a)%c;b–;}b>>=1;a=(a+a)%c;}return ans;}LL quick_mod(LL a,LL b,LL c){LL ans = 1;while(b){if(b&1){ans = multi(ans,a,c);b–;}b>>=1;a=multi(a,a,c);}return ans ;}int main(){LL n,p;while(~scanf("%lld%lld",&n,&p)){if(n==1){printf("%d\n",1%p);continue;}LL ans = 2;ans = quick_mod(ans,n,p);ans =(ans – 2 + p)%p;printf("%I64d\n",ans);}return 0;}
总在盼望未来,愿你的人生美开
