OUPC2012 問題G Palindromic Anagram (AOJ2356)

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2356）

制約条件

S

≦40

Sは英小文字からなる
答えは2^63以下に収まる

方針

ビットDPするか、コンビネーションを使って適当に求める。

sの長さが奇数のときは、1種類のアルファベットが中央に来る。
ほかのsに含まれる文字は全部2の倍数個でなければならない。
そうなってなかった場合は0を出力する。

ソースコード

ll C(int n,int k){
	ll res=1;
	rep(i,k)res*=n-i, res/=i+1;
	return res;
}
int main(){
	int n,cnt[26]={};
	string in;
	cin>>in;
	n=in.size();
	rep(i,n)cnt[in[i]-'a']++;
	if(n%2){
		int odd=0;
		rep(i,26)if(cnt[i]%2)odd++, cnt[i]--;
		if(odd!=1){
			cout<<0<<endl; return 0;
		}
	}
	n/=2;
	rep(i,26){
		if(cnt[i]%2){
			cout<<0<<endl; return 0;
		}
		cnt[i]/=2;
	}
	ll ans=1;
	rep(i,26)ans*=C(n,cnt[i]), n-=cnt[i];
	cout<<ans<<endl;
	return 0;
}