`
阿尔萨斯
  • 浏览: 4107408 次
社区版块
存档分类
最新评论

uva 11076 - Add Again(组合数学)

 
阅读更多

题目链接:uva 11076 - Add Again


解题思路:给出一个序列,要求将所有可能的序列每个序列形成的数值相加的和。


解题思路:对每个位置进行考虑,计算每种数字在这个位置出现的次数,其他位置按照组合数学去计算次数。然后有n个位置,每个位置的情况是一样的。


#include <stdio.h>
#include <string.h>

const int N = 105;
typedef unsigned long long ll;

int n;
ll C[N][N], cnt[N];

void init () {
	C[0][0] = 1;
	for (int i = 1; i <= 12; i++) {
		for (int j = 0; j <= i; j++)
			C[i][j] = C[i-1][j] + C[i-1][j-1];
	}
}

ll count () {
	int k = n - 1;
	ll t = 1;
	for (int i = 0; i < 10; i++) {
		t *= C[k][cnt[i]];
		k -= cnt[i];
	}
	return t;
}

ll solve () {
	ll tmp = 0;	
	for (ll i = 0; i < 10; i++) {
		if (cnt[i]) {
			cnt[i]--;
			ll t = count();
			cnt[i]++;
			tmp += i * t;
		}
	}

	ll ans = 0;
	for (int i = 0; i < n; i++)
		ans = ans * 10 + tmp;
	return ans;
}

int main () {
	init ();
	while (scanf("%d", &n), n) {
		memset(cnt, 0, sizeof(cnt));
		int a;
		for (int i = 0; i < n; i++) {
			scanf("%d", &a);
			cnt[a]++;
		}
		printf("%lld\n", solve ());
	}
	return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics