UVA 10844 Bloques - 貝爾數與高精度楊輝三角優化

題目大意

給定 n（≤ 900），求將 n 個元素分成若干非空子集的方法數（即貝爾數 B_n）。答案極大（n=900 時超過 1700 位），需高精度輸出。

遞推關係

貝爾數可透過「第二類斯特靈數」S(n,k) 計算：B_n = Σ S(n,k)。
S(n,k) = S(n-1,k-1) + k * S(n-1,k)。
直接 DP 需高精度乘法，會超時。

楊輝三角優化（純加法）

構建三角表 T[i][j]：
T[1][1] = 1
T[i][1] = T[i-1][i-1]
T[i][j] = T[i][j-1] + T[i-1][j-1] (j ≥ 2)
則 B_i = T[i][i]。
此法將乘法轉為純加法，極大提升高精度運算速度。

高精度實作

採用 base = 10^8 壓位儲存（每個 int 存 8 位十進制），實現大整數加法、輸出（補零對齊）。

完整程式碼

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 1800;
struct BigInt {
    int len, num[MAXN];
    BigInt() { len = 0; memset(num, 0, sizeof(num)); }
    void DelZero() { while (len && num[len-1]==0) len--; if(!len) num[len++]=0; }
    void Print() { printf("%d", num[len-1]); for(int i=len-2;i>=0;i--) printf("%08d", num[i]); }
    BigInt operator+(const BigInt& b) const {
        BigInt ans; long long sum = 0;
        for(int i=0;i