d639 - 企鵝村三兄弟penguin

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個遞迴數列的第 n 項的值，數列的定義是：前三項固定為 1, 1, 1，從第四項開始，每一項都是前三項的和，並且所有項的值都需要模 10007。

解題思路

觀察數列的特性，可以發現數列的生成方式是基於前三項的和。由於題目要求模 10007，因此在計算和的過程中需要進行模運算。程式碼首先計算數列的前幾項，直到出現特定的模式 (3, 5, 9)，然後利用這個模式的週期性來計算第 n 項的值。具體來說，程式碼預先計算數列的一部分，儲存在 dp 向量中，然後利用 n 與 dp 向量大小的關係，找到對應的數列項。由於數列具有週期性，因此可以通過取模運算來找到正確的索引。

複雜度分析

• 時間複雜度: O(N)，其中 N 是數列的週期長度。在找到週期後，計算第 n 項的時間複雜度為 O(1)。
• 空間複雜度: O(N)，用於儲存數列的週期部分。

程式碼

#include <iostream>
#include <vector>
using namespace std;
int n,mod=10007,a[3]={1,1,1};
vector <int> dp;
int main(){
	for(int i=1;;++i){
		long long tmp=(a[0]+a[1]+a[2])%mod; 
		if(a[0]==3&&a[1]==5&&a[2]==9&&i>=10)break;
		a[0]=a[1];
		a[1]=a[2];
		a[2]=tmp;
		dp.push_back(tmp);
	} 
	while(cin >> n){
		if(n<=3){
			cout << "1\n";
		}
		else{
			cout << dp[(n-4)%(dp.size()-3)] << "\n";
		}
	}
}