TopCoder, SRM 625, Division 1, Level 1 : PalindromePermutations

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=11856&rd=15858

問題概要

　文字列 word が与えられる。word のアナグラムの内一つをランダムに選んだとき、それが回文となっている確率を求めよ。

解法

　文字列長を と書きます。
　文字列が回文であるとき、対応する位置（先頭と末尾・先頭 + 1 と末尾 -1, ... ）にある文字は等しくなります。従って、 が偶数のとき、word に含まれる各文字は、全て偶数個でなければなりません。 が奇数の場合は、中央にくる一文字だけが奇数個になれます。そうでない場合、word のアナグラムに回文は存在しません。
　 が奇数の場合は中央の処理が入りますが、奇数個ある文字が中央に来る確率を予め（乗法単位元に）掛けておくことで、 が偶数の場合に帰着できます。奇数個ある文字が中央に来る確率は、奇数個ある文字の数を とすれば と書けます。
　これで、全ての文字が偶数個の場合に帰着されました。この場合、一文字ずつ対応する位置に同じ文字が来る確率を求めて掛け合わせることで、全体が回文になる確率を求めることができます。今、着目している文字の数が であり、まだ考慮していない文字の数が だとします。対応する位置の片側をその文字に決めたとき、他方に同じ文字が来る確率は と書けます。この文字の考慮を終えたとき、 は ずつ減ります。
　以上のようにして求まるそれぞれの確率を全て掛け合わせた値が、全体が回文になる確率です。

コード

using VI = vector<int>;

#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

const auto odd = bind( modulus<int>(), _1, 2 );

class PalindromePermutations
{
public:
	double palindromeProbability( string word )
	{
		const int L = word.size();

		VI counts( 26 );
		FOR( c, word )
		{
			counts[ c - 'a' ]++;
		}
		
		if ( 2 <= count_if( ALL( counts ), odd ) )
		{
			return 0;
		}

		double res = 1;
		int rest = L;
		if ( L % 2 )
		{
			const auto p = find_if( ALL( counts ), odd );
			res *= 1. * (*p)-- / L;
			rest--;
		}

		FOR( num, counts )
		{
			while ( 2 <= num )
			{
				res *= 1. * ( num - 1 ) / ( rest - 1 );
				num -= 2;
				rest -= 2;
			}
		}
		return res;
	}
};