学步园

。。。题意在这里。

http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=571&pid=1002

我找出来的规律为 ai+1=ai +2，然后我就用矩阵快速幂。。两个数相乘的时候爆掉范围。。

所以要把乘法变成加法快速幂。。

在矩阵快速幂的基础上再加法快速幂。

代码。

//author: CHC
//First Edit Time:    2015-03-14 19:37
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef unsigned long long ULL;
//typedef unsigned __int64 LL;
const int MAXN=2;
ULL MOD;
ULL quickadd(ULL a,ULL b){
    ULL ans=0;
    while(a>0){
        if(a&1)ans=(ans+b)%MOD;
        a>>=1;
        b=(b+b)%MOD;
    }
    return ans;
}
//C=A*B
void mul(ULL A[][MAXN],ULL B[][MAXN],ULL C[][MAXN]){
    ULL tmp[MAXN][MAXN];
    memset(tmp,0,sizeof(tmp));
    for(int i=0;i<MAXN;i++){
    for(int j=0;j<MAXN;j++){
    for(int k=0;k<MAXN;k++){
        //tmp[i][j]+=(A[i][k]*B[k][j])%MOD;
        tmp[i][j]+=quickadd(A[i][k],B[k][j])%MOD;
        tmp[i][j]%=MOD;
    }
    }
    }
    for(int i=0;i<MAXN;i++){
    for(int j=0;j<MAXN;j++){
        C[i][j]=(tmp[i][j]+MOD)%MOD;
    }
    }
}
ULL quickpow(ULL n){
    if(n==1ULL)return 1ULL%MOD;
    if(n==2ULL)return 2ULL%MOD;
    if(n==3ULL)return 6ULL%MOD;
    ULL ans[][MAXN]={{2ULL,2ULL},{0ULL,0ULL}};
    ULL base[][MAXN]={{2ULL,0ULL},{1ULL,1ULL}};
    n-=2ULL;
    while(n>0){
        //printf("here\n");
        if((n&1ULL)==1ULL)mul(ans,base,ans);
        mul(base,base,base);
        n>>=1;
    }
    return ans[0][0]%MOD;
}
int main()
{
    ULL n;
    while(~scanf("%I64u%I64u",&n,&MOD)){
        printf("%I64u\n",quickpow(n));
    }
    //MOD=1e+9 +7;
    //while(~scanf("%llu",&n)){
        //printf("%llu\n",quickpow(n));
    //}
    return 0;
}