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

左手的ㄟ右手 2022-06-09 11:15 199阅读 0赞

## 字串数 ##

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