题目链接：
思路：曾经有一个矩阵乘法的做法请戳这儿。。
。
。
開始我们把数都不模。。。
能够得到一个规律
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;
}