HDU5187 zhx's contest(计数问题)

?

题意：

从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 
  
   
#include 
   
     #include 
    
      #include 
     
       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 ,1%p); continue; } LL ans = 2; ans = quick_mod(ans,n,p); ans =(ans - 2 + p)%p; printf(%I64d ,ans); } return 0; } 
     
    
   
  

?

?