naoya_t@topcoder

SRM433 Div1 Easy: MagicWords

過去問, 練習 | 20:25 |

• next_permutationを使う方針はそのまま
• L/K周期の文字列になっているのでは
• Kとして可能性があるのは各文字の出現回数のGCDの約数のみ
• で、その最大がKなら可
• いちおうメモ化

typedef vector<int> vi;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

int gcd(int m, int n)
{
  if (m == 0 || n == 0) return 0;
  if (m == 1 || n == 1) return 1;
  if (m == n) return m;
  while (1) {
        if (m == 0) return n;
        if (n == 0) return m;
        if (m > n) m %= n; else n %= m;
  }
}

class MagicWords {
  int L, subl, k;
  set<int> alt;

  int check(const string &s){
    int kmax=0;
    tr(alt,it){
      int k_=*it;
      int sl=L/k_;
      bool c=true;
      for(int j=1;j<k_;j++){
        rep(i,sl) if(s[i]!=s[i+sl*j]) {c=false;break;}
      }
      if(c) kmax=max(kmax,k_);
    }
    return (kmax==k)?1:0;
  }
 public:
  int count(vector<string> S, int K) {
    int N=sz(S);//1-8
    L=0; k=K;
    vector<int> chc(26,0);
    rep(i,N){
      int len=sz(S[i]); L+=len;
      rep(j,len){
        chc[ S[i][j]-'A' ]++;
      }
    }
    if(L%K) return 0;
    subl=L/k;
    int g=0;
    rep(i,26){
      if(chc[i]%K) return 0;
      if(chc[i]>0) {
        g=(g==0)?chc[i]:gcd(g,chc[i]);
      }
    }
    for(int i=1;i<=g;i++){
      if(g%i)continue;
      alt.insert(i);
    }

    map<string,int> memo;
    vi iota(N); rep(i,N) iota[i]=i;
    int cnt=0;
    do{
      string w="";
      rep(i,N) w+=S[iota[i]];
      if(found(memo,w)) cnt += memo[w];
      else cnt += (memo[w]=check(w));
    } while(next_permutation(all(iota)));
    return cnt;
  }
};