SRM625 Div1Easy PalindromePermutations

解法
左右対称に着目して、その場合の数を求めるためにmapで数え上げた文字の数を半分にする。
奇数の文字が２つ以上あったら回文は作れない。一つの文字のみが奇数なら、中央に一文字置けば回文になる。後は同じものを含む順列を利用する。

（回文の半分の全パターンの同じものを含む順列） / （回文全体の全パターンの同じものを含む順列）

で答えが求まる。

最後のケースでのオーバーフローに注意。計算過程を long double にして tgammal() するとうまくいく。

反省
Div2のコンテストが終わった後解いてみた。まずN=1の単純なケースの例外処理を忘れて落として、その後通して 75.0pt だった。初めオーバーフローを避けるために、階乗計算の一番大きい数を掛けないで、一度分母で割って残りの階乗を書けてから、最後に一番大きな数を掛ける小細工をしたけど、あまり意味がなかったかも知れない。

using namespace std;
typedef long double ld;
class PalindromePermutations {
public:
  double palindromeProbability(string word) {
    
    int const N = word.size();
    if(N==1) return 1.0;
    map<char, int> chrs;
    for(int i=0; i<N; i++) {
      chrs[word[i]] ++;
    }
    int M = chrs.size();
    if(M>25) return 0.0;
    int oddcnt = 0;
    for(const auto& e : chrs) {
      oddcnt += e.second%2;
    }
    if(oddcnt >= 2) return 0.0;
    
    ld anume = 0;
    ld adeno = 1;
    for(const auto& e : chrs) {
      if(e.second==0) continue;
      adeno *= tgammal(e.second+1);
      anume += e.second;
    }
    ld allpat = tgammal(anume+1)/adeno;
    for(auto& e : chrs) {
      e.second /= 2;
    }
    ld nume = 0;
    ld deno = 1;
    for(const auto& e : chrs) {
      if(e.second == 0) continue;
      deno *= tgammal(e.second+1);
      nume += e.second;
    }
    return tgammal(nume+1)/deno/allpat;
  }
};