d580 - 末日預言

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個數列的第 n 項，該數列的定義如下：數列的第 0 項和第 1 項都為 1，之後的每一項都是前兩項的和。由於數值可能很大，需要將結果對 2012 取模。

解題思路

題目描述的數列實際上是斐波那契數列。由於 n 的範圍較大 (0 <= N <= 10000)，直接遞迴計算斐波那契數列會導致時間超限。因此，可以使用動態規劃的方法，預先計算出數列的每一項，並儲存在一個陣列中。在計算每一項時，對 2012 取模，以避免數值溢出。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(n)

程式碼

#include <stdio.h>
int main(){
int b[10000]={0,1,2},a;
for(int c=3;c<=10000;c++)
b[c]=(b[c-2]+b[c-1])%2012;
while(scanf("%d",&a)>0)
printf("%d\n",b[a]);
}