【題解】ZeroJudge e811: 3. 密碼產生器 (Password)

#include <iostream>
#include <cstring>
using namespace std;
#define ll long long
ll P, Q, R, A0, A1, N, mod = 1e4;

struct mat{
    ll a[3][3];
    mat(){
        memset(a, 0, sizeof(a));
    }
    mat operator * (const mat &b)const{
        mat ret;
        for (int i = 0; i < 3; i++){
            for (int j = 0; j < 3; j++){
                for (int k = 0; k < 3; k++){
                    ret.a[i][j] = (ret.a[i][j] + a[i][k] * b.a[k][j]) % mod;
                }
            }
        }
        return ret;
    }
};

void myPrint(ll x){
    char s[4];
    for (int i = 3; i >= 0; i--){
        s[i] = '0' + (x % 10);
        x /= 10;
    }
    for (int i = 0; i < 4; i++){
        cout << s[i];
    }
    cout << "\n";
}
 
int main() {
    cin >> P >> Q >> R >> A0 >> A1 >> N;
    if (N == 1){
        myPrint(A1);
    } else {
        mat ret, p;
        ret.a[0][0] = A1;
        ret.a[1][0] = A0;
        ret.a[2][0] = 1;
        p.a[0][0] = P;
        p.a[0][1] = Q;
        p.a[0][2] = R;
        p.a[1][0] = 1;
        p.a[2][2] = 1;
        N--;
        while (N){
            if (N & 1){
                ret = p * ret;
            }
            p = p * p;
            N >>= 1;
        }
        myPrint(ret.a[0][0]);
    }
    return 0;
}