5f23464ec4 2014-06-28 kinaba: #include <iostream> 5f23464ec4 2014-06-28 kinaba: #include <sstream> 5f23464ec4 2014-06-28 kinaba: #include <iomanip> 5f23464ec4 2014-06-28 kinaba: #include <vector> 5f23464ec4 2014-06-28 kinaba: #include <string> 5f23464ec4 2014-06-28 kinaba: #include <map> 5f23464ec4 2014-06-28 kinaba: #include <set> 5f23464ec4 2014-06-28 kinaba: #include <algorithm> 5f23464ec4 2014-06-28 kinaba: #include <numeric> 5f23464ec4 2014-06-28 kinaba: #include <iterator> 5f23464ec4 2014-06-28 kinaba: #include <functional> 5f23464ec4 2014-06-28 kinaba: #include <complex> 5f23464ec4 2014-06-28 kinaba: #include <queue> 5f23464ec4 2014-06-28 kinaba: #include <stack> 5f23464ec4 2014-06-28 kinaba: #include <cmath> 5f23464ec4 2014-06-28 kinaba: #include <cassert> 5f23464ec4 2014-06-28 kinaba: #include <tuple> 5f23464ec4 2014-06-28 kinaba: using namespace std; 5f23464ec4 2014-06-28 kinaba: typedef long long LL; 5f23464ec4 2014-06-28 kinaba: typedef complex<double> CMP; 5f23464ec4 2014-06-28 kinaba: 5f23464ec4 2014-06-28 kinaba: class PalindromePermutations { public: 5f23464ec4 2014-06-28 kinaba: double palindromeProbability(string word) 5f23464ec4 2014-06-28 kinaba: { 5f23464ec4 2014-06-28 kinaba: map<char, int> cnt; 5f23464ec4 2014-06-28 kinaba: for(char c: word) cnt[c]++; 5f23464ec4 2014-06-28 kinaba: 5f23464ec4 2014-06-28 kinaba: vector<int> ns; 5f23464ec4 2014-06-28 kinaba: for(auto cn: cnt) ns.emplace_back(cn.second); 5f23464ec4 2014-06-28 kinaba: 5f23464ec4 2014-06-28 kinaba: return solve(ns); 5f23464ec4 2014-06-28 kinaba: } 5f23464ec4 2014-06-28 kinaba: 5f23464ec4 2014-06-28 kinaba: double solve(vector<int> c) 5f23464ec4 2014-06-28 kinaba: { 5f23464ec4 2014-06-28 kinaba: if(count_if(c.begin(), c.end(), [&](int x){return x%2==1;}) >= 2) 5f23464ec4 2014-06-28 kinaba: return 0.0; 5f23464ec4 2014-06-28 kinaba: return rec(c); 5f23464ec4 2014-06-28 kinaba: } 5f23464ec4 2014-06-28 kinaba: 5f23464ec4 2014-06-28 kinaba: double rec(vector<int> c) 5f23464ec4 2014-06-28 kinaba: { 5f23464ec4 2014-06-28 kinaba: if(c.size() <= 1) 5f23464ec4 2014-06-28 kinaba: return 1.0; 5f23464ec4 2014-06-28 kinaba: 5f23464ec4 2014-06-28 kinaba: int n = accumulate(c.begin(), c.end(), 0); 5f23464ec4 2014-06-28 kinaba: int n2 = n/2; 5f23464ec4 2014-06-28 kinaba: int k = c.back(); 5f23464ec4 2014-06-28 kinaba: int k2 = k/2; 5f23464ec4 2014-06-28 kinaba: c.pop_back(); 5f23464ec4 2014-06-28 kinaba: return C(n2,k2) / C(n,k) * rec(c); 5f23464ec4 2014-06-28 kinaba: } 5f23464ec4 2014-06-28 kinaba: 5f23464ec4 2014-06-28 kinaba: double C(int n, int k) 5f23464ec4 2014-06-28 kinaba: { 5f23464ec4 2014-06-28 kinaba: double v = 1.0; 5f23464ec4 2014-06-28 kinaba: for(int i=1; i<=k; ++i) 5f23464ec4 2014-06-28 kinaba: v = v * (n+1-i) / i; 5f23464ec4 2014-06-28 kinaba: return v; 5f23464ec4 2014-06-28 kinaba: } 5f23464ec4 2014-06-28 kinaba: }; 5f23464ec4 2014-06-28 kinaba: 5f23464ec4 2014-06-28 kinaba: // BEGIN CUT HERE 5f23464ec4 2014-06-28 kinaba: #include <ctime> 5f23464ec4 2014-06-28 kinaba: double start_time; string timer() 5f23464ec4 2014-06-28 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 5f23464ec4 2014-06-28 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 5f23464ec4 2014-06-28 kinaba: { os << "{ "; 5f23464ec4 2014-06-28 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 5f23464ec4 2014-06-28 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 5f23464ec4 2014-06-28 kinaba: void verify_case(const double& Expected, const double& Received) { 5f23464ec4 2014-06-28 kinaba: bool ok = (abs(Expected - Received) < 1e-9); 5f23464ec4 2014-06-28 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 5f23464ec4 2014-06-28 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 5f23464ec4 2014-06-28 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 5f23464ec4 2014-06-28 kinaba: #define END verify_case(_, PalindromePermutations().palindromeProbability(word));} 5f23464ec4 2014-06-28 kinaba: int main(){ 5f23464ec4 2014-06-28 kinaba: 5f23464ec4 2014-06-28 kinaba: CASE(0) 5f23464ec4 2014-06-28 kinaba: string word = "haha"; 5f23464ec4 2014-06-28 kinaba: double _ = 0.3333333333333333; 5f23464ec4 2014-06-28 kinaba: END 5f23464ec4 2014-06-28 kinaba: CASE(1) 5f23464ec4 2014-06-28 kinaba: string word = "xxxxy"; 5f23464ec4 2014-06-28 kinaba: double _ = 0.2; 5f23464ec4 2014-06-28 kinaba: END 5f23464ec4 2014-06-28 kinaba: CASE(2) 5f23464ec4 2014-06-28 kinaba: string word = "xxxx"; 5f23464ec4 2014-06-28 kinaba: double _ = 1.0; 5f23464ec4 2014-06-28 kinaba: END 5f23464ec4 2014-06-28 kinaba: CASE(3) 5f23464ec4 2014-06-28 kinaba: string word = "abcde"; 5f23464ec4 2014-06-28 kinaba: double _ = 0.0; 5f23464ec4 2014-06-28 kinaba: END 5f23464ec4 2014-06-28 kinaba: CASE(4) 5f23464ec4 2014-06-28 kinaba: string word = "hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhff"; 5f23464ec4 2014-06-28 kinaba: double _ = 0.025641025641025637; 5f23464ec4 2014-06-28 kinaba: END 5f23464ec4 2014-06-28 kinaba: /* 5f23464ec4 2014-06-28 kinaba: CASE(5) 5f23464ec4 2014-06-28 kinaba: string word = ; 5f23464ec4 2014-06-28 kinaba: double _ = ; 5f23464ec4 2014-06-28 kinaba: END 5f23464ec4 2014-06-28 kinaba: CASE(6) 5f23464ec4 2014-06-28 kinaba: string word = ; 5f23464ec4 2014-06-28 kinaba: double _ = ; 5f23464ec4 2014-06-28 kinaba: END 5f23464ec4 2014-06-28 kinaba: */ 5f23464ec4 2014-06-28 kinaba: } 5f23464ec4 2014-06-28 kinaba: // END CUT HERE