【POJ 1737】Connected Graph

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

struct BigInt
{
    static const int BASE = 10000;
    int s[1000];
    int len;

    BigInt()
    {
        memset(s, 0, sizeof(s));
        len = 0;
        s[len++] = 0;
    }
    
    BigInt operator = (const int &b)
    {
        memset(s, 0, sizeof(s));
        len = 0;
        s[len++] = b;
        int i = 0;
        while (s[i] > BASE)
        {
            s[len++] = (s[i] / BASE);
            s[i] %= BASE;
        }
        return (*this);
    }

    BigInt operator + (const int &b)
    {
        s[0] += b;
        for (int i = 1; i < len; ++i)
        {
            s[i] += s[i - 1] / BASE;
            s[i - 1] %= BASE;
        }
        if (s[len - 1] > BASE)
        {
            s[len] = s[len - 1] / BASE;
            s[len - 1] %= BASE;
            len++;
        }
        return (*this);
    }
    
    BigInt operator + (const BigInt &b) const
    {
        BigInt c;
        c.len = max(b.len, len);
        for (int i = 0; i < c.len; ++i)
        {
            c.s[i] += s[i] + b.s[i];
            c.s[i + 1] += c.s[i] / BASE;
            c.s[i] %= BASE;
        }
        while (c.s[c.len])
        {
            c.s[c.len + 1] = c.s[c.len] / BASE;
            c.s[c.len++] %= BASE;
        }
        return c;
    }

    BigInt operator * (int x)
    {
        for (int i = 0; i < len; ++i) s[i] *= x;
        for (int i = 0; i < len; ++i)
        {
            s[i + 1] += s[i] / BASE;
            s[i] %= BASE;
        }
        while (s[len])
        {
            s[len + 1] = s[len] / BASE;
            s[len++] %= BASE;
        }
        return (*this);
    }

    BigInt operator * (const BigInt &b) const
    {
        BigInt c;
        int x, m;
        for (int i = 0; i < b.len; ++i)
        {
            x = 0;
            for (int j = 0; j < len; ++j)
            {
                c.s[i + j] += x + b.s[i] * s[j];
                x = c.s[i + j] / BASE;
                c.s[i + j] %= BASE;
            }
            c.s[i + len] += x;
        }
        c.len = b.len + len;
        while (c.len > 1 && c.s[c.len - 1] == 0) c.len--;
        while (c.s[c.len])
        {
            c.s[c.len + 1] = c.s[c.len] / BASE;
            c.s[c.len] %= BASE;
        }
        return c;
    }

    BigInt operator - (const BigInt &b)
    {
        BigInt c;
        memcpy(c.s, s, sizeof(s));
        c.len = len;
        for (int i = 0; i < b.len; ++i)
        {
            c.s[i] = c.s[i] - b.s[i];
            if (c.s[i] < 0)
            {
                c.s[i] = BASE + c.s[i];
                c.s[i + 1]--;
            }
        }
        while (c.len > 1 && c.s[c.len - 1] == 0) c.len--;
        return c;
    }

    BigInt operator / (const int &b) const
    {
        BigInt c;
        c = 0;
        int x = 0;
        for (int i = len - 1; i >= 0; --i)
        {
            x = x * BASE + s[i];
            if (x >= b)
            {
                c = c * BASE + x / b;
                x %= b;
            }
            else c = c * BASE;
        }
        return c;
    }
    
};

const int MAXN = 55;

BigInt h[MAXN], g[MAXN], f[MAXN];
int n;

BigInt C(int m, int k)
{
    BigInt ans;
    ans = 1;
    for (int i = m - k + 1; i <= m; ++i) ans = ans * i;
    for (int i = 1; i <= k; ++i) ans = ans / i;
    return ans; 
}

int main()
{
    h[0] = 1;
    h[1] = 1;
    f[1] = 1;
    g[1] = 0;
    for (int i = 2; i <= 50; ++i)
    {
        h[i] = 1;
        for (int j = 0; j < i * (i - 1) / 2; ++j) h[i] = h[i] * 2;
        for (int j = 1; j < i; ++j)
            g[i] = g[i] + (C(i - 1, j - 1) * f[j] * h[i - j]);
        f[i] = h[i] - g[i];
    }
    while (scanf("%d", &n) == 1 && n)
    {
        printf("%d", f[n].s[f[n].len - 1]);
        for (int i = f[n].len - 2; i >= 0; --i) printf("%04d", f[n].s[i]);
        printf("\n");
    }
    return 0;
}