Algoogle

Algorithm for Programming Contest

AOJ 2356 Palindromic Anagram

Category: AOJ Tag: math

Palindromic Anagram

問題概要


解法


各アルファベットの出現回数が奇数回なものが2個以上あったら回文にならない.
1個の時は入力のサイズが奇数以外では回文にならない.
それ以外について
それぞれの出現回数を半分にした文字列の並べ替え方の数が答え.

コード


(2356.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i = 0;i < (a); i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)
typedef long long ll;
const int MAX = 21;
ll fact[MAX];

ll comb(int n, int k){
    return fact[n]/fact[k]/fact[n-k];
}
int main(){
    string str;
    cin >> str;
    int cnt[26] = {0};
    rep(i,str.size()) cnt[str[i]-'a']++;
    int o = 0;
    rep(i,26){
        if(cnt[i] % 2) o++;
        cnt[i] /= 2;
    }
    if((!(str.size()%2) && o) || (str.size()%2 && o > 1)){
        cout << 0 << endl;
        return 0;
    }
    ll ans = 1, res = str.size()/2;
    fact[0] = 1;
    repi(i,1,MAX) fact[i] = fact[i-1] * i;
    rep(i,26)if(cnt[i]){
        ans *= comb(res,cnt[i]);
        res -= cnt[i];
    }
    cout << ans << endl;
    return 0;
}

Comments