---
title: "递推数列"
created: 2025-11-28
tags:
  - 算法
---

# 递推数列

## 题目 [递推数列](https://www.acwing.com/problem/content/description/3395/)

![[image-7a751113.png]]

## 思路分析

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=10010,mod=10000;

LL fn[N];

int main()

{

    int a0,a1,p,q,k;

    cin>>a0>>a1>>p>>q>>k;

    fn[0]=a0,fn[1]=a1;

    if(k==1){

        cout<<0;

        return 0;

    }

    for(int i=2;i<=k;i++)

        fn[i]=(fn[i-1]*p%mod+fn[i-2]*q%mod)%mod;

    cout<<fn[k];

    return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=10010,mod=10000;

int main()

{

    int a0,a1,p,q,k;

    cin>>a0>>a1>>p>>q>>k;

    if(k==1){

        cout<<0;

        return 0;

    }

    int fn;

    for(int i=2;i<=k;i++){

        fn=(a1*p%mod+a0*q%mod)%mod;

        a0=a1,a1=fn;

    }

    cout<<fn;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[递推|递推]] 🏠 [[00-刷题理模型]] ➡️ [[飞行员兄弟|飞行员兄弟]]