【数论-数位统计】UVa 11076

Add Again
Input: Standard Input

Output: Standard Output

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

3 1 2 3 3 1 1 2 0

1332 444

题意：给你n个数字（0~9，1<=n<=12）,问这些数字构成的所有不重复排列的和。

分析：举个例子

含重复数字时能构成的所有不重复排列的个数为：(n!)/((n1!)*(n2!)*...*(nn!))，其中ni指数字i出现的次数。

又因为每个数字在每一位出现的概率时等可能的。

比如1 1 2，所能构成的所有情况为

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

而1、2、3出现在个、十、百位的次数时一样的，即6/3;

则每个数字在每一位出现的次数为 [(n!)/((n1!)*(n2!)*...*(nn!))]/n;（含重复数字时同样适用）

简化加法，即每个数字在每一位均出现1次时这个数字的和为 x*1...1 (n个1)

则n个数字在每一位出现times次，即为所求答案。ans = (a1+a2+...+an)*(1...1)*[(n!)/((n1!)*(n2!)*...*(nn!))]/n;

切忌：[(n!)/((n1!)*(n2!)*...*(nn!))]/n*(a1+a2+...+an)*(1...1)这样表达时错误的，当n个数字相同时，[(n!)/((n1!)*(n2!)*...*(nn!))] = 1, 1/n会得到0，所以应先乘再除；

【代码】：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
const int maxn = 15;
int x, a[maxn], num[maxn];
ull C[maxn];
const ull basic[] =
{
    1, 11, 111, 1111, 11111, 111111, 1111111, 11111111,
    111111111, 1111111111, 11111111111, 111111111111
};
void init()
{
    C[0] = C[1] = 1;
    for(int i = 2; i <= 12; i++)
    {
        C[i] = C[i-1]*i;
    }
}

int main()
{
    init();
    int n;
    while(scanf("%d", &n) && n)
    {
        memset(num, 0, sizeof(num));
        ull ans = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &x);
            ans += x;
            num[x]++;
        }
        ull times = C[n];
        for(int i = 0; i < 10; i++)
        {
            times /= C[num[i]];
        }
        ans = ans*times*basic[n-1]/n;
        cout << ans << endl;
    }
    return 0;
}