UVa 11076 Add Again （组合数学）

UVa 11076 Add Again （组合数学）2014-04-26 csdn博客 synapse711076 - Add Again

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？ option=com_onlinejudge&Itemid=8&category=467&page=show_problem&problem=20 17

Summation of sequence of integers is always a common problem in Computer Science. Rather than computing blindly, some intelligent techniques make the task simpler. Here you have to find the summation of a sequence of integers. The sequence is an interesting one and it is the all possible permutations of a given set of digits. For example, if the digits are <1 2 3>, then six possible permutations are <123>, <132>, <213>, <231>, <312>, <321> and the sum of them is 1332.

Input

Each input set will start with a positive integer N （1≤N≤12）. The next line will contain N decimal digits. Input will be terminated by N=0. There will be at most 20000 test set.

Output

For each test set, there should be a one line output containing the summation. The value will fit in 64-bit unsigned integer.

Sample Input Output for Sample Input

思路：平均数思想

由于每个数出现在各个位的次数是一样的，

所以ans=每个位的平均数*排列数*n个1

比如<1 1 2 2>，我们有：

完整代码：

/*0.042s*/#include<cstdio>#include<cstring>const long long one[13] ={0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111,111111111, 1111111111, 11111111111, 111111111111};long long a[10], fac[13];//factorialint main（void）{int n, num, count;long long ans;fac[0] = 1;for （int i = 1; i <= 12; i++）fac[i] = i * fac[i - 1];///计算阶乘while （scanf（"%d", &n）, n）{memset（a, 0, sizeof（a））;count = 0;for （int i = 0; i < n; i++）{scanf（"%d", &num）;count += num;a[num]++;}ans = fac[n - 1] * count;for （int i = 0; i < 10; ++i）ans /= fac[a[i]];printf（"%lld
", ans * one[n]）;}}