TopCoder SRM 433 Div1 Easy MagicWords

問題

文字列Tがmagic wordであるとは、
Tをi(0≦i＜|T|)文字シフトした文字列がTに等しくなるようなiがちょうどK個あることを言う。

n個の文字列が与えられる。
0からn-1の数の順列p[i]について、この順に
これらの文字列を結合した文字列をSとする。
Sがmagic wordになるような順列はいくつあるか、求めよ。

制約条件

n≦8
各文字列の長さ≦20
K≦200

方針

まずは、順列から文字列を全生成する。
そのあと、文字列がmagic wordかどうかを判定するが、これをナイーブにやると
O(文字列長さ^2)の時間がかかりTLE.

rolling hashを使ってO(文字列の長さ)の時間でやるようにすれば制限時間に間に合う。

ソースコード

typedef unsigned long long ll;
ll hash[1000],pw[1000];
bool magic(int k,string &s){
  int n=s.size();
  s+=s;
  hash[0]=0; pw[0]=1;
  rep(i,n*2)pw[i+1]=pw[i]*29;
  rep(i,n*2)hash[i+1]=hash[i]+(s[i]-'A'+1)*pw[i];
  rep(i,n)if(hash[i+n]-hash[i]==hash[n]*pw[i])k--;
  return k==0;
}
class MagicWords {
  public:
  int count(vector <string> S, int K) {
    vi ord;
    int n=S.size(),ans=0;
    rep(i,n)ord.pb(i);
    do{
      string s;
      rep(i,n)s+=S[ord[i]];
      if(magic(K,s))ans++;
    }while(next_permutation(all(ord)));
    return ans;
  }
};