题解 | #递推数列#

#include <iostream>
#include <cstring>
#include<algorithm>
using namespace std;

typedef long long ll;


const int MOD = 10000;

ll a[5], b[2][3];

void mul(ll c[], ll a[], ll b[][3]){
    ll temp[5] = {0};

    for(int i = 0; i < 3; i ++){
        for(int j = 0; j < 3; j ++){
            temp[i] = (temp[i] + a[j] * b[j][i]) % MOD;
        }
    }

    memcpy(c, temp, sizeof temp);

}

void mul(ll c[][3], ll a[][3], ll b[][3]){
    ll temp [2][3] = {0};

    for(int i = 0; i < 2; i ++){
        for(int j = 0; j < 3; j ++){
            for(int k = 0; k < 3; k  ++){
                temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    memcpy(c, temp, sizeof temp);
}

void qmi(ll a[], ll b[][3], ll k){
    k --;

    while(k){
        if(k & 1) mul(a, a, b);
        mul(b, b, b);
        k >>= 1;

    }

    
}
int main(){
    ll a0, a1, p, q, k;
    cin >> a0 >> a1 >> p >> q >> k;
    a[0] = a1, a[1] = a0, a[2] = 1;
    b[0][0] = p, b[1][0] = q;
    b[0][1] = 1, b[1][2] = 1;

    if(k == 0){
        cout << a0 % MOD;
    }
    else if(k == 1) {
        cout << a1 % MOD;
    }
    else{
        //cout << "hello";
        qmi(a, b, k);
        cout << a[0] % MOD;
    }
    

}