【HDU 5187】zhx's contest快速べき乗+快速乗

ACチャネル:http://vjudge.net/problem/HDU-5187
【問題の説明】
史上最強のブラシの一つとして、zhxの先生は後輩たちにn題を出させた.zhxはi番目の問題の難易度がiだと考えている.彼はこれらのテーマをきれいに並べたいと思っています.
zhxは、きれいなシーケンス{ai}の次の2つの条件を満たす必要があると考えています.
1:a 1..aiは単調に減少または単調に増加する.
2:ai..anは単調に減少または単調に増加します.
彼はあなたに何種類の配列がきれいか教えてほしいと思っています.答えが大きいので、答えモードpの後の値を出力するだけです.
【問題解】
セグメント全体のシーケンスについて単調に増減する場合は,2つの場合である.
増加後減少または減少後増加の場合:1つのシーケンスの最小値(最大値)を決定し、その他は左または右で2^(n-1)*2種類あります.
一方,この2^n種の場合では単調な増減を2回繰り返し計算した.
だから答えは2^n-2
データ範囲が広いため、直接高速べき乗はできません.高速乗が必要です.

/*************
  HDU 5187
  by chty
  2016.11.1
*************/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
ll n,mod;
ll mul(ll x,ll y) {return ((x*y-(ll)(((long double)x*y+0.5)/mod)*mod)%mod+mod)%mod;}//     
ll fast(ll a,ll b){ll ans=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ans=mul(ans,a);return ans;}//     
int main()
{
    while(~scanf("%lld%lld",&n,&mod))
    {
        if(n==1) printf("%lld
",n%mod);
        else printf("%lld
",(fast(2,n)+mod-2)%mod);
    }
    return 0;
}