ACM UVA 10303 (How Many Trees?)

题目： 

思路： (找规律、big integer)

• 公式推导请参见下图：

• 以前用C++写的那个非常初级的BigInt类<http://blog.chinaunix.net/uid-20128696-id-1734249.html>速度非常慢。重新写了一个BigInteger类(还不太完善)，以后就可以用这个类工作了。主要参考了Java的BigInteger的源代码。

代码：

//
// Author: xfye
// Status: Accept
//

#include <sstream>
#include <iostream>

#include <vector>
#include <cstring>
#include <cstdlib>

using namespace std;

typedef unsigned int uint;
typedef unsigned long long ullong;
typedef long long llong;


class BigInteger
{
public:
    BigInteger();
    BigInteger(int val);
    BigInteger(unsigned int val);
    BigInteger(ullong val);
    BigInteger(const BigInteger& val);
    BigInteger add(const BigInteger& bint, int val) const;
    BigInteger add(const BigInteger& bint, uint val) const;
    BigInteger add(const BigInteger& x, const BigInteger& y) const;
    std::string toStdString() const;
    bool isNegative() const;

    BigInteger& operator +=(int val);
    BigInteger& operator +=(uint val);
    BigInteger& operator +=(const BigInteger& val);
    BigInteger& operator *=(int val);
    BigInteger& operator *=(uint val);
    BigInteger& operator *=(BigInteger& val);
    BigInteger& operator =(int val);
    BigInteger& operator =(unsigned int val);
    BigInteger& operator =(ullong val);
    BigInteger& operator =(const BigInteger& val);
    bool operator !=(int val);
    bool operator ==(int val);

    // for debug only.
    void debug();

private:
    /// Compare the sign with val
    bool compareSign(int val) const;

    /// Compare the sign with val
    bool compareSign(BigInteger& val) const;

    int wordsNeeded(const uint words[], int len) const;
    void canonicalize();

    void doCarry(unsigned int val);

    void assign(int val);
    void assign(uint val);
    void assign(ullong val);
    void assign(const BigInteger& val);

    void alloc(int newSize);

    BigInteger times(const BigInteger& bint, int val) const;
    BigInteger times(const BigInteger& bint, uint val) const;
    BigInteger times(const BigInteger& x, const BigInteger& y) const;

    void expandWords();
    void expandWords(int newSize);
    void format(int radix, std::string& buffer) const;
    ullong longValue() const;

    ullong udiv_qrnnd(ullong N, uint D) const;
    uint divmod_1 (uint quotient[], uint dividend[], int len, uint divisor) const;
    uint mul_1(uint* dest, const uint* x, int len, uint y) const;
    void mul(uint dest[],
             const uint x[], int xlen,
             const uint y[], int ylen) const;
    uint MPN_add_n(uint dest[], const uint x[], const uint y[], int len) const;

    //
    /// All integers are stored in 2's-complement form.
    /// If words == null, the ival is the value of this BigInteger.
    /// Otherwise, the first ival elements of words make the value
    /// of this BigInteger, stored in little-endian order, 2's-complement form.
    ///
    uint *m_words;
    uint m_ival;

    /// The size of words
    int m_sizeOfWords;

    ///
    int m_sign;
};

BigInteger::BigInteger()
    : m_words(NULL),
      m_ival(0),
      m_sizeOfWords(0),
      m_sign(0)
{
}

BigInteger::BigInteger(int val)
    : m_words(NULL),
      m_sizeOfWords(0)
{
    assign(val);
}

BigInteger::BigInteger(unsigned int val)
    : m_words(NULL),
      m_sizeOfWords(0)
{
    assign(val);
}

BigInteger::BigInteger(ullong val)
{
    assign(val);
}

BigInteger::BigInteger(const BigInteger& val)
    : m_words(NULL)
{
    assign(val);
}

void BigInteger::assign(uint val)
{
    if (m_words != NULL) {
        delete[] m_words;
        m_words = NULL;
        m_sizeOfWords = 0;
    }
    m_ival = val;
    if (val == 0) {
        m_sign = 0;
    } else {
        m_sign = 1;
    }
}

void BigInteger::assign(int val)
{
    if (m_words != NULL) {
        delete[] m_words;
        m_words = NULL;
        m_sizeOfWords = 0;
    }
    if (val == 0) {
        m_sign = 0;
        m_ival = 0;
    } else if (val < 0) {
        m_ival = 0 - val;
        m_sign = -1;
    } else { // val > 0
        m_ival = val;
        m_sign = 1;
    }
}

void BigInteger::assign(ullong val)
{
    uint v = (uint) val;
    if ((ullong) v == val) {
        assign(v);
        return;
    }
    if (m_words == NULL) {
        expandWords();
    }
    m_words[0] = v;
    m_words[1] = val >> 32;
    m_ival = 2;
    m_sign = 1;
}

void BigInteger::assign(const BigInteger& val)
{
    if (m_words != NULL) {
        delete[] m_words;
        m_words = NULL;
    }
    if (val.m_words != NULL) {
        m_sizeOfWords = val.m_sizeOfWords;
        m_words = new uint[val.m_sizeOfWords];
        memcpy(m_words, val.m_words, m_sizeOfWords * sizeof(uint));
    }
    m_ival = val.m_ival;
    m_sign = val.m_sign;
}

BigInteger BigInteger::add(const BigInteger& x, const BigInteger& y) const
{
    BigInteger result;

    if (x.m_words == NULL && y.m_words == NULL) {
        result = ((ullong) y.m_ival + (ullong) x.m_ival);
        return result;
    }

    if (x.m_words == NULL) {
        result = add(y, x.m_ival);
        return result;
    }
    if (y.m_words == NULL) {
        result = add(x, y.m_ival);
        return result;
    }

    BigInteger xx = x;
    BigInteger yy = y;
    // Both are big
    if (y.m_ival > x.m_ival)
    { // Swap so x is longer then y.
        xx = y;
        yy = x;
    }
    result.expandWords(xx.m_ival + 1);
    int i = yy.m_ival;
    ullong carry = MPN_add_n(result.m_words, xx.m_words, yy.m_words, i);
    ullong y_ext = yy.m_words[i - 1] < 0 ? 0xffffffffL : 0;
    for (; i < xx.m_ival;  i++) {
        carry += ((ullong) xx.m_words[i] & 0xffffffffL) + y_ext;
        result.m_words[i] = (uint) carry;
        carry >>= 32;
    }
    if (xx.m_words[i - 1] < 0) {
        y_ext--;
    }
    result.m_words[i] = (uint) (carry + y_ext);
    /// result.m_ival = i+1;
    result.m_ival = i+1;
    result.canonicalize();
    return result;
}

BigInteger BigInteger::add(const BigInteger& bint, uint val) const
{
    BigInteger result = bint;

    if (result.m_words == NULL) {
        long long sum = (long long) val + (long long) result.m_ival;
        uint v = (uint) sum;
        if ((long long) v != sum) {
            result.m_words = new uint[32];
            result.m_sizeOfWords = 32;
            result.m_ival = 2;
            result.m_words[0] = v;
            result.m_words[1] = sum >> 32;
        } else {
            result.m_ival = v;
        }
    } else {
        long long carry = val;
        for (int i = 0; i < result.m_ival; i++) {
            carry += result.m_words[i];
            result.m_words[i] = (uint) carry;
            carry >>= 32;
        }
        if (carry > 0) {
            result.doCarry(carry);
        }
    }

    return result;
}

BigInteger BigInteger::add(const BigInteger& bint, int val) const
{
    BigInteger result = bint;

    if (result.compareSign(val)) {
        val = val & 0x7fffffff;  // abs();
        if (result.m_words == NULL) {
            long long sum = (long long) val + (long long) result.m_ival;
            uint v = (uint) sum;
            if ((long long) v != sum) {
                result.m_words = new uint[32];
                result.m_sizeOfWords = 32;
                result.m_ival = 2;
                result.m_words[0] = v;
                result.m_words[1] = sum >> 32;
            } else {
                result.m_ival = v;
            }
        } else {
            long long carry = val;
            for (int i = 0; i < result.m_ival; i++) {
                carry += result.m_words[i];
                result.m_words[i] = (uint) carry;
                carry >>= 32;
            }
            if (carry > 0) {
                result.doCarry(carry);
            }
        }
    }
    return result;
}

/** Add x[0:len-1] and y[0:len-1] and write the len least
 * significant words of the result to dest[0:len-1].
 * All words are treated as unsigned.
 * @return the carry, either 0 or 1
 * This function is basically the same as gmp's mpn_add_n.
 */
uint BigInteger::MPN_add_n(uint dest[], const uint x[], const uint y[], int len) const
{
    ullong carry = 0;
    for (int i = 0; i < len;  i++)
    {
        carry += ((ullong) x[i] & 0xffffffffL)
            + ((ullong) y[i] & 0xffffffffL);
        dest[i] = (uint) carry;
        carry >>= 32;
    }
    return (uint) carry;
}

bool BigInteger::compareSign(int val) const
{
    if ((m_sign == 0 && val == 0)
        || (m_sign > 0 && val > 0)
        || (m_sign < 0 && val < 0)) {
        return true;
    }

    return false;
}

bool BigInteger::compareSign(BigInteger& val) const
{
    if (m_sign != val.m_sign) {
        return false;
    }

    return true;
}


void BigInteger::doCarry(unsigned int val)
{
    expandWords();
    m_words[m_ival++] = val;
}

void BigInteger::expandWords()
{
    uint* newWords = new uint[m_sizeOfWords+32];
    memset(newWords, 0, m_sizeOfWords+32 * sizeof(uint));
    memcpy(newWords, m_words, m_sizeOfWords * sizeof(uint));
    delete[] m_words;
    m_words = newWords;
    m_sizeOfWords += 32;
}

void BigInteger::expandWords(int newSize)
{
    if (m_words != NULL && m_sizeOfWords >= newSize) {
        return;
    }

    uint* newWords = new uint[newSize];
    memset(newWords, 0, newSize * sizeof(uint));

    if (m_words == NULL) {
        memcpy(newWords, m_words, m_sizeOfWords * sizeof(uint));
    } else {
        delete[] m_words;
    }
    m_words = newWords;
    m_sizeOfWords = newSize;
}

std::string BigInteger::toStdString() const
{
    std::string str;
    format(10, str);
#if 0
    std::stringstream ss;
    std::string str;
    if (m_words == NULL) {
        if (0 == m_ival) {
            str = "0";
            return str;
        } else {
            if (m_sign < 0) {
                str += "-";
            }
            ss << m_ival;
            std::string s;
            ss >> s;
            str += s;
        }
    } else {    // m_words != NULL
        if (m_sign < 0) {
            str += "-";
        }
        for (int i = m_ival-1; i >= 0; i--) {
            ss << m_words[i];
        }
        std::string s;
        ss >> s;
        str += s;
    }
#endif

    return str;
}

/* Divide (unsigned long) N by (unsigned int) D.
* Returns (remainder << 32)+(unsigned int)(quotient).
* Assumes (unsigned int)(N>>32) < (unsigned int)D.
* Code transcribed from gmp-2.0's mpn_udiv_w_sdiv function.
*
* It's OK
*/
ullong BigInteger::udiv_qrnnd(ullong N, uint D) const
{
    ullong q, r;
    ullong a1 = N >> 32;
    ullong a0 = N & 0xffffffffL;
    if (D >= 0)
    {
        if (a1 < ((D - a1 - (a0 >> 31)) & 0xffffffffL))
        {
            /* dividend, divisor, and quotient are nonnegative */
            q = N / D;
            r = N % D;
        }
        else
        {
            /* Compute c1*2^32 + c0 = a1*2^32 + a0 - 2^31*d */
            ullong c = N - ((ullong) D << 31);
            /* Divide (c1*2^32 + c0) by d */
            q = c / D;
            r = c % D;
            /* Add 2^31 to quotient */
            q += 1 << 31;
        }
    }
    else
    {
        ullong b1 = D >> 1;      /* d/2, between 2^30 and 2^31 - 1 */
        //long c1 = (a1 >> 1); /* A/2 */
        //int c0 = (a1 << 31) + (a0 >> 1);
        ullong c = N >> 1;
        if (a1 < b1 || (a1 >> 1) < b1)
        {
            if (a1 < b1)
            {
                q = c / b1;
                r = c % b1;
            }
            else /* c1 < b1, so 2^31 <= (A/2)/b1 < 2^32 */
            {
                c = ~(c - (b1 << 32));
                q = c / b1;  /* (A/2) / (d/2) */
                r = c % b1;
                q = (~q) & 0xffffffffL;    /* (A/2)/b1 */
                r = (b1 - 1) - r; /* r < b1 => new r >= 0 */
            }
            r = 2 * r + (a0 & 1);
            if ((D & 1) != 0)
            {
                if (r >= q) {
                    r = r - q;
                } else if (q - r <= ((ullong) D & 0xffffffffL)) {
                    r = r - q + D;
                    q -= 1;
                } else {
                    r = r - q + D + D;
                    q -= 2;
                }
            }
        }
        else                            /* Implies c1 = b1 */
        {                             /* Hence a1 = d - 1 = 2*b1 - 1 */
            if (a0 >= ((ullong)(-D) & 0xffffffffL))
            {
                q = -1;
                r = a0 + D;
            }
            else
            {
                q = -2;
                r = a0 + D + D;
            }
        }
    }

    return (r << 32) | (q & 0xFFFFFFFFl);
}


/** Divide divident[0:len-1] by (unsigned int)divisor.
* Write result into quotient[0:len-1.
* Return the one-word (unsigned) remainder.
* OK for quotient==dividend.
*/
uint BigInteger::divmod_1(uint quotient[], uint dividend[],
                          int len, uint divisor) const
{
    int i = len - 1;
    ullong r = dividend[i];
    if ((r & 0xffffffffL) >= ((ullong)divisor & 0xffffffffL))
        r = 0;
    else
    {
        quotient[i--] = 0;
        r <<= 32;
    }

    for (;  i >= 0;  i--)
    {
        uint n0 = dividend[i];
        r = (r & 0xffffffff00000000) | (n0 & 0xffffffffL);
        r = udiv_qrnnd (r, divisor);
        quotient[i] = (uint) r;
    }
    return (uint)(r >> 32);
}


//
// Only support radix 10
//
void BigInteger::format(int radix, std::string& buffer) const
{
    if (m_words == NULL) {
        std::stringstream ss;
        ss << m_ival;
        buffer += ss.str();
    } else if (m_ival <= 2) {
        std::stringstream ss;
        ss << longValue();
        buffer += ss.str();
    } else {
        bool neg = isNegative();
        uint *work;
        if (neg || radix != 16) {
            // work = new uint(m_ival);
            // getAbsolute(work);   // commented by xfye
            work = m_words;
        }
        else {
            work = m_words;
        }
        uint len = m_ival;

        if (radix == 16) {
#if 0
            if (neg)
                buffer.append('-');
            int buf_start = buffer.length();
            for (int i = len;  --i >= 0; )
            {
                int word = work[i];
                for (int j = 8;  --j >= 0; )
                {
                    int hex_digit = (word >> (4 * j)) & 0xF;
                    // Suppress leading zeros:
                    if (hex_digit > 0 || buffer.length() > buf_start)
                        buffer.append(Character.forDigit(hex_digit, 16));
                }
            }
#endif
        } else {
            for (;;) {
                int digit = divmod_1(work, work, len, radix);
                buffer.push_back(digit+'0');
                while (len > 0 && work[len-1] == 0) {
                    len--;
                }
                if (len == 0) {
                    break;
                }
            }
            if (neg) {
                buffer.push_back('-');
            }

#if 1
            /* Reverse buffer. */
            int i = 0;
            int j = buffer.length() - 1;
            while (i < j)
            {
                char tmp = buffer[i];
                buffer[i] = buffer[j];
                buffer[j] = tmp;
                i++;  j--;
            }
#endif
        }
    }
}

bool BigInteger::isNegative() const
{
    if (m_sign < 0) {
        return true;
    }
    return false;
}

ullong BigInteger::longValue() const
{
    if (NULL == m_words) {
        return (ullong) m_ival;
    }
    if (m_ival == 1) {
        return (ullong) m_words[0];
    }
    return ((ullong) m_words[1] << 32) + ((ullong) m_words[0] & 0xffffffff);
}

void BigInteger::debug()
{
    uint work[] = { 0x63, 0x01, 0x05 };
    uint r = divmod_1(work, work, 3, 10);
    std::cout << "[debug] r=" << r << std::endl;

    //ullong a = 0x100000000;
    //ullong b =  udiv_qrnnd(a, 10);
    //std::cout << "debug:: " << b << std::endl;
}

BigInteger BigInteger::times(const BigInteger& bint, uint val) const
{
    BigInteger result;

    if (val == 0) {
        result.assign(0);
        return result;
    }
    if (val == 1) {
        result = bint;
        return result;
    }

    if (bint.m_words == NULL) {
        result.assign((ullong) m_ival * (ullong) val);
        return result;
    }

    result = bint;
    result.expandWords();
    result.m_words[result.m_ival] = mul_1(result.m_words, result.m_words, result.m_ival, val);
    result.m_ival++;
    result.canonicalize();
    return result;
}

BigInteger BigInteger::times(const BigInteger& bint, int y) const
{
    BigInteger result;

#if 1
    if (y == 0) {
        result.assign(0);
        return result;
    }
    if (y == 1) {
        result = bint;
        return result;
    }

    if (bint.m_words == NULL) {
        result.assign((ullong) m_ival * (ullong) y);
        if (bint.compareSign(y)) {
            result.m_sign = 1;
        } else {
            result.m_sign = -1;
        }
        return result;
    }

    result = bint;
    result.expandWords();
    result.m_words[result.m_ival] = mul_1(result.m_words, result.m_words, result.m_ival, y);
    result.m_ival++;
    if (bint.compareSign(y)) {
        result.m_sign = 1;
    } else {
        result.m_sign = -1;
    }

    result.canonicalize();
    return result;

#endif
}

/** Multiply x[0:len-1] by y, and write the len least
 * significant words of the product to dest[0:len-1].
 * Return the most significant word of the product.
 * All values are treated as if they were unsigned
 * (i.e. masked with 0xffffffffL).
 * OK if dest==x (not sure if this is guaranteed for mpn_mul_1).
 * This function is basically the same as gmp's mpn_mul_1.
 */
uint BigInteger::mul_1(uint* dest, const uint* x, int len, uint y) const
{
    ullong yword = (ullong) y & 0xffffffffL;
    ullong carry = 0;
    for (int j = 0;  j < len; j++)
    {
        carry += ((ullong) x[j] & 0xffffffffL) * yword;
        dest[j] = (uint) carry;
        carry >>= 32;
    }
    return (uint) carry;
}

/**
 * Multiply x[0:xlen-1] and y[0:ylen-1], and
 * write the result to dest[0:xlen+ylen-1].
 * The destination has to have space for xlen+ylen words,
 * even if the result might be one limb smaller.
 * This function requires that xlen >= ylen.
 * The destination must be distinct from either input operands.
 * All operands are unsigned.
 * This function is basically the same gmp's mpn_mul. */

void BigInteger::mul (uint dest[],
                      const uint x[], int xlen,
                      const uint y[], int ylen) const
{
    dest[xlen] = mul_1 (dest, x, xlen, y[0]);

    for (int i = 1;  i < ylen; i++)
    {
        ullong yword = (ullong) y[i] & 0xffffffffL;
        ullong carry = 0;
        for (int j = 0;  j < xlen; j++)
        {
            carry += ((ullong) x[j] & 0xffffffffL) * yword
                + ((ullong) dest[i+j] & 0xffffffffL);
            dest[i+j] = (uint) carry;
            carry >>= 32;
        }
        dest[i+xlen] = (uint) carry;
    }
}

BigInteger& BigInteger::operator *=(int val)
{
    *this = times(*this, val);
    return *this;
}

BigInteger& BigInteger::operator *=(uint val)
{
    *this = times(*this, val);
    return *this;
}

BigInteger& BigInteger::operator *=(BigInteger& val)
{
    *this = times(*this, val);
    return *this;
}

BigInteger& BigInteger::operator =(unsigned int val)
{
    assign(val);
    return *this;
}

BigInteger& BigInteger::operator =(int val)
{
    assign(val);
    return *this;
}

BigInteger& BigInteger::operator =(ullong val)
{
    assign(val);
    return *this;
}

BigInteger& BigInteger::operator =(const BigInteger& val)
{
    assign(val);
    return *this;
}

bool BigInteger::operator !=(int val)
{
    if (!compareSign(val)) {
        return true;
    }
    if (m_words != NULL) {
        return true;
    }
    if (m_ival != val) {
        return true;
    }

    return true;
}

bool BigInteger::operator ==(int val)
{
    if (!compareSign(val)) {
        return false;
    }
    if (m_words != NULL) {
        return false;
    }
    if (m_ival != val) {
        return false;
    }

    return true;
}

BigInteger BigInteger::times(const BigInteger& x, const BigInteger& y) const
{
#if 1
    if (y.m_words == NULL) {
        return times(x, y.m_ival);
    }

    if (x.m_words == NULL) {
        return times(y, x.m_ival);
    }

    uint *xwords = x.m_words;
    uint *ywords = y.m_words;
    int xlen = x.m_ival;
    int ylen = y.m_ival;
    if (xlen < ylen) {
        int tlen = xlen;  xlen = ylen;  ylen = tlen;
        uint* twords = xwords; xwords = ywords; ywords = twords;
    }
    BigInteger result;
    result.expandWords(xlen + ylen);
    mul(result.m_words, xwords, xlen, ywords, ylen);
    result.m_ival = xlen+ylen;
    return result;
#endif
}

BigInteger& BigInteger::operator +=(int val)
{
    *this = add(*this, val);
    return *this;
}

BigInteger& BigInteger::operator +=(uint val)
{
    *this = add(*this, val);
    return *this;
}

BigInteger& BigInteger::operator +=(const BigInteger& val)
{
    BigInteger bint = add(*this, val);
    *this = bint;
    return *this;
}

void BigInteger::canonicalize()
{
    if (m_words != NULL
        && (m_ival = wordsNeeded(m_words, m_ival)) <= 1) {
        if (m_ival == 1) {
            m_ival = m_words[0];
        }
        delete[] m_words;
        m_words = NULL;
    }
#if 0
    if (words == null && ival >= minFixNum && ival <= maxFixNum)
        return smallFixNums[ival - minFixNum];
#endif
}

/** Calculate how many words are significant in words[0:len-1].
 * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
 * when words is viewed as a 2's complement integer.
 */
int BigInteger::wordsNeeded(const uint words[], int len) const
{
    int i = len;
    if (i > 0) {
        int word = words[--i];
        if (word == -1)
        {
            while (i > 0 && (word = words[i - 1]) < 0)
            {
                i--;
                if (word != -1) break;
            }
        }
        else
        {
            while (word == 0 && i > 0 && (word = words[i - 1]) >= 0)  i--;
        }
    }
    return i + 1;
}

BigInteger g_cache[1001];

BigInteger& calcTreeNum(int n)
{
    if (g_cache[n] != 0) {
        // cout << "1:" << g_cache[n] << endl;
        return g_cache[n];
    }

    if (n == 1) {
        g_cache[1] = 1;
        //cout << "2:" << g_cache[n] << endl;
        return g_cache[1];
    }
    if (n == 2) {
        g_cache[2] = 2;
        return g_cache[2];
    }
    for (int i = n-1; i >= n/2; i--) {
        if (i == (n-1)/2) {
            if (g_cache[i] == 0) {
                calcTreeNum(i);
            }
            BigInteger& bint = g_cache[i];
            BigInteger v = bint;
            v *= bint;
            g_cache[n] += v;
        } else {
            if (g_cache[i] == 0) {
                calcTreeNum(i);
            }
            BigInteger b1 = g_cache[i];
            if (n - i > 2) {
                if (g_cache[n-i-1] == 0) {
                    calcTreeNum(n-i-1);
                }
                BigInteger& b2 = g_cache[n-i-1];
                BigInteger v = b1;
                v *= b2;
                v *= 2;
                g_cache[n] += v;
            } else {
                b1 *= 2;
                g_cache[n] += b1;
            }
        }
    }

    //cout << "3:" << g_cache[n] << endl;
    return g_cache[n];
}

int main()
{
    int n = 0;

    g_cache[0] = 1;
    g_cache[1] = 1;

    BigInteger bint;

    for (int j = 2; j < 1001; j++) {
        for (int i = 1; i <= j; i++) {
            bint = g_cache[j-i];
            bint *= g_cache[i-1];
            g_cache[j] += bint;
        }
    }

    while (cin >> n) {
        cout << g_cache[n].toStdString() << endl;
    }

    return 0;
}