算法1

(迭代) $O(n)$

因数字范围太大，递归实现可能时间方面通不过，故使用迭代方式

C++ 代码

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

int main()
{
    int F[10001] = {0};
    F[1] = 1;
    F[2] = 2;
    for(int i = 3; i < 10001; i++){
        F[i] = (F[i-1] + F[i-2]) % 999983;
    }

    int num;
    cin >> num;
    cout << F[num] << endl;

    return 0;
}