递推数列

方法一:矩阵快速幂

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

typedef long long ll;
#define _for(i, a, b) for(int i = a; i < b; i++)
const int mod = 10000;

template<int row, int col>
struct Matrix{
    int r, c;
    ll ele[row][col];

    Matrix();
    Matrix(int a, int b): r(a), c(b) {
        memset(ele, 0, sizeof(ele));
    }
    ll &operator()(int a, int b){
        return ele[a][b];
    }    
};

template<int m, int n>
Matrix<m, n> qpowmod(Matrix<m, n>mat, ll k, int mod){
    Matrix<m, n> ans = mat;
    for(k--; k; mat = mulmod(mat, mat, mod), k >>= 1){
        if(k & 1){
            ans = mulmod(ans, mat, mod);
        }    
    }
    return ans;
}

template<int m, int n, int p>
Matrix<m, p> mulmod(Matrix<m, n>m1, Matrix<n, p>m2, int mod){
    Matrix<m, p> ret(m1.r, m2.c);
    _for(i, 0, m1.r){
        _for(k, 0, m1.c){
            _for(j, 0, m2.c){
                ret(i, j) = (ret(i, j) + m1(i, k) * m2(k, j) % mod) % mod; 
//                ret(i, j) += m1(i, k) * m2(k, j);
            }
        }
    }
    return ret;
}
template<int m, int n>
istream &operator>>(istream &is, Matrix<m, n> &mat){
    _for(i, 0, mat.r){
        _for(j, 0, mat.c){
            is >> mat(i, j);
        }
    }
    return is;
} 
template<int m, int n>
ostream &operator<<(ostream &os, Matrix<m, n> &mat){
    _for(i, 0, mat.r){
        _for(j, 0, mat.c){
            os << mat(i, j) << ' ';
        }
        os << endl;
    }
    return os;
} 
const int maxn = 10;
int main(){
    int a0, a1, p, q, k;
    cin >> a0 >> a1 >> p >> q >> k;
    Matrix<maxn, maxn> init(2, 1);
    init(0, 0) = a1, init(1, 0) = a0;

    Matrix<maxn, maxn> mat(2, 2);    
    mat(0, 0) = p, mat(0, 1) = q;
    mat(1, 0) = 1, mat(1, 1) = 0;

    auto tmp = mulmod(qpowmod(mat, k - 1, mod), init, mod);
    cout << tmp(0, 0);

    return 0;
}