4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <sstream>
4fd800b3a8 2011-02-23        kinaba: #include <iomanip>
4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <map>
4fd800b3a8 2011-02-23        kinaba: #include <set>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: #include <numeric>
4fd800b3a8 2011-02-23        kinaba: #include <iterator>
4fd800b3a8 2011-02-23        kinaba: #include <functional>
4fd800b3a8 2011-02-23        kinaba: #include <complex>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: #include <stack>
4fd800b3a8 2011-02-23        kinaba: #include <cmath>
4fd800b3a8 2011-02-23        kinaba: #include <cassert>
4fd800b3a8 2011-02-23        kinaba: #include <cstring>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: typedef long long LL;
4fd800b3a8 2011-02-23        kinaba: typedef complex<double> CMP;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: class PalindromePhrases {
4fd800b3a8 2011-02-23        kinaba: public:
4fd800b3a8 2011-02-23        kinaba: 	vector<string> W;
4fd800b3a8 2011-02-23        kinaba: 	int N;
4fd800b3a8 2011-02-23        kinaba: 	map<pair<int,string>, LL> memo1;
4fd800b3a8 2011-02-23        kinaba: 	map<pair<int,string>, LL> memo2;
4fd800b3a8 2011-02-23        kinaba: 	map<pair<int,string>, LL> memo3;
4fd800b3a8 2011-02-23        kinaba: 	map<pair<int,string>, LL> memo4;
4fd800b3a8 2011-02-23        kinaba: 	map<pair<int,string>, LL> memo5;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	string rev(string s)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		reverse(s.begin(), s.end());
4fd800b3a8 2011-02-23        kinaba: 		return s;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	bool prefix_all(const string& p, const string& a)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		return p.size() <= a.size() && equal(p.begin(), p.end(), a.begin());
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	bool suffix_all(const string& p, const string& a)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		return p.size() <= a.size() && equal(p.begin(), p.end(), a.begin()+a.size()-p.size());
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	long long getAmount(vector <string> words)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		W = words;
4fd800b3a8 2011-02-23        kinaba: 		N = W.size();
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		LL cnt = 0;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<N; ++i)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int mask = (1<<N) - 1;
4fd800b3a8 2011-02-23        kinaba: 			mask &= ~ (1<<i);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			cnt += rec_startpalin(mask, W[i]);
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return cnt;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	LL rec_startpalin(int mask, const string& w) // #{ws | ws is palin}
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		pair<int,string> key(mask, w);
4fd800b3a8 2011-02-23        kinaba: 		if( memo1.count(key) )
4fd800b3a8 2011-02-23        kinaba: 			return memo1[key];
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		string rw = rev(w);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		LL cnt = 0;
4fd800b3a8 2011-02-23        kinaba: 		cnt += rec_end(mask, rw);
4fd800b3a8 2011-02-23        kinaba: 		for(int ov=1; ov<=w.size(); ++ov)
4fd800b3a8 2011-02-23        kinaba: 			if( w.substr(w.size()-ov) == rw.substr(0,ov) )
4fd800b3a8 2011-02-23        kinaba: 				cnt += exact(mask, rw.substr(ov));
4fd800b3a8 2011-02-23        kinaba: 		return memo1[key]=cnt;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	LL rec_endpalin(int mask, const string& w) // #{sw | sw is palin}
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		pair<int,string> key(mask, w);
4fd800b3a8 2011-02-23        kinaba: 		if( memo4.count(key) )
4fd800b3a8 2011-02-23        kinaba: 			return memo4[key];
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		string rw = rev(w);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		LL cnt = 0;
4fd800b3a8 2011-02-23        kinaba: 		cnt += rec(mask, rw);
4fd800b3a8 2011-02-23        kinaba: 		for(int ov=1; ov<=w.size(); ++ov)
4fd800b3a8 2011-02-23        kinaba: 			if( rw.substr(w.size()-ov) == w.substr(0,ov) )
4fd800b3a8 2011-02-23        kinaba: 				cnt += exact(mask, rw.substr(0,w.size()-ov));
4fd800b3a8 2011-02-23        kinaba: 		return memo4[key]=cnt;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	LL rec(int mask, const string& w) // #{ws | s is palin}
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		pair<int,string> key(mask, w);
4fd800b3a8 2011-02-23        kinaba: 		if( memo2.count(key) )
4fd800b3a8 2011-02-23        kinaba: 			return memo2[key];
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		LL cnt = (w.empty() ? 1 : 0);
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<N; ++i)
4fd800b3a8 2011-02-23        kinaba: 			if( mask & (1<<i) )
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				if( prefix_all(W[i], w) )
4fd800b3a8 2011-02-23        kinaba: 					cnt += rec( mask &~ (1<<i),
4fd800b3a8 2011-02-23        kinaba: 						w.substr(W[i].size())
4fd800b3a8 2011-02-23        kinaba: 					);
4fd800b3a8 2011-02-23        kinaba: 				else if( prefix_all(w, W[i]) )
4fd800b3a8 2011-02-23        kinaba: 					cnt += rec_startpalin( mask &~ (1<<i),
4fd800b3a8 2011-02-23        kinaba: 						W[i].substr(w.size())
4fd800b3a8 2011-02-23        kinaba: 					);
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 		return memo2[key]=cnt;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	LL rec_end(int mask, const string& w) // #{sw | s is palin}
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		pair<int,string> key(mask, w);
4fd800b3a8 2011-02-23        kinaba: 		if( memo5.count(key) )
4fd800b3a8 2011-02-23        kinaba: 			return memo5[key];
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		LL cnt = (w.empty() ? 1 : 0);
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<N; ++i)
4fd800b3a8 2011-02-23        kinaba: 			if( mask & (1<<i) )
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				if( suffix_all(W[i], w) )
4fd800b3a8 2011-02-23        kinaba: 					cnt += rec_end( mask &~ (1<<i),
4fd800b3a8 2011-02-23        kinaba: 						w.substr(0,w.size()-W[i].size())
4fd800b3a8 2011-02-23        kinaba: 					);
4fd800b3a8 2011-02-23        kinaba: 				else if( suffix_all(w, W[i]) )
4fd800b3a8 2011-02-23        kinaba: 					cnt += rec_endpalin( mask &~ (1<<i),
4fd800b3a8 2011-02-23        kinaba: 						W[i].substr(0, W[i].size()-w.size())
4fd800b3a8 2011-02-23        kinaba: 					);
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 		return memo5[key]=cnt;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	LL exact(int mask, const string& w) // # of ways to create w
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		pair<int,string> key(mask, w);
4fd800b3a8 2011-02-23        kinaba: 		if( memo3.count(key) )
4fd800b3a8 2011-02-23        kinaba: 			return memo3[key];
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		LL cnt = (w.empty() ? 1 : 0);
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<N; ++i)
4fd800b3a8 2011-02-23        kinaba: 			if( mask & (1<<i) )
4fd800b3a8 2011-02-23        kinaba: 				if( prefix_all(W[i], w) )
4fd800b3a8 2011-02-23        kinaba: 					cnt += exact( mask &~ (1<<i), w.substr(W[i].size()) );
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		return memo3[key] = cnt;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: // BEGIN CUT HERE
4fd800b3a8 2011-02-23        kinaba: #include <ctime>
4fd800b3a8 2011-02-23        kinaba: double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: int verify_case(const long long &Expected, const long long &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int N> struct Case_ { Case_(){start_time=clock();} };
4fd800b3a8 2011-02-23        kinaba: char Test_(...);
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<0>) {
4fd800b3a8 2011-02-23        kinaba: 	string words_[] = {"a","ba"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> words(words_, words_+sizeof(words_)/sizeof(*words_));
4fd800b3a8 2011-02-23        kinaba: 	long long RetVal = 2LL;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, PalindromePhrases().getAmount(words)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<1>) {
4fd800b3a8 2011-02-23        kinaba: 	string words_[] = {"ab","bcd","efg"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> words(words_, words_+sizeof(words_)/sizeof(*words_));
4fd800b3a8 2011-02-23        kinaba: 	long long RetVal = 0LL;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, PalindromePhrases().getAmount(words)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<2>) {
4fd800b3a8 2011-02-23        kinaba: 	string words_[] = {"a", "bba", "abb"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> words(words_, words_+sizeof(words_)/sizeof(*words_));
4fd800b3a8 2011-02-23        kinaba: 	long long RetVal = 7LL;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, PalindromePhrases().getAmount(words)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<3>) {
4fd800b3a8 2011-02-23        kinaba: 	string words_[] = {"aabccc", "ccbbca", "a", "acaabb", "aaa", "aab", "c", "babb", "aacaa", "b"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> words(words_, words_+sizeof(words_)/sizeof(*words_));
4fd800b3a8 2011-02-23        kinaba: 	long long RetVal = 47LL;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, PalindromePhrases().getAmount(words)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<4>) {
4fd800b3a8 2011-02-23        kinaba: 	string words_[] = {"a", "aa", "aaa"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> words(words_, words_+sizeof(words_)/sizeof(*words_));
4fd800b3a8 2011-02-23        kinaba: 	long long RetVal = 47LL;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, PalindromePhrases().getAmount(words)); }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
4fd800b3a8 2011-02-23        kinaba: template<>      void Run_<-1>() {}
4fd800b3a8 2011-02-23        kinaba: int main() { Run_<0>(); }
4fd800b3a8 2011-02-23        kinaba: // END CUT HERE