srm625D1E.cpp

#include <algorithm>
#include <sstream>
#include <cmath>
#include <unordered_map>
using namespace std;
class PalindromePermutations {
public:
	double palindromeProbability(string word) {
		int len = word.size();
		int odd = len%2;
		unordered_map<char,int> cnt;
		for (auto i : word) ++cnt[i];
		int oddcnt = 0;
		for (auto i : cnt) oddcnt += (i.second)%2;
		if(oddcnt>odd) return 0.;
		double prob = 1;
		for (int i = 1; i <= len; i++)
			prob /= i;
		for (auto i : cnt) {
			for (int j = 1; j <= i.second; j++)
				prob *= j;
		}
		for (auto i : cnt) {
			for (int j = 1; j <= (i.second)/2; j++)
				prob /= j;
		}
		for (int i = 1; i <= len/2; i++)
			prob *= i;
		return double(prob);
	}
};