SRM 625 DIV1 Easy - PalindromePermutations (×)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11856&rd=15858
・ある文字列が与えられる。
・この文字をシャッフルした時に、回文となる確率を求める。
解き方
・まず与えられた文字列が回文となるかどうか判定する必要がある。
・すべてのアルファベットについて出現回数を調べる。
・このとき、すべてのアルファベットの出現回数が偶数回なら回文となる。
また、奇数回出現するアルファベットが１つだけなら回文となる。
それ以外は回文とならない。
・次に、回文となるときの確率を求める。
・まず奇数回出現するアルファベットがある場合、その中央にそのアルファベットを
置く必要がある。その確率はその出現回数／文字列長。
そこから出現回数と文字列長をデクリメントする。
・あとはすべてのアルファベットが偶数回の出現回数となる。
あるアルファベット２つ置く時、それが回文となるのはひとつアルファベットを置いたときに
一意に定まる。
よって、ひとつアルファベットを置かれたとき、そのあと残りのアルファベットを指定の場所に置く
ので(出現回数-1)/(L-1)となる。
（例）
L(文字列長)=4 ,アルファベットaのcnt(出現回数)=2のとき
すべての並び：aaxx, axax, axxa, xaax, xaxa, xxaa
うち回文のもの：axxa, xaax
つまり(cnt-1)/(L-1)となる。
・反省：確率の計算の基本が・・・。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PalindromePermutations {
public:
double P(int x){
double ret=1.0;
FORE(i,1,x+1)ret*=i;
return ret;
}
double palindromeProbability(string word) {
int n=word.size();
int a[26]={};
FORE(i,0,n)a[word[i]-'a']++;
int flag=0;
FORE(i,0,26)if(a[i]%2)flag++;
if(flag>1)return 0;
int L=n;
double ret=1.0;
if(flag){
FORE(i,0,26)if(a[i]%2){
ret=(double)a[i]/L;
L--;
a[i]--;
}
}
FORE(i,0,26)while(a[i]){
ret*=(double)(a[i]-1)/(L-1);
L-=2;
a[i]-=2;
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PalindromePermutations {
public:
double P(int x){
double ret=1.0;
FORE(i,1,x+1)ret*=i;
return ret;
}
double palindromeProbability(string word) {
int n=word.size();
int a[26]={};
FORE(i,0,n)a[word[i]-'a']++;
int flag=0;
FORE(i,0,26)if(a[i]%2)flag++;
if(flag>1)return 0;
int L=n;
double ret=1.0;
if(flag){
FORE(i,0,26)if(a[i]%2){
ret=(double)a[i]/L;
L--;
a[i]--;
}
}
FORE(i,0,26)while(a[i]){
ret*=(double)(a[i]-1)/(L-1);
L-=2;
a[i]-=2;
}
return ret;
}
};
