UVa 11076 (有重元素的排列) Add Again

n个可重复的元素的排列一共有 = All种，其中

假设这些数依次为ai，每种数字有mi个。

从右往左考虑第d位数(d≥0)，第i个数字出现的次数为，那么这个数字对所求答案的贡献为

其实可以先一次求出个位上每种数字对答案的贡献，然后乘上

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const int maxn = ;

 LL fac[maxn + ], pow10[maxn + ];

 int a[maxn + ], b[maxn + ], num[maxn + ];

 int main()

 {

     //freopen("in.txt", "r", stdin);

     fac[] = pow10[] = ;

     for(int i = ; i <= maxn; i++) { fac[i] = fac[i-] * i; pow10[i] = pow10[i-] * ; }

     for(int i = ; i <= maxn; i++) pow10[i] += pow10[i - ];

     int n;

     while(scanf("%d", &n) ==  && n)

     {

         for(int i = ; i < n; i++) scanf("%d", &a[i]);

         sort(a, a + n);

         int cnt = ;

         for(int i = ; i < n;)

         {

             int j = i;

             while(j < n && a[j] == a[i]) j++;

             b[cnt] = a[i]; num[cnt++] = j - i;

             i = j;

         }

         LL all = fac[n];

         for(int i = ; i < cnt; i++) all /= fac[num[i]];

         LL sum = ;

         for(int i = ; i < cnt; i++) sum += b[i] * num[i] * all / n;

         printf("%lld\n", sum * pow10[n-]);

     }

     return ;

 }

代码君