JOI春合宿 2007-day3 Anagram

問題文 アナグラム(pdf注意, 1枚目)

解法 :
元の文字列sの各文字を昇順にソートしたs'を考える.
目的の文字列の前にある順列の総数は,
s'の先頭から文字を選んでいき, 元の文字列の接頭辞にならない文字列の組み合わせを全て求めれば求まる.
もとの文字列と現在の文字がマッチした場合は, マッチした文字を先頭に起き, 残りの文字で同じ操作を繰り返す.

たとえば, "kagamiz"という文字列であれば, これをソートして"aagikmz"という文字列を得るが,

"a******", "g******", "i******", "kaa****", "kagai**"
となる文字列の組み合わせの総数が, "kagamiz"という文字列の前にある文字列となる.

'*'に入る組み合わせの総数は, 同じ物を含む順列の考え方で求めることが出来る(s!/((aの数)!*...*(zの数)!) , aの数+...+zの数=s).
これを具体的に計算で求めてやれば良い.

コード:

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long lint;

lint perm[21];

lint calc(char *str, int pos)
{
	lint ret = perm[strlen(str) - pos];
	int memo[32];
	
	memset(memo, 0, sizeof(memo));
	
	for (int i = 0; str[i] != '\0'; i++){
		if (str[i] != '*'){
			memo[str[i] - 'A']++;
		}
	}
	
	for (int i = 0; i < 26; i++){
		ret /= perm[memo[i]];
	}
	
	return (ret);
}

int main()
{
	char str[32], order[32];
	
	scanf("%s", str);
	
	
	perm[0] = 1;
	for (int i = 1; i <= 20; i++){
		perm[i] = perm[i - 1] * i;
	}
	
	int n = strlen(str);
	strcpy(order, str);
	sort(order, order + n);
	
	lint pos = 0;
	bool check[32];
	for (int i = 0; i < n; i++){
		memset(check, false, sizeof(check));
		int j;
		for (j = 0; order[j] != str[i]; j++){
			if (check[order[j] - 'A'] == true || order[j] == '*') continue;
			char t = order[j];
			order[j] = '*';
			pos += calc(order, i + 1);
			order[j] = t;
			check[order[j] - 'A'] = true;
		}
		order[j] = '*';
	}
	
	printf("%lld\n", pos + 1);
	
	return (0);
}