题解 UVa11076

题目大意 给出 \(n\) 个一位数，求出这些一位数组成的所有不同整数的和。

分析 考虑一个数对某一位的贡献，为这个数乘以其他数的全排列数，问题转化为可重复元素的全排列。

引理 \(n\) 个元素，可分为 \(m\) 组，其中本组元素全部相同，不同组元素不同，且第 \(i\) 组有 \(p_i\) 个，则总的排列数为

\[\frac{n!}{\prod_{k=1}^m p_k!}\]

证明可从 \(n\) 个位置放物品的组合数导出，这里略去。

则总的答案为各数位上的贡献之和。

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

int n;
ull tmp, ans;
ull base[13] = {0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111};
map<ull, int> m;

ull Read()
{
    ull x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return x;
}

int main()
{
    while(~scanf("%d", &n) && n) {
        ans = 0, tmp = 1, m.clear();
        for(int i = 1; i <= n; ++i)
            tmp = tmp * i / (++m[Read()]);

        map<ull, int>::iterator it = m.begin();
        while(it != m.end())
            ans += it->first * tmp * it->second / n, ++it;

        printf("%llu\n", ans * base[n]);
    }
}