题目链接：

pid=4990" style="color:rgb(255,153,0); text-decoration:none; font-family:Arial; line-height:26px">http://acm.hdu.edu.cn/showproblem.php?pid=4990

思路：曾经有一个矩阵乘法的做法请戳这儿。。

。

。

開始我们把数都不模。。。

能够得到一个规律

n：1        ans：1      4^0 
                        n：2     ans：2         2*(4^0)

2                
5      4^0+4^1                        4              10 
     2*(4^0+4^1)

3                 21    4^0+4^1+4^2                6 
            42      2*(4^0+4^1+4^2  )

7                 85    4^0+4^1+4^2+4^3         8 
            170   
2*(4^0+4^1+4^2+4^3  )

所以能够看出规律。。

。

。然后我们直接计算。

。

。。。注意不能用等比数列的求和公式。。。。得用分治法中的等比数列求和。。。。。

code:

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef __int64 LL;

int mod;

LL power(LL p,LL n)    //高速幂

{

    LL sq=1;

    while(n>0)

    {

        if(n%2) sq=sq*p%mod;

        n/=2;

        p=p*p%mod;

    }

    return sq;

}

LL sum(LL p,LL n)     //等比数列求和

{

    if(n==0) return 1;

    if(n%2)

    {

        return (sum(p,n/2)*(1+power(p,n/2+1)))%mod;

    }

    else

    {

        return (sum(p,n/2-1)*(1+power(p,n/2+1))+power(p,n/2))%mod;

    }

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)==2)

    {

        mod=m;

        int ans=0;

        if(n&1)

        {

            ans=sum(4,n/2);

        }

        else

        {

            ans=sum(4,n/2-1);

            ans*=2;

        }

        printf("%d\n",ans%mod);

    }

    return 0;

}