快速組合數

遞推公式很簡單：

C(n,k+1) = C(n,k) * (n-k) / (k + 1)

方法很暴力

經測，C（2000，1000）可以求出，C（2000，0）到C（2000，2000）所用時間僅需0.2s

#include <iostream>   
#include <cstdio>   
#include <cstring>   
#include <algorithm>   
#include <limits>   
#include <cstdlib>   
  
using namespace std;  
  
const int MAXD = 100, DIG = 9, BASE = 1000000000;  
  
const unsigned long long BOUND = numeric_limits <unsigned long long> :: max () - (unsigned long long) BASE * BASE;  
  
  
  
class bignum  
{  
private:  
    int digits[MAXD];  
    int D;  
public:  
  
    friend ostream &operator<<(ostream &out,bignum &c);  
  
    inline void trim()  
    {  
        while(D > 1 && digits[D-1] == 0 )  
            D--;  
    }  
  
    inline void dealint(long long x)  
    {  
        memset(digits,0,sizeof(digits));  
        D = 0;  
        do  
        {  
            digits[D++] = x % BASE;  
            x /= BASE;  
        }  
        while(x > 0);  
    }  
  
    inline void dealstr(char *s)  
    {  
        memset(digits,0,sizeof(digits));  
        int len = strlen(s),first = (len + DIG -1)%DIG + 1;  
  
        D = (len+DIG-1)/DIG;  
  
        for(int i = 0; i < first; i++)  
            digits[D-1] = digits[D-1]*10 + s[i] - '0';  
  
        for(int i = first, d = D-2; i < len; i+=DIG,d--)  
            for(int j = i; j < i+DIG; j++)  
                digits[d] = digits[d]*10 + s[j]-'0';  
  
        trim();  
    }  
  
    inline char *print()  
    {  
        trim();  
  
        char *cdigits = new char[DIG * D + 1];  
  
        int pos = 0,d = digits[D-1];  
  
        do  
        {  
            cdigits[pos++] = d % 10 + '0';  
            d/=10;  
        }  
        while(d > 0);  
  
        reverse(cdigits,cdigits+pos);  
  
        for(int i = D - 2; i >= 0; i--,pos += DIG)  
            for(int j = DIG-1,t = digits[i]; j >= 0; j--)  
            {  
                cdigits[pos+j] = t%10 + '0';  
                t /= 10;  
            }  
  
        cdigits[pos] = '\0';  
  
        return cdigits;  
    }  
  
  
    bignum()  
    {  
        dealint(0);  
    }  
  
    bignum(long long x)  
    {  
        dealint(x);  
    }  
  
    bignum(int x)  
    {  
        dealint(x);  
    }  
  
    bignum(char *s)  
    {  
        dealstr(s);  
    }  
  
  
  
    inline bool operator < (const bignum &o) const  
    {  
        if(D != o.D)  
            return D < o.D;  
  
        for(int i = D-1; i>=0; i--)  
            if(digits[i] != o.digits[i])  
                return digits[i] < o.digits[i];  
        return false; //equal   
  
    }  
  
    bool operator >  (const bignum & o)const  
    {  
        return o < *this;  
    }  
    bool operator <= (const bignum & o)const  
    {  
        return !(o < *this);  
    }  
    bool operator >= (const bignum & o)const  
    {  
        return !(*this < o);  
    }  
    bool operator != (const bignum & o)const  
    {  
        return o < *this || *this < o;  
    }  
    bool operator == (const bignum & o)const  
    {  
        return !(o < *this) && !(*this < o);  
    }  
  
  
    bignum &operator++()  
    {  
        *this = *this  + 1;  
        return *this;  
    }  
  
  
    bignum operator ++(int)  
    {  
        bignum old = *this;  
        ++(*this);  
        return old;  
    }  
  
    inline bignum operator << (int p) const  
    {  
        bignum temp;  
        temp.D = D + p;  
  
        for (int i = 0; i < D; i++)  
            temp.digits [i + p] = digits [i];  
  
        for (int i = 0; i < p; i++)  
            temp.digits [i] = 0;  
  
        return temp;  
    }  
  
    inline bignum operator >> (int p) const  
    {  
        bignum temp;  
        temp.D = D - p;  
  
        for (int i = 0; i < D - p; i++)  
            temp.digits [i] = digits [i + p];  
  
        for (int i = D - p; i < D; i++)  
            temp.digits [i] = 0;  
  
        return temp;  
    }  
  
  
    bignum &operator += (const bignum &b)  
    {  
        *this = *this + b;  
        return *this;  
    }  
  
    bignum &operator -= (const bignum &b)  
    {  
        *this = *this - b;  
        return *this;  
    }  
  
    bignum &operator *= (const bignum &b)  
    {  
        *this = *this * b;  
        return *this;  
    }  
  
    bignum &operator /= (const bignum &b)  
    {  
        *this = *this / b;  
        return *this;  
    }  
  
    bignum &operator %= (const bignum &b)  
    {  
        *this = *this % b;  
        return *this;  
    }  
  
    inline bignum operator + (const bignum &o) const  
    {  
        bignum sum = o;  
        int carry = 0;  
  
        for (sum.D = 0; sum.D < D || carry > 0; sum.D++)  
        {  
            sum.digits [sum.D] += (sum.D < D ? digits [sum.D] : 0) + carry;  
  
            if (sum.digits [sum.D] >= BASE)  
            {  
                sum.digits [sum.D] -= BASE;  
                carry = 1;  
            }  
            else  
                carry = 0;  
        }  
  
        sum.D = max (sum.D, o.D);  
        sum.trim ();  
        return sum;  
    }  
    inline bignum operator - (const bignum &o) const  
    {  
        bignum diff = *this;  
  
        for (int i = 0, carry = 0; i < o.D || carry > 0; i++)  
        {  
            diff.digits [i] -= (i < o.D ? o.digits [i] : 0) + carry;  
  
            if (diff.digits [i] < 0)  
            {  
                diff.digits [i] += BASE;  
                carry = 1;  
            }  
            else  
                carry = 0;  
        }  
  
        diff.trim ();  
        return diff;  
    }  
    inline bignum operator * (const bignum &o) const  
    {  
        bignum prod = 0;  
        unsigned long long sum = 0, carry = 0;  
  
        for (prod.D = 0; prod.D < D + o.D - 1 || carry > 0; prod.D++)  
        {  
            sum = carry % BASE;  
            carry /= BASE;  
  
            for (int j = max (prod.D - o.D + 1, 0); j <= min (D - 1, prod.D); j++)  
            {  
                sum += (unsigned long long) digits [j] * o.digits [prod.D - j];  
  
                if (sum >= BOUND)  
                {  
                    carry += sum / BASE;  
                    sum %= BASE;  
                }  
            }  
  
            carry += sum / BASE;  
            prod.digits [prod.D] = sum % BASE;  
        }  
  
        prod.trim ();  
        return prod;  
    }  
    inline bignum range (int a, int b) const  
    {  
        bignum temp = 0;  
        temp.D = b - a;  
  
        for (int i = 0; i < temp.D; i++)  
            temp.digits [i] = digits [i + a];  
  
        return temp;  
    }  
  
  
    inline double double_div (const bignum &o) const  
    {  
        double val = 0, oval = 0;  
        int num = 0, onum = 0;  
  
        for (int i = D - 1; i >= max (D - 3, 0); i--, num++)  
            val = val * BASE + digits [i];  
  
        for (int i = o.D - 1; i >= max (o.D - 3, 0); i--, onum++)  
            oval = oval * BASE + o.digits [i];  
  
        return val / oval * (D - num > o.D - onum ? BASE : 1);  
    }  
  
    inline pair <bignum, bignum> divmod (const bignum &o) const  
    {  
        bignum quot = 0, rem = *this, temp;  
  
        for (int i = D - o.D; i >= 0; i--)  
        {  
            temp = rem.range (i, rem.D);  
            int div = (int) temp.double_div (o);  
            bignum mult = o * div;  
  
            while (div > 0 && temp < mult)  
            {  
                mult = mult - o;  
                div--;  
            }  
  
            while (div + 1 < BASE && !(temp < mult + o))  
            {  
                mult = mult + o;  
                div++;  
            }  
  
            rem = rem - (o * div << i);  
  
            if (div > 0)  
            {  
                quot.digits [i] = div;  
                quot.D = max (quot.D, i + 1);  
            }  
        }  
  
        quot.trim ();  
        rem.trim ();  
        return make_pair (quot, rem);  
    }  
  
    inline bignum operator / (const bignum &o) const  
    {  
        return divmod (o).first;  
    }  
  
    inline bignum operator % (const bignum &o) const  
    {  
        return divmod (o).second;  
    }  
  
  
    inline bignum power (int exp) const  
    {  
        bignum p = 1, temp = *this;  
  
        while (exp > 0)  
        {  
            if (exp & 1) p = p * temp;  
            if (exp > 1) temp = temp * temp;  
            exp >>= 1;  
        }  
  
        return p;  
    }  
  
    inline bignum factorial() const  
    {  
        bignum ans = 1, num = *this;  
  
        if (num == 0 || num == 1)  
            return ans;  
        while (!(num < 0 || num == 0))  
        {  
            ans = ans * num;  
            num = num - 1;  
        }  
        return ans;  
    }  
};  
  
ostream &operator<<(ostream &out, bignum &c)  
{  
    out<<c.print();  
    return out;  
}  
  
istream &operator >> (istream &in,bignum &c)  
{  
    char s[10000];  
    in>>s;  
    c = s;  
    return in;  
}  
bignum gcd(bignum a,bignum b)  
{  
    return b==0?a:gcd(b,a%b);  
}  
  
  
  
int main()  
{  
  
    bignum c[3020];  
    freopen("D:\\a.txt","w",stdout);  
    int m, n;  
    n = 2000, m = 1;  
    {  
        c[0] = 1;  
        for (int k = 0; k <= 2000; k++)  
        {  
            c[k + 1] = c[k] * (n - k) / (k + 1);  
        }  
        for (int i = 0; i <= 2000; i++)  
        {  
            cout << "C" << "(" << n << "," << i << ") is " <<c[i] << endl;  
        }  
    }  
}  

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <limits>
#include <cstdlib>

using namespace std;

const int MAXD = 100, DIG = 9, BASE = 1000000000;

const unsigned long long BOUND = numeric_limits <unsigned long long> :: max () - (unsigned long long) BASE * BASE;



class bignum
{
private:
    int digits[MAXD];
    int D;
public:

    friend ostream &operator<<(ostream &out,bignum &c);

    inline void trim()
    {
        while(D > 1 && digits[D-1] == 0 )
            D--;
    }

    inline void dealint(long long x)
    {
        memset(digits,0,sizeof(digits));
        D = 0;
        do
        {
            digits[D++] = x % BASE;
            x /= BASE;
        }
        while(x > 0);
    }

    inline void dealstr(char *s)
    {
        memset(digits,0,sizeof(digits));
        int len = strlen(s),first = (len + DIG -1)%DIG + 1;

        D = (len+DIG-1)/DIG;

        for(int i = 0; i < first; i++)
            digits[D-1] = digits[D-1]*10 + s[i] - '0';

        for(int i = first, d = D-2; i < len; i+=DIG,d--)
            for(int j = i; j < i+DIG; j++)
                digits[d] = digits[d]*10 + s[j]-'0';

        trim();
    }

    inline char *print()
    {
        trim();

        char *cdigits = new char[DIG * D + 1];

        int pos = 0,d = digits[D-1];

        do
        {
            cdigits[pos++] = d % 10 + '0';
            d/=10;
        }
        while(d > 0);

        reverse(cdigits,cdigits+pos);

        for(int i = D - 2; i >= 0; i--,pos += DIG)
            for(int j = DIG-1,t = digits[i]; j >= 0; j--)
            {
                cdigits[pos+j] = t%10 + '0';
                t /= 10;
            }

        cdigits[pos] = '\0';

        return cdigits;
    }


    bignum()
    {
        dealint(0);
    }

    bignum(long long x)
    {
        dealint(x);
    }

    bignum(int x)
    {
        dealint(x);
    }

    bignum(char *s)
    {
        dealstr(s);
    }



    inline bool operator < (const bignum &o) const
    {
        if(D != o.D)
            return D < o.D;

        for(int i = D-1; i>=0; i--)
            if(digits[i] != o.digits[i])
                return digits[i] < o.digits[i];
        return false; //equal

    }

    bool operator >  (const bignum & o)const
    {
        return o < *this;
    }
    bool operator <= (const bignum & o)const
    {
        return !(o < *this);
    }
    bool operator >= (const bignum & o)const
    {
        return !(*this < o);
    }
    bool operator != (const bignum & o)const
    {
        return o < *this || *this < o;
    }
    bool operator == (const bignum & o)const
    {
        return !(o < *this) && !(*this < o);
    }


    bignum &operator++()
    {
        *this = *this  + 1;
        return *this;
    }


    bignum operator ++(int)
    {
        bignum old = *this;
        ++(*this);
        return old;
    }

    inline bignum operator << (int p) const
    {
        bignum temp;
        temp.D = D + p;

        for (int i = 0; i < D; i++)
            temp.digits [i + p] = digits [i];

        for (int i = 0; i < p; i++)
            temp.digits [i] = 0;

        return temp;
    }

    inline bignum operator >> (int p) const
    {
        bignum temp;
        temp.D = D - p;

        for (int i = 0; i < D - p; i++)
            temp.digits [i] = digits [i + p];

        for (int i = D - p; i < D; i++)
            temp.digits [i] = 0;

        return temp;
    }


    bignum &operator += (const bignum &b)
    {
        *this = *this + b;
        return *this;
    }

    bignum &operator -= (const bignum &b)
    {
        *this = *this - b;
        return *this;
    }

    bignum &operator *= (const bignum &b)
    {
        *this = *this * b;
        return *this;
    }

    bignum &operator /= (const bignum &b)
    {
        *this = *this / b;
        return *this;
    }

    bignum &operator %= (const bignum &b)
    {
        *this = *this % b;
        return *this;
    }

    inline bignum operator + (const bignum &o) const
    {
        bignum sum = o;
        int carry = 0;

        for (sum.D = 0; sum.D < D || carry > 0; sum.D++)
        {
            sum.digits [sum.D] += (sum.D < D ? digits [sum.D] : 0) + carry;

            if (sum.digits [sum.D] >= BASE)
            {
                sum.digits [sum.D] -= BASE;
                carry = 1;
            }
            else
                carry = 0;
        }

        sum.D = max (sum.D, o.D);
        sum.trim ();
        return sum;
    }
    inline bignum operator - (const bignum &o) const
    {
        bignum diff = *this;

        for (int i = 0, carry = 0; i < o.D || carry > 0; i++)
        {
            diff.digits [i] -= (i < o.D ? o.digits [i] : 0) + carry;

            if (diff.digits [i] < 0)
            {
                diff.digits [i] += BASE;
                carry = 1;
            }
            else
                carry = 0;
        }

        diff.trim ();
        return diff;
    }
    inline bignum operator * (const bignum &o) const
    {
        bignum prod = 0;
        unsigned long long sum = 0, carry = 0;

        for (prod.D = 0; prod.D < D + o.D - 1 || carry > 0; prod.D++)
        {
            sum = carry % BASE;
            carry /= BASE;

            for (int j = max (prod.D - o.D + 1, 0); j <= min (D - 1, prod.D); j++)
            {
                sum += (unsigned long long) digits [j] * o.digits [prod.D - j];

                if (sum >= BOUND)
                {
                    carry += sum / BASE;
                    sum %= BASE;
                }
            }

            carry += sum / BASE;
            prod.digits [prod.D] = sum % BASE;
        }

        prod.trim ();
        return prod;
    }
    inline bignum range (int a, int b) const
    {
        bignum temp = 0;
        temp.D = b - a;

        for (int i = 0; i < temp.D; i++)
            temp.digits [i] = digits [i + a];

        return temp;
    }


    inline double double_div (const bignum &o) const
    {
        double val = 0, oval = 0;
        int num = 0, onum = 0;

        for (int i = D - 1; i >= max (D - 3, 0); i--, num++)
            val = val * BASE + digits [i];

        for (int i = o.D - 1; i >= max (o.D - 3, 0); i--, onum++)
            oval = oval * BASE + o.digits [i];

        return val / oval * (D - num > o.D - onum ? BASE : 1);
    }

    inline pair <bignum, bignum> divmod (const bignum &o) const
    {
        bignum quot = 0, rem = *this, temp;

        for (int i = D - o.D; i >= 0; i--)
        {
            temp = rem.range (i, rem.D);
            int div = (int) temp.double_div (o);
            bignum mult = o * div;

            while (div > 0 && temp < mult)
            {
                mult = mult - o;
                div--;
            }

            while (div + 1 < BASE && !(temp < mult + o))
            {
                mult = mult + o;
                div++;
            }

            rem = rem - (o * div << i);

            if (div > 0)
            {
                quot.digits [i] = div;
                quot.D = max (quot.D, i + 1);
            }
        }

        quot.trim ();
        rem.trim ();
        return make_pair (quot, rem);
    }

    inline bignum operator / (const bignum &o) const
    {
        return divmod (o).first;
    }

    inline bignum operator % (const bignum &o) const
    {
        return divmod (o).second;
    }


    inline bignum power (int exp) const
    {
        bignum p = 1, temp = *this;

        while (exp > 0)
        {
            if (exp & 1) p = p * temp;
            if (exp > 1) temp = temp * temp;
            exp >>= 1;
        }

        return p;
    }

    inline bignum factorial() const
    {
        bignum ans = 1, num = *this;

        if (num == 0 || num == 1)
            return ans;
        while (!(num < 0 || num == 0))
        {
            ans = ans * num;
            num = num - 1;
        }
        return ans;
    }
};

ostream &operator<<(ostream &out, bignum &c)
{
    out<<c.print();
    return out;
}

istream &operator >> (istream &in,bignum &c)
{
    char s[10000];
    in>>s;
    c = s;
    return in;
}
bignum gcd(bignum a,bignum b)
{
    return b==0?a:gcd(b,a%b);
}



int main()
{

	bignum c[3020];
    freopen("D:\\a.txt","w",stdout);
	int m, n;
	n = 2000, m = 1;
	{
		c[0] = 1;
		for (int k = 0; k <= 2000; k++)
		{
			c[k + 1] = c[k] * (n - k) / (k + 1);
		}
		for (int i = 0; i <= 2000; i++)
		{
			cout << "C" << "(" << n << "," << i << ") is " <<c[i] << endl;
		}
	}
}