HDU1261 大数

字串数
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3913 Accepted Submission(s): 950

Problem Description
一个A和两个B一共可以组成三种字符串:”ABB”,”BAB”,”BBA”.
给定若干字母和它们相应的个数,计算一共可以组成多少个不同的字符串.

Input
每组测试数据分两行,第一行为n(1<=n<=26),表示不同字母的个数,第二行为n个数A1,A2,…,An(1<=Ai<=12),表示每种字母的个数.测试数据以n=0为结束.

Output
对于每一组测试数据,输出一个m,表示一共有多少种字符串.

Sample Input
2
1 2
3
2 2 2
0

Sample Output
3
90

题意：
略
题解：
求总个数为多少，可以知道结果为(a1+a2+…..an)!/(a1!a2!*a3….an!),这里直接算肯定会超过数据上限，所以必须用高精度的大数。但是直接用高精度太慢又会超时。所以我们可以先预处理一下。设sum = a1+a2+…an。那么sum！=1*2*3…sum。我们先用一个数组a储存1到sum，然后对ai！= 1*2*3*…ai其中的每一个数求和数组a里每一个数的最大公约数，然后约去，将每个ai！约分到1，最终把得到的数组a里的每个数用大数乘起来就可以了。g++下耗时46ms

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#define f(i,a,b) for(i = a;i<=b;i++)
#define fi(i,b) for(i = a;i>=b;i--)

using namespace std;

#define LEN 500
#define MOD 10000

//定义了+ - * / % = == != >> << < > <= >= += -= *= /= %= print length pow等操作
struct INT
{
    int num[LEN],len;
    bool sign;
    inline INT(long long x = 0)
    {
        *this = x;
    }
    inline INT(const string &str)
    {
        *this = str;
    }
    inline INT(const int a[],int b,bool c)
    {
        memcpy(num,sizeof num);
        len = b; sign = c;
    }
    inline INT &operator =(const string &str)
    {
        int start = 0;
        len = 0; sign = false;
        memset(num,0,sizeof num);
        if (str[0] == '-') sign = true,start = 1;
        while (str[start] == '0') start++;
        for (int i = str.length() - 1; i >= start; i -= 4,len++)
            for (int j = max(start,i - 3); j <= i; j++)
                num[len] = (num[len] << 3) + (num[len] << 1) + str[j] - '0';
        if (!len) sign = false;
        if (len) len--;
        return *this;
    }
    inline INT &operator =(long long x)
    {
        len = 0; sign = false;
        memset(num,sizeof num);
        if (x < 0) sign = true,x = -x;
        while (x)
            num[len++] = x % MOD,x /= MOD;
        if (len) len--;
        return *this;
    }
    inline int length() const
    {
        int re = len << 2,t = num[len];
        while (t) t /= 10,re++;
        return re;
    }
    inline void print()
    {
        if (sign) putchar('-');
        printf("%d",num[len]);
        for (int i = len - 1; i >= 0; i--)
            printf("%04d",num[i]);
    }
    inline friend void print_to_string(const INT &x,string &y)
    {
        stringstream stream;
        stream << x;
        stream >> y;
    }
    inline friend INT pow(const INT &x,int y)
    {
        INT re = 1,_x = x;
        while (y)
        {
            if (y & 1)
                re *= _x;
            y >>= 1;
            _x *= _x;
        }
        return re;
    }
    inline friend INT pow(const INT &x,const INT &y)
    {
        INT re = 1,_x = x,_y = y;
        while (_y != 0)
        {
            if (_y.num[0] & 1)
                re *= _x;
            _y = shr(_y);
            _x *= _x;
        }
        return re;
    }
    inline friend istream &operator >>(istream &in,INT &x)
    {
        string str;
        in >> str;
        x = str;
        return in;
    }
    inline friend ostream &operator <<(ostream &out,const INT &x)
    {
        if (x.sign) out << '-';
        out << x.num[x.len];
        for (int i = x.len - 1; i >= 0; i--)
            out.fill('0'),out.width(4),out << x.num[i];
        return out;
    }
    inline INT operator -() const
    {
        return INT(num,len,!sign);
    }
    inline friend INT abs(const INT &x)
    {
        return INT(x.num,x.len,false);
    }
    inline friend bool operator <(const INT &x,const INT &y)
    {
        if (x.sign ^ y.sign) return x.sign;
        int lx = x.length(),ly = y.length();
        if (lx == ly)
        {
            for (int i = x.len; i >= 0; i--)
                if (x.num[i] != y.num[i])
                    return (x.num[i] < y.num[i])^x.sign;
            return false;
        }
        return (lx < ly)^x.sign;
    }
    inline friend bool operator >(const INT &x,const INT &y) { return y < x; }
    inline friend bool operator <=(const INT &x,const INT &y) { return !(y < x); }
    inline friend bool operator >=(const INT &x,const INT &y) { return !(x < y); }
    inline friend bool operator ==(const INT &x,const INT &y) { return !(x < y || y < x); }
    inline friend bool operator !=(const INT &x,const INT &y) { return !(x == y); }

    inline friend INT operator +(const INT &x,const INT &y)
    {
        if (x.sign ^ y.sign)
            return x - (-y);
        INT re;
        re.sign = x.sign;
        re.len = max(x.len,y.len);
        for (int i = 0; i <= re.len; i++)
        {
            re.num[i] += x.num[i] + y.num[i];
            re.num[i + 1] = re.num[i] / MOD;
            re.num[i] %= MOD;
        }
        if (re.num[re.len + 1]) re.len++;
        return re;
    }
    inline friend INT operator -(const INT &x,const INT &y)
    {
        if (x.sign ^ y.sign)
            return x + (-y);
        INT re,_y = y;
        re.sign = _x < _y;
        if (re.sign ^ _x.sign)
            swap(_x,_y);
        for (int i = 0; i <= _x.len; i++)
        {
            re.num[i] += _x.num[i] - _y.num[i];
            if (re.num[i] < 0)
                re.num[i] += MOD,re.num[i + 1]--;
        }
        re.len = _x.len;
        while (!re.num[re.len] && re.len >= 0) re.len--;
        return re;
    }
    inline friend INT operator *(const INT &x,const INT &y)
    {
        INT re,_y = y;
        while (_y != 0)
        {
            if (_y.num[0] & 1)
                re += _x;
            _y = shr(_y);
            _x += _x;
        }
        if (y.sign) re.sign ^= 1;
        return re;
    }
    inline friend INT operator /(const INT &x,const INT &y)
    {
        if ((!y.len && !y.num[0]) || (!x.len && !x.num[0]) || abs(x) < abs(y)) { return INT(); }
        INT re,left,_y = abs(y);
        re.sign = x.sign ^ y.sign;
        re.len = x.len - y.len + 1;
        left.len = -1;
        for (int i = x.len; i >= 0; i--)
        {
            memmove(left.num + 1,left.num,sizeof(left.num) - sizeof(int));
            left.len++;
            left.num[0] = x.num[i];
            int l = 0,r = MOD - 1,mid;
            if (left < y) r = 1;
            while (l < r)
            {
                mid = (l + r) >> 1;
                INT t = mid;
                if (t * _y <= left)
                    l = mid + 1;
                else r = mid;
            }
            re.num[i] = r - 1;
            INT t = r - 1;
            left = left - (t * _y);
        }
        while (re.num[re.len] == 0 && re.len) re.len--;
        return re;
    }
    inline friend INT operator %(const INT &x,const INT &y)
    {
        if ((!y.len && !y.num[0]) || (!x.len && !x.num[0])) { return INT(); }
        INT left,_y = abs(y);
        left.sign = (x.sign && !y.sign);
        left.len = -1;
        for (int i = x.len; i >= 0; i--)
        {
            memmove(left.num + 1,mid;
            while (l < r)
            {
                mid = (l + r) >> 1;
                INT t = mid;
                if (t * _y <= left)
                    l = mid + 1;
                else r = mid;
            }
            INT t = r - 1;
            left = left - (t * _y);
        }
        return left;
    }
    inline friend INT shr(const INT &x)
    {
        INT re;
        re.len = x.len;
        for (int i = re.len; i >= 0; i--)
        {
            if (x.num[i] & 1 && i - 1 >= 0)
                re.num[i - 1] += MOD >> 1;
            re.num[i] += x.num[i] >> 1;
        }
        if (re.len && !re.num[re.len]) re.len--;
        return re;
    }
    INT &operator +=(const INT &x) { return *this = *this + x; }
    INT &operator -=(const INT &x) { return *this = *this - x; }
    INT &operator *=(const INT &x) { return *this = *this * x; }
    INT &operator /=(const INT &x) { return *this = *this / x; }
    INT &operator %=(const INT &x) { return *this = *this % x; }
};


int a[400];
int b[30];

int gcd(int a,int b){
    while(b^=a^=b^=a%=b);
    return a;
}

int main()
{
    int n;
    while(scanf("%d",&n)&&n) {
        int sum = 0;
        int i,j,k;
        f(i,1,n){
            scanf("%d",&b[i]);
            sum+=b[i];
        }
        f(i,sum) a[i] = i;
        f(i,n){
            fi(j,b[i],2){
                int t = j;
                fi(k,sum,2){
                    int tem = gcd(a[k],t);
                    a[k]/=tem;
                    t/=tem;
                    if(t == 1)
                        break;
                }
            }
        }
        INT ans = 1LL;
        f(i,sum) ans*=a[i];
        ans.print();
        printf("n");
    }
    return 0;
}