SRM625 div1 easy PalindromePermutations

解法

まず、回文が存在する条件として
* それぞれの文字種の個数が全て偶数
* 一つの文字種だけ奇数でそれ以外は偶数
のいずれかの条件を満たす必要がある。文字種ごとに文字列内の個数を数え、奇数のものが2個以上あれば存在しないので0を出力する。
cnt[i] = 文字種iの個数とすると、文字列を並べ替えるパターン数は (|S|!)/(cnt[0]!cnt[1]!…cnt[25]!) となる。回文の数は (|S|/2)! / ((cnt[0]/2)!(cnt[0]/2)!…(cnt[0]/2)!) なので計算すればできる。オーバーフローに注意。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int cnt[30];

class PalindromePermutations {
   public:
   double palindromeProbability(string word)
  {
    memset(cnt, 0, sizeof(cnt));
    for(char c: word) cnt[c-'a']++;
    bool ng = false;
    int sum = 0;
    REP(i, 26) {
      if(!ng && cnt[i]%2) ng = true;
      else if(ng && cnt[i]%2) return 0;
      sum += cnt[i];
    }
    double ret = 1;
    FOR(i, (sum/2)+1, sum+1) {
      ret /= i;
    }
    REP(i, 26) {
      FOR(j, cnt[i]/2+1, cnt[i]+1) {
        ret *= j;
      }
    }
    return ret;
  }
};