1198.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 1198 on 2007-07-31 at 11:14:03 */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 32;

int C(int, int);

int main()
{
	char w[N];
	while(scanf("%s", w) != EOF && w[0] != '#') {
		int cnt[N] = { 0 };
		int n = strlen(w), m = 0;
		for(int i = 0; i < n; i++) cnt[w[i]-'a']++;
		for(int i = 0; i < n; i++) {
			int tot = n-i;
			for(int j = 0; j < w[i]-'a'; j++) {
				if(cnt[j] == 0) continue;
				int ct = tot-1, cc = 1; cnt[j]--;
				for(int k = 0; k < 26; k++)
					{ cc *= C(cnt[k], ct); ct -= cnt[k]; }
				m += cc; cnt[j]++;
			}
			cnt[w[i]-'a']--;
		}
		printf("%10d\n", m+1);
	}
	return 0;
}

int C(int m, int n)
{
	if(m+m > n) m = n-m;
	long long res = 1;
	for(int i = 0; i < m; i++)
		res = res*(n-i)/(i+1);
	return (int)res;
}