SRM433 Div2 500

問題

文字列Tがあった時，それをi個だけ横に循環シフトしたものをT(i)とする．ここで，T(i)=Tとなるiの個数がKの時，この文字列をmagicwordと呼ぶ．
文字列の配列Sと個数Kが与えられ，その配列の文字列を順列で並び替えてくっつけた大きな文字列のうちmagicwordとなる個数を返す．

考え方

T(i)=Tの判定はO(n)でできる．なので，ある文字列のmagicwordかの判定はO(n^2)．
また，permutationでできる大きな文字列S[p[0] ]+S[p[1] ]+...はO(N!)．
O(N! * n^2)なので，普通に計算するとTLE．
計算量を減らすことを考えると，magicwordの判定かpermutationの生成のどちらか．

permutationの部分で考えると，文字列A,B,Cがあった場合，
ABCとBCAとCABのT(i)=Tの個数は同じになるので，magicwordかどうかも同じ．ACBも同様に3つが同じ．
すなわち，「一つ固定して後ろのN-1個のpermutationしたモノ(A??)ででてくるmagicwordの個数」*「同じと見なした分=N」が答え．になるので，(N-1)!回の計算になる．
すべての計算は，n^2*(N-1)!．(n=20,N=8なので，400*7!=2016000ぐらい)

反省

同じ計算を何度もしない．
計算量を削れるところを探す．