Problem 1183 - 排列

 1 #include<iostream>
 2 #include<vector>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int cnk(int n, int k)
 7 {
 8     int a,b;
 9     a=b=1;
10     for(int i=0; i<k; i++)
11     {
12         a *= n--;
13         b *= (i+1);
14     }
15 
16     return a/b;
17 }
18 
19 int arrange_calculate(int *a)
20 {
21     int n=0;
22     int ans=1;
23     for(int i=1; i<10; i++)
24         n += a[i];
25 
26     for(int i=1; i<10; i++)
27         if(a[i]>0)
28         {
29             ans *= cnk(n, a[i]);
30             n -= a[i];
31         }
32     return ans;
33 }
34 
35 int main()
36 {
37     int T,N;
38     cin>>T;
39     for(int i=0; i<T; i++)
40     {
41         cin>>N;
42         int a[10]={0};  //记录N中1-9出现的次数
43         int total=0;    //记录N的各个位上的数之和
44         int count=0;    //保存N有多少位，1表示个位，2表示十位，3表示百位，以此类推
45         while(N)
46         {
47             int temp = N%10;
48             total += temp;
49             a[temp]++;
50             N /=10;
51             count++;
52         }
53         int arrangeNum = arrange_calculate(a);
54 
55         int s=0;
56         for(int j=0; j<count; j++)
57         {
58             s += total;
59             total *= 10;
60         }
61 
62         int ans;
63         if(arrangeNum<count)  //此时输入的N一定是22222这种各个位上的数都相同的这种类型的数
64             ans = s/count;
65         else
66             ans = (int)(s * (arrangeNum*1.0/count)); //arrangeNum不一定是count的整数倍，比如2233对应的count=4,arrangeNum=6
67 
68         cout<<ans<<endl;
69 
70 
71     }
72     return 0;
73 }