e932 - pB. 數字拆解
題目描述
題目要求計算給定正整數 n 的整數分割方案數。整數分割是指將一個正整數分解成若干個正整數的和，其中順序不考慮。例如，對於 n=4，可能的分割方案有：4, 3+1, 2+2, 2+1+1, 1+1+1+1，總共有 5 種方案。
解題思路
此題可以使用動態規劃解決。由於 n 的範圍較小 (1 ≤ n ≤ 100)，可以直接使用一個陣列 ans 儲存從 1 到 100 的每個數字的整數分割方案數。程式碼中預先計算了 ans 陣列的值，然後直接輸出 ans[n]。預計算的過程實際上是動態規劃的應用，但程式碼中直接使用了預計算好的結果，避免了在執行時進行計算。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#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 <stdio.h>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int ans[101]={1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,792,1002,1255,1575,1958,2436,3010,3718,4565,5604,6842,8349,10143,12310,14883,17977,21637,26015,31185,37338,44583,53174,63261,75175,89134,105558,124754,147273,173525,204226,239943,281589,329931,386155,451276,526823,614154,715220,831820,966467,1121505,1300156,1505499,1741630,2012558,2323520,2679689,3087735,3554345,4087968,4697205,5392783,6185689,7089500,8118264,9289091,10619863,12132164,13848650,15796476,18004327,20506255,23338469,26543660,30167357,34262962,38887673,44108109,49995925,56634173,64112359,72533807,82010177,92669720,104651419,118114304,133230930,150198136,169229875,190569292},n;
int main(){
n=read();
write(ans[n]);
}