読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 2356 : Palindromic Anagram

問題リンク:Palindromic Anagram | Aizu Online Judge

問題概要:

使用した言語:Java

解法:
同じものを含む順列の公式をつかった
まず、与えられた文字列S内の各アルファベットの数を数える
アルファベットの個数が奇数のものが2つ以上あった場合は回文にはなりえないので0を出力して終了
その後、各アルファベットの数の総和を2で割ったものを各アルファベットの数を2で割ったもので割っていく
2で割っていくのは回文なので半分の状態だけ分かればあとの状態はその逆なので考える必要がないからである
つまり、高校で習った
n!
______ という同じものを含む順列の公式を使う
a!b!c!・・・

それが終わった時の値が答えである

コード:

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
 
class Main
{
 
    public static void main(String args[])throws IOException
    {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String s = in.readLine();
    int[] alpha = new int[30];
    for(int i=0;i<30;i++)
        alpha[i] = 0;
    for(int i=0;i<s.length();i++)
        alpha[s.charAt(i)-'a']++;
    int cnt = 0;
    for(int i=0;i<27;i++)
        {
        if(alpha[i]%2 == 1)
            cnt++;
        if(cnt >= 2)
            break;
        }
 
    if(cnt >= 2)
        {
        System.out.println("0");
        }
    else
        {
        int n = 0;
        int[] counter = new int[28];
        int index = 0;
        for(int i=0;i<28;i++)
            {
            if(alpha[i] == 0)
                continue;
            if(alpha[i]%2==1)
                alpha[i]--;
            counter[index++] = alpha[i]/2;
            n += alpha[i]/2;
            counter[index] = -1;
            }
 
        BigInteger N = new BigInteger("1");
        BigInteger abc = new BigInteger("1"); 
 
        for(int i=2;i<=n;i++)
            N = N.multiply(new BigInteger(Integer.toString(i)));
 
        for(int i=0;i<28;i++)
            {
            if(counter[i] == -1)
                break;
            for(int j=2;j<=counter[i];j++)
                {
                abc = abc.multiply(new BigInteger(Integer.toString(j)));
                }
            }
        System.out.println(N.divide(abc));
 
 
        }
 
    }
 
}