题目地址：HDU 4565
这题曾经在上海邀请赛前做过，但是当时一点思路都没有，现在拿起这道题来简直是小菜一碟啊。而且这题跟hdu2256也很像。详情请看：HDU 2256
构造矩阵：
a,b
1,a
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 LL mod; struct matrix { LL ma[3][3]; }init, res; matrix Mult(matrix x, matrix y) { int i, j, k; matrix tmp; memset(tmp.ma,0,sizeof(tmp.ma)); for(i=0;i<2;i++) { for(k=0;k<2;k++) { for(j=0;j<2;j++) { tmp.ma[i][j]=(tmp.ma[i][j]+x.ma[i][k]*y.ma[k][j])%mod; } } } return tmp; } matrix Pow(matrix x, int k) { matrix tmp; int i, j; for(i=0;i<2;i++) for(j=0;j<2;j++) tmp.ma[i][j]=(i==j); while(k) { if(k&1) tmp=Mult(tmp,x); x=Mult(x,x); k>>=1; } return tmp; } int main() { LL a, b, k; while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&k,&mod)!=EOF) { init.ma[0][0]=a; init.ma[0][1]=b; init.ma[1][0]=1; init.ma[1][1]=a; res=Pow(init,k-1); LL ans=(res.ma[0][0]*a+res.ma[0][1])%mod; printf("%I64d\n",(2*ans)%mod); } return 0; }