AOJ2356 Palindromic Anagram

問題リンク Palindromic Anagram

• 解法

登場する各アルファベットの個数を数えます。次に文字列の長さNの偶奇によって場合わけします。
Nが偶数のとき、奇数個登場するアルファベットが1つ以上あったら回文は作れないので答えは0となります。そうでない場合、回文の前半分における文字の並び方を考えればいいので(N/2)!を(アルファベットの個数/2)!で割っていったものが答えです。
Nが奇数のときもほとんど同じです。奇数個登場するアルファベットがただ1つだけある場合のみ回文が作れます。あとは同様に回文の前半分における文字の並び方を考えれば解けます。

• ソース

import java.util.Scanner;

//Palindromic Anagram
public class AOJ2356 {

	void run(){
		Scanner sc = new Scanner(System.in);
		long[] f = new long[21];
		f[0] = 1;
		for(int i=1;i<21;i++)f[i]=f[i-1]*i;
		char[] s = sc.next().toCharArray();
		int N = s.length;
		int[] c = new int[26];
		for(char r:s)c[r-'a']++;
		int odd = 0;
		long res = 0;
		for(int i=0;i<26;i++)odd+=c[i]%2;
		if(N%2==0){
			if(odd==0){
				res = f[N/2];
				for(int i=0;i<26;i++)if(c[i]!=0)res/=f[c[i]/2];
			}
		}
		else {
			if(odd==1){
				for(int i=0;i<26;i++)if(c[i]%2==1)c[i]--;
				res = f[(N-1)/2];
				for(int i=0;i<26;i++)if(c[i]!=0)res/=f[c[i]/2];
			}
		}
		System.out.println(res);
	}
	
	public static void main(String[] args) {
		new AOJ2356().run();
	}
}