Avoid the Set {00, 11} — Solution & Editorial

Back to the Problem

Build an Aho–Corasick automaton over the forbidden set, propagate terminal flags along fail links, drop dead states, and raise the surviving transfer matrix to the N-th power.

Complexity: O(S³ log N)

Watch out: A state is dead if it or any fail-ancestor completes a pattern; those must be excluded from the matrix.