HDU 4565 So Easy!（矩阵快速幂）

题意：就和图片上的一样

思路：和HDU 2256差不多，其实这个是可以推出通向的，所以就可以得到递推关系式

代码：

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;

LL MOD;
///使用前要先对r,c赋值
struct mat{
    long long a[30][30];
    int r,c;
    mat operator *(const mat &b)const{
        mat ret;
        for (int i=0;i<r;i++){
            for (int j=0;j<b.c;j++){
                ret.a[i][j]=0;
                for (int k=0;k<c;k++)
                    ret.a[i][j]+=a[i][k]*b.a[k][j],ret.a[i][j]%=MOD;
            }
        }
        ret.r=r;
        ret.c=b.c;
        return ret;
    }
    void init_unit(int x)
    {
        r=c=x;
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(i==j)a[i][j]=1;
                else a[i][j]=0;
            }
        }
    }
}unit;
mat qmod(mat p,LL n){
    unit.init_unit(p.c);
    mat ans=unit;
    while(n){
        if(n&1)ans=p*ans;
        p=p*p;
        n>>=1;
    }
    return ans;
}

int main()
{
    LL a,b,n;

    while(~scanf("%lld%lld%lld%lld",&a,&b,&n,&MOD)){
        LL aa=(a*2)%MOD;
        double as=(a+sqrt((double)b))*(a+sqrt((double)b));
        LL bb=((LL)ceil(as))%MOD;
        if(n==1){
            cout<<aa<<endl;
            continue;
        }
        if(n==2){
            cout<<bb<<endl;
            continue;
        }
        mat A;
        A.r=2;A.c=2;
        A.a[0][0]=2*a;A.a[0][1]=(b-a*a+MOD)%MOD;
        A.a[1][0]=1;A.a[1][1]=0;
        mat ans;
        ans.r=ans.c=2;
        ans=qmod(A,n-2);
        printf("%lld
",(((ans.a[0][0]*bb)%MOD+MOD)%MOD+((ans.a[0][1]*aa)%MOD+MOD)%MOD)%MOD);
    }
    return 0;
}