HDU-1261 字串数(高精度，组合数学)-蒲公英云

HDU-1261 字串数(高精度，组合数学)

字串数

一个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

思路：对于这种排列问题，我们可以先考虑没有重复情况，也就是全排列n！。然后要把重复的部分给除掉，也就是要除去n1！n2！n3！……，然后就是答案了，不过这题数据很大，要用高精度。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
#include <functional>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1e9 + 5;
const int MAXN = 10005;
const int MOD = 30021;
const double eps = 1e-8;
const double PI = acos(-1.0);
const int L = 1005;
int a[L];
string fac(int n)
{
    string ans;
    if (n == 0) return "1";
    fill(a, a + L, 0);
    int s = 0, m = n;
    while (m) a[++s] = m % 10, m /= 10;
    for (int i = n - 1; i >= 2; i--)
    {
        int w = 0;
        for (int j = 1; j <= s; j++) a[j] = a[j] * i + w, w = a[j] / 10, a[j] = a[j] % 10;
        while (w) a[++s] = w % 10, w /= 10;
    }
    while (!a[s]) s--;
    while (s >= 1) ans += a[s--] + '0';
    return ans;
}
int sub(int *a, int *b, int La, int Lb)
{
    if (La<Lb) return -1;//如果a小于b，则返回-1 
    if (La == Lb)
    {
        for (int i = La - 1; i >= 0; i--)
            if (a[i]>b[i]) break;
            else if (a[i]<b[i]) return -1;//如果a小于b，则返回-1 
    }
    for (int i = 0; i<La; i++)//高精度减法 
    {
        a[i] -= b[i];
        if (a[i]<0) a[i] += 10, a[i + 1]--;
    }
    for (int i = La - 1; i >= 0; i--)
        if (a[i]) return i + 1;//返回差的位数 
    return 0;//返回差的位数 
}
string div(string n1, string n2, int nn)//n1,n2是字符串表示的被除数，除数,nn是选择返回商还是余数 
{
    string s, v;//s存商,v存余数 
    int a[L], b[L], r[L], La = n1.size(), Lb = n2.size(), i, tp = La;//a，b是整形数组表示被除数，除数，tp保存被除数的长度 
    fill(a, a + L, 0); fill(b, b + L, 0); fill(r, r + L, 0);//数组元素都置为0 
    for (i = La - 1; i >= 0; i--) a[La - 1 - i] = n1[i] - '0';
    for (i = Lb - 1; i >= 0; i--) b[Lb - 1 - i] = n2[i] - '0';
    if (La<Lb || (La == Lb && n1<n2)) {
        //cout<<0<<endl; 
        return n1;
    }//如果a<b,则商为0，余数为被除数 
    int t = La - Lb;//除被数和除数的位数之差 
    for (int i = La - 1; i >= 0; i--)//将除数扩大10^t倍 
        if (i >= t) b[i] = b[i - t];
        else b[i] = 0;
        Lb = La;
        for (int j = 0; j <= t; j++)
        {
            int temp;
            while ((temp = sub(a, b + j, La, Lb - j)) >= 0)//如果被除数比除数大继续减 
            {
                La = temp;
                r[t - j]++;
            }
        }
        for (i = 0; i<L - 10; i++) r[i + 1] += r[i] / 10, r[i] %= 10;//统一处理进位 
        while (!r[i]) i--;//将整形数组表示的商转化成字符串表示的 
        while (i >= 0) s += r[i--] + '0';
        //cout<<s<<endl; 
        i = tp;
        while (!a[i]) i--;//将整形数组表示的余数转化成字符串表示的</span> 
        while (i >= 0) v += a[i--] + '0';
        if (v.empty()) v = "0";
        //cout<<v<<endl; 
        if (nn == 1) return s;
        if (nn == 2) return v;
}
string jc[13] = { "0","1","2","6","24","120","720","5040","40320","362880","3628800","39916800","479001600" };
int main()
{
    int n;
    int a[30];
    int sum;
    string an;
    while (scanf("%d",&n)!=EOF)
    {
        if (n == 0)
            break;
        sum = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        an = fac(sum);
        for (int i = 1; i <= n; i++)
        {
            an = div(an, jc[a[i]],1);
        }
        cout << an << endl;
    }
}