hdu 4565 So Easy!（矩陣+快速冪）

題目大意：就是給出a,b,n,m；讓你求s(n);

解題思路：因為n很可能很大，所以一步一步的乘肯定會超時，我建議看代碼之前，先看一下快速冪和矩陣快速冪，這樣看起來就比較容易，這裡我直接貼別人的推導，應該很容易懂。

看到這裡你應該明白了大概吧！好吧現在繼續看我的代碼吧！！

AC代碼：

#include<stdio.h>
long long c[2][2],d[2];
int main()
{
    long long a,b,n,m,x,y,p,q;
    while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&m)!=EOF)
    {
        c[0][0]=2*a;
        c[0][1]=b-a*a;
        c[1][0]=1;
        c[1][1]=0;
        d[0]=2*a;
        d[1]=2;
        while(n)//矩陣快速冪的實現過程
        {
            if(n&1)
            {
                x=(c[0][0]*d[0]+c[0][1]*d[1])%m;
                y=(c[1][0]*d[0]+c[1][1]*d[1])%m;
                d[0]=x;
                d[1]=y;
            }
            n=n/2;
            x=(c[0][0]*c[0][0]+c[0][1]*c[1][0])%m;
            y=(c[0][0]*c[0][1]+c[0][1]*c[1][1])%m;
            p=(c[1][0]*c[0][0]+c[1][1]*c[1][0])%m;
            q=(c[1][0]*c[0][1]+c[1][1]*c[1][1])%m;
            c[0][0]=x;
            c[0][1]=y;
            c[1][0]=p;
            c[1][1]=q;
        }
        printf("%I64d\n",(d[1]+m)%m);
    }
    return 0;
}