程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU5187 zhx's contest(計數問題)

HDU5187 zhx's contest(計數問題)

編輯:C++入門知識

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;
}

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved