\(F_{n,k}\) の長さを各 \(n\) について計算してみると、\(|S| \le 20000\) という制約から \(n \le 22\) でなければならないことがわかります。よって答えの候補は \(n \le 22, k < 2^{n-2}\) の範囲であり、約 \(2^{21}\) 通りしかありません。そこで全探索を考えます。\(F_{n,k}\) そのものを列挙すると間に合わないので、ローリングハッシュ \(H(F_{n,k})\) を列挙します。

ローリングハッシュは文字列 \(s, t\) に対して \(H(s + t) = b^{|t|}H(s)H(t) \bmod h\) を満たすことを使えば効率的に計算できます。