題目鏈接：http://www.topcoder.com/stat?c=problem_statement&pm=10195直接按描述生成S的所有排列，并計(jì)數(shù)就可以了。用map緩存一下計(jì)算結(jié)果，不然會(huì)超時(shí)
在一個(gè)整數(shù)vector上用next_permutation算法來(lái)生成所有排列的索引。
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>
#include <iostream>
#include <map>
using namespace std;
class MagicWords
{
public:
map<string,bool> m;
int count(vector <string> s, int k)
{
int ret = 0;
vector<int> v(s.size());
for(int i=0;i<v.size();++i)
v[i] = i;
m.clear();
do{
string str;
for(int i=0;i<v.size();++i){
str+=s[v[i]];
}
if( isMagic(str,k) )
ret++;
}while( next_permutation(v.begin(),v.end()) );
return ret;
}
bool isMagic(string &str,int k){
if(m.find(str)!=m.end())
return m[str];
int cnt = 1;
int len = str.size();
for(int i=1;i<len;++i){
bool ok = true;
for(int j=0;j<len;++j){
if( str[j] != str[(j+i)%len]){
ok = false;
break;
}
}
if(ok)
cnt++;
}
m[str] = (cnt==k);
return cnt==k;
}
}