Fibonacci sequence

Question

Fibonacci sequence is

Input

Input is integer $n$ ($0\le n\le 1000$)

Output

Since $f(n)$ can be really big, hence output $f(n)\mathrm{mod}998244353$

Answer

递归（失败）

每次教到递归都会教如何用其来解 Fibonacci sequence

def fib(n: int) -> int:
	MOD = 998244353
    if n >= 2:
        return (fib(n-1) + fib(n-2)) % MOD
    return 1
print(fib(int(input(""))))

但是这个算法复杂度为 $O(2^n)$，如果 $n$ 太大的话提交到 OJ 会失败

迭代

用回最传统的方法反而可以解题

def fib(n: int) -> int:
	MOD = 998244353
    if n < 2:
        return 1
    prev, now = 1, 1
    for _ in range(2, n + 1):
        prev, now = now, (prev + now) % MOD
    return now
    
print(fib(int(input())))

把 $f(n-2)$ 赋值为 prev 、$f(n-1)$ 赋值为 now
有一点需要注意的是，prev, now = now, (prev + now) % MOD 不可以分开写

# 错误示范
prev = now
now = (prev + now) % MOD

这样写的话，第二行的 prev 便成为 now 的值

now = (prev + now) % MOD
# 等价于
now = (now + now) % MOD

因此 prev, now 必须要写在同一行

C++ 版本

#include <iostream>
using namespace std;

long fib(int n) {
    long MOD = 998244353;
    if (n<2) return 1;
    long prev = 1, now = 1;
    for (int i = 2; i<=n; i++){
        long temp = now;
        now = (prev + now) % MOD;
        prev = temp;
    }
    return now;
}

int main(){
    int num;
    cin >> num;
    cout << fib(num);
}