a272 - 猥瑣罐頭下樓梯

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算從地下 0 樓到地下 N 樓，每次可以走 1 步或 2 步，共有多少種走法。由於答案可能很大，需要將答案模 10007。

解題思路

這道題目是一個典型的費波那契數列問題。因為每次只能走 1 步或 2 步，所以到達第 n 階的方法數等於到達第 n-1 階的方法數加上到達第 n-2 階的方法數。 初始條件為 f(1) = 1 (走一步) 和 f(2) = 2 (走兩步或走一步再一步)。

由於 N 的範圍很大，直接計算費波那契數列可能會導致整數溢出。因此，我們需要使用模運算來保持結果在可接受的範圍內。 題目要求模 10007。

為了避免計算過大的費波那契數，可以利用費波那契數列的週期性。由於我們進行了模運算，數列會呈現週期性。 程式碼中預先計算了前 20017 個費波那契數，然後利用 n % 20016 來找到對應的結果，避免了計算大數。

複雜度分析

• 時間複雜度: O(N + Q) ，其中 N 是預先計算費波那契數列的長度 (20017)，Q 是輸入的數量。預先計算費波那契數列需要 O(N) 時間，處理每個輸入需要 O(1) 時間。
• 空間複雜度: O(N)，用於儲存預先計算的費波那契數列。

程式碼

#include <iostream>
using namespace std;
int main(int argc, char** argv) {
	ios::sync_with_stdio(0);cin.tie(0);
	int s[20017],n;
	s[1]=1;
	s[2]=2;
	for(int i=3;i<20017;i++){
		s[i]=s[i-1]+s[i-2];
		s[i]%=10007;
	}
	while(cin>>n)
        cout<<s[n%20016]<<"\n"; 
    return 0; 
}