f255 - 肥貓的保險箱密碼
題目描述
題目要求計算由 0 和 1 組成的長度為 N 的字串有多少種可能的組合。由於 N 的範圍較大 (N <= 10000)，直接使用迴圈或排列組合公式可能會導致整數溢位或時間超時。
解題思路
題目實際上要求的是 2 的 N 次方。但由於 N 的範圍較大，直接計算 2 的 N 次方會導致溢位。因此，程式碼使用字串來表示大數，並實現了大數的加法運算。程式碼預先計算了從 1 到 10000 的 2 的 N 次方，並將結果儲存在 ans 陣列中。對於每個輸入的 N，程式碼直接從 ans 陣列中取出對應的結果並輸出。
複雜度分析
- 時間複雜度: O(N^2) (預計算 2^1 到 2^10000 的加法，每次加法最壞情況下需要遍歷字串) + O(1) (查詢)
- 空間複雜度: O(N) (儲存 2^1 到 2^10000 的字串)
程式碼
#include <iostream>
using namespace std;
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;
}
int n;
string ans[10001]={"1"};
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=1;i<=10000;++i){
ans[i]=add(ans[i-1],ans[i-1]);
}
while(cin >> n){
if(n==0)break;
cout << ans[n] << "\n";
}
}