HDU 4565矩阵快速幂—— So Easy!

题目链接

借鉴别人的一张解题思路

转化成了 (a^n + b^n) %M

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
typedef  long long ll;
ll MOD ;


struct Matrix {
    ll a[2][2];
    Matrix() {
        memset(a, 0, sizeof(a));
    }

    Matrix operator * (const Matrix y) {
        Matrix ans;
        for(int i = 0; i <= 1; i++)
            for(int j = 0; j <= 1; j++)
                for(int k = 0; k <= 1; k++)
                    ans.a[i][j] += a[i][k]*y.a[k][j];
        for(int i = 0; i <= 1; i++)
            for(int j = 0; j <= 1; j++)
                ans.a[i][j] %= MOD;
        return ans;
    }

    void operator = (const Matrix b) {
        for(int i = 0; i <= 1; i++)
            for(int j = 0; j <= 1; j++)
                a[i][j] = b.a[i][j];
    }
};

ll solve(ll a,ll b,ll n) {
    Matrix ans, trs;

    ans.a[0][1] = 1;
    //初始值
    ans.a[0][0] = a;
    ans.a[0][1] = 2;

    // f(n) = a*f(n-1) + b * f(n-2);
    trs.a[0][0] = a;
    trs.a[1][0] = -b;
    trs.a[0][1] = 1;


    while(n) {
        if(n&1)
            ans = ans*trs;
        trs = trs*trs;
        n >>= 1;
    }
    return (ans.a[0][1]+ans.a[1][1]+MOD)%MOD;//improtant
}


int main() {

     ios_base::sync_with_stdio(false);
//    freopen("data.txt","r",stdin);
    ll aa,bb,m,n;
    while(cin>>aa>>bb>>n>>m)
    {
        ll p = 2*aa;
        ll q = aa*aa-bb;
        MOD  = m;
        cout<<solve(p,q,n)<<endl;
    }
    return 0;
}