Hdu-1261 字串数

Dear 丶 2022-04-10 09:17 209阅读 0赞

**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

**问题分析：**  
不难看出是有重复元素的排列问题。  
sum = a1 + a2 + … + an;  
公式 result = sum! / (a1 ! \* a2 ! \* … \* an !);  
但是，sum的最大值已经是300多了，肯定是高精度运算。  
下面的代码：思路很简单，先求出sum！再除a1到an的阶乘。不过需要选择适当的模板，ai的范围是\[1,12\]，所以除法的话用的是高精度除以单精度，是O(n)的算法，乘法是自己写的一个模板，复杂度是O(n^2), 下面的代码是AC的。

#include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long ll;
    
    
    
    string mul(string a, string b)
    {
        
    	int len = a.size() + b.size();
    	vector<int> res(len, 0);
    	for (int i = 0; i < a.size(); i++)
    	{
        
    		for (int j = 0; j < b.size(); j++)
    		{
        
    			res[j + i] += (a[i] - '0') * (b[j] - '0');
    		}
    	}
    	string tmpres = "";
    	int i = res.size() - 2;
    	int r = 0;
    	while (i >= 0){
        
    		int t = res[i] + r;
    		tmpres = (char)(t % 10 + '0') + tmpres;
    		r = t / 10;
    		i--;
    	}
    	while (r){
        
    		tmpres = (char)(r % 10 + '0') + tmpres;
    		r = r / 10;
    	}
    	return tmpres;
    }
    
    
    string div(string a, ll b)//高精度a除以单精度b
    {
        
    	string r, ans;
    	ll d = 0;
    	if (a == "0") return a;//特判
    	for (int i = 0; i<a.size(); i++)
    	{
        
    		r += (d * 10 + a[i] - '0') / b + '0';//求出商
    		d = (d * 10 + (a[i] - '0')) % b;//求出余数
    	}
    	ll p = 0;
    	for (int i = 0; i<r.size(); i++)
    		if (r[i] != '0') {
         p = i; break; }
    	return r.substr(p);
    }
    
    ll get_n_i(int a)
    {
        
    	ll res = 1;
    	for (int i = 2; i <= a; i++)
    		res *= i;
    	return res;
    }
    
    int main()
    {
        
    	int n;
    	while (cin >> n, n)
    	{
        
    		vector<ll> nums(30);
    		int m = 0;
    
    		for (int i = 0; i < n; i++){
        
    			cin >> nums[i];
    			m += nums[i];
    			nums[i] = get_n_i(nums[i]);
    		}
    
    		string tmpa = "1";
    		for (int i = 2; i <= m; i++){
        
    			tmpa = mul(tmpa, to_string(i));
    		}
    		for (int i = 0; i < n; i++){
        
    			tmpa = div(tmpa, nums[i]);
    		}
    
    		cout << tmpa << endl;
    	}
    }