d266 - 退休的福利
題目描述
題目描述了退休福利的計算方式：第一天得到 1 顆米，第二天得到 2 顆米，第三天得到 4 顆米，以此類推，每天得到的米數都是前一天的兩倍。要求計算第 N 天總共得到的米數。
解題思路
這道題的本質是計算一個等比數列的和，其中首項為 1，公比為 2，項數為 N。由於米數會非常大，直接使用數值型別可能會溢位。因此，程式碼使用字串來表示米數，並使用自定義的 add 函數來進行大數加法。程式碼預先計算了前 1000 天的米數，並將結果儲存在 a 和 b 陣列中。a[i] 儲存第 i 天得到的米數（2的i-1次方），b[i] 儲存前 i 天得到的總米數。讀取輸入 n 後，直接輸出 b[n-1] 即可。
複雜度分析
- 時間複雜度: O(N) (預計算部分，N <= 1000) + O(1) (查詢部分)
- 空間複雜度: O(N) (儲存預計算結果的陣列)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
using namespace std;
string a[1001]={"1"},b[1001]={"1"};
inline string add(string x,string y){
int xx[303]={0},xl(x.length()-1),i(0);
string ans;
for(;i<=xl;++i){
xx[i]+=y[xl-i]+x[xl-i]-96;
if(xx[i]>9){
xx[i]-=10;
++xx[i+1];
}
}
++xl;
if(!xx[xl])--xl;
for(;xl>=0;--xl)
ans+=xx[xl]+48;
return ans;
}
inline void write(string x) {
for(int i=0,xl=x.length();i<xl;++i)
putchar_unlocked(x[i]);
putchar_unlocked(10);
}
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
int main(){
int n;
for(int i=1;i<1001;++i){
a[i]=add(a[i-1],a[i-1]);
b[i]=add(a[i],b[i-1]);
}
while(n=read())write(b[n-1]);
}