题解报告：hdu 1261 字串数

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1261

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

1 2

2 2 2

Sample Output

解题思路：这道题考察全排列知识：考虑n个元素组成的多重集,其中a1重复了n1次,a2重复了n2次,…,ak重复了nk次,n=n1+n2+…+nk.
考虑n个元素的全排列，则不同的排列数为：n!/(n1!*n2!*n3!……nk!)；因为12*26=312的阶乘肯定造成数据溢出，所以要用数组来保存每一位。这道题的做法是先对当前每一种字母的个数加到s变量中，从j=1开始依次对当前的每位进行（s+j）相乘，再从高位开始枚举除以b[i]的阶乘，这样的话就简单了，大数乘法+大数除法+数组存储。。。

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[550],b[30];//a数组来保存结果,b数组是来存每种字母的个数
 4 int main()
 5 {
 6     int n,tmp,s,g;
 7     while(cin>>n&&n){
 8         memset(a,0,sizeof(a));
 9         s=0,a[0]=1;//0的阶乘是1
10         for(int i=0;i<n;i++){//表示有n种字母
11             cin>>b[i];
12             for(int j=1;j<=b[i];j++){//从1开始枚举到当前的b数组元素
13                 tmp=0;//中间值
14                 for(int k=0;k<=550;k++){//从低位开始向高位枚举当前结果的每一位
15                     tmp=a[k]*(s+j)+tmp;//先乘上(s加上当前每一位)这里的for先计算字母总个数的阶乘
16                     a[k]=tmp%10;//只留小于10的数
17                     tmp/=10;//除数保存在tmp中
18                 }
19                 tmp=0;//可以直接将tmp置为0,因为550够保存12*26阶乘结果的长度了,顺便除以当前数组b元素b[i]的阶乘
20                 for(int k=550;k>=0;k--){//从高位开始枚举除法,参照公式
21                     tmp=a[k]+tmp*10;//与乘法相反,tmp做中间量乘以10
22                     a[k]=tmp/j;//枚举当前每一位去除以j
23                     tmp%=j;//取余当前除数并保存在tmp中
24                 }
25             }
26             s+=b[i];//将每种字母的个数加到s
27         }
28         for(g=550;g>=0;g--)
29             if(a[g])break;//当最高位不为0是直接跳出
30         for(int i=g;i>=0;i--)
31             cout<<a[i];//从高位(右边)输出
32         cout<<endl;
33     }
34     return 0;
35 }