矩阵快速幂/模拟

https://blog.csdn.net/csyifanZhang/article/details/105625010
【为了良好的阅读体验，建议到上面】

乍一看直接模拟，暴力递推，索性NK的数据比较水，过起来很容易

#include<iostream>
#include<string>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;

#define ll int
#define MAX 250
#define inf 10000000
#define mod 10000

int main() {
    ll a0, a1, p, q, k;
    while (cin >> a0 >> a1 >> p >> q >> k) {
        ll cnt = 2, res = 0;
        if (k == 0)cout << a0 << endl;
        else if (k == 1)cout << a1 << endl;
        else {
            while (cnt <= k) {
                res = (q * a0 % mod + p * a1 % mod) % mod;
                a0 = a1, a1 = res; cnt++;
            }
        }
        cout << res << endl;
    }
}

但是这种题直接递推一般是过不了的出题人比较憨除外，这种类似于斐波那契数列的问题，一般都可以高效的转化为矩阵快速幂进行计算，一个详细教程

对公式

我们可以将他写作


这样的话我们进行和正常斐波那契数列一样的递推，就能得出（详细步骤见上面链接的教程）

#include<iostream>
#include<string>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;

#define ll int
#define MAX 250
#define inf 10000000
#define mod 10000

struct mat {
    ll a[2][2];
    mat operator * (mat m) {
        mat res;
        for (int i = 0; i < 2; i++)for (int j = 0; j < 2; j++)res.a[i][j] = 0;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * m.a[k][j]) % mod;
        return res;
    }
};

mat quickPow(mat a, int k) {
    mat res;//对角矩阵
    res.a[0][0] = res.a[1][1] = 1; res.a[0][1] = res.a[1][0] = 0;
    while (k > 0) {
        if (k & 1) res = res * a;
        a = a * a; k >>= 1;
    }
    return res;
}

int main() {
    ll a0, a1, p, q, k;
    while (cin >> a0 >> a1 >> p >> q >> k) {
        ll cnt = 2, ans = 0;
        if (k == 0)cout << a0 << endl;
        else if (k == 1)cout << a1 << endl;
        mat a; a.a[0][0] = p, a.a[0][1] = q, a.a[1][0] = 1, a.a[1][1] = 0;
        mat res = quickPow(a, k - 1);
        ans = ((res.a[0][0] * a1) % mod + (res.a[0][1] * a0) % mod) % mod;
        cout << ans << endl;
    }
}