e604 - Sierpinski's Triangle's secret (I)
題目描述
題目要求計算謝爾賓斯基三角形在給定遞迴次數 n 時，總共有多少個三角形。由於三角形數量會快速增長，因此需要處理大數。
解題思路
題目描述中提到謝爾賓斯基三角形是一種碎形，並且與遞迴有關。觀察可以發現，謝爾賓斯基三角形的三角形數量與遞迴次數 n 之間存在遞迴關係。
初始狀態為 n=0 時，三角形數量為 1。
遞迴關係為：DP[n] = 3 * DP[n-1] + 2。
由於數字可能很大，因此不能使用標準的整數類型，需要使用字串來表示大數，並實現大數的加法和乘法運算。
程式碼使用動態規劃 (DP) 來儲存每個遞迴次數對應的三角形數量，避免重複計算。
複雜度分析
- 時間複雜度: O(N * M^2)，其中 N 是輸入的最大值 (10000)，M 是大數的平均長度。大數加法和乘法操作的時間複雜度都是 O(M^2)。
- 空間複雜度: O(N * M)，其中 N 是輸入的最大值 (10000)，M 是大數的平均長度。用於儲存 DP 陣列。
程式碼
#include <iostream>
using namespace std;
string DP[10001]={"1"};
string add(string a,string b){
int tmp[10001]={0},al=a.length(),bl=b.length();
string c;
for(int i=0;i<al;++i)tmp[al-i-1]+=a[i]-'0';
for(int i=0;i<bl;++i)tmp[bl-i-1]+=b[i]-'0';
for(int i=0;i<10000;++i)
if(tmp[i]>9){
++tmp[i+1];
tmp[i]-=10;
}
for(int i=10000;i>=0;--i)
if(tmp[i]){
al=i;
break;
}
for(int i=al;i>=0;--i)c+=tmp[i]+'0';
return c;
}
string mul(string a,string b){
int tmp[10001]={0},al=a.length(),bl=b.length();
for(int i=al-1,it=0;i>=0;--i,++it)
for(int j=bl-1,it2=it;j>=0;--j,++it2)
tmp[it2]+=(a[i]-'0')*(b[j]-'0');
int tl=0;
for(int i=0;i<10000;++i){
if(tmp[i])tl=i;
if(tmp[i]>=10){
tmp[i+1]+=tmp[i]/10;
tmp[i]%=10;
}
}
string rt;
for(int i=tl;i>=0;--i)
rt+=tmp[i]+'0';
return rt;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=1;i<10001;++i)
DP[i]=add(mul(DP[i-1],"3"),"2");
int n;
while(cin >> n)
cout << DP[n] << "\n";
}