1.直接递推

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a0,a1,p,q,k;
    int i;
    while(cin>>a0>>a1>>p>>q>>k)
	{
        int a[k+1];
        a[0]=a0;
        a[1]=a1;
        for(i=2;i<k+1;i++) a[i]=(p*a[i-1]+q*a[i-2])%10000;
        cout<<a[k]<<endl;
    }
}

直接进行k次递推就行了，时间复杂度O（n）

2.快速幂

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2,INF = 0x3f3f3f3f;;
typedef pair<int, int> PII;
const int m=10000;      // 点的数量
int p=0,q=0,k=0;
void mul(int c[],int a[],int b[][N])
{
	int temp[N]={0};
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			temp[i]=(temp[i]+(ll)a[j]*b[j][i])%m;
		}
	}
	memcpy(c,temp,sizeof temp);
}
void mul(int c[][N],int a[][N],int b[][N])
{
	int temp[N][N]={0};
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			for(int k=0;k<N;k++)
			{
				temp[i][j]=(temp[i][j]+(ll)a[i][k]*b...