Add Again(重復元素排序) UVA11076，adduva11076

Add Again(重復元素排序) UVA11076，adduva11076

Add Again

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 integerN (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

Problemsetter: Md. Kamruzzaman

Special Thanks: Shahriar Manzoor

思路：對於第x位，一共有k個元素,其中第i個元素有ni個,求全排列個數：全排列個數=（n-1）!/(n1!*n2!*n3!*n4!..(ni-1)!..*nk!)算出每個數出現在每個位置的次數，然後乘以i加起來就是i元素的貢獻值了

轉載請注明出處：尋找&星空の孩子

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define LL unsigned long long
 4 
 5 int a[10];// 題目沒有說很清楚，是0-9之間的數；
 6 int b[15];
 7 LL jie[15];
 8 int N;
 9 void init()
10 {
11     jie[0]=1;
12     for(LL i=1;i<15;i++)
13     {
14         jie[i]=i*jie[i-1];
15     }
16 }
17 LL chsort(LL x)
18 {
19     LL cnt=1;
20     for(int i=0;i<10;i++)
21     {
22         if(a[i])
23         {
24             if(i==x)
25                 cnt*=jie[a[i]-1];
26             else
27                 cnt*=jie[a[i]];
28         }
29     }
30     return cnt;
31 }
32 int main()
33 {
34    // freopen("Add.txt","r",stdin);
35 
36     LL ans,sum;
37     init();
38     while(scanf("%d",&N),N)
39     {
40         sum=0;
41         memset(a,0,sizeof(a));
42         for(int i=0;i<N;i++)
43         {
44             int tp;
45             scanf("%d",&tp);
46             a[tp]++;
47  //           sum+=b[i];
48         }
49         ans=0;
50  //       ans=jie[N-1]*sum;
51         for(LL i=0;i<10;i++)
52         {
53             if(a[i])
54             {
55                 ans+=jie[N-1]*i/chsort(i);
56             }
57         }
58         LL kk=0;
59         for(int i=1;i<=N;i++)
60         {
61             kk=kk*10+ans;
62         }
63         printf("%llu\n",kk);
64     }
65     return 0;
66 }