BOJ 18457 Knowledge

문제

You have a string s consisting of lowercase English letters “a” and “b”.

You can make zero or more operations in any order. Here are the possible operations:

• Delete “aa” from any place of the string.
• Delete “bbb” from any place of the string.
• Delete “ababab” from any place of the string.
• Add “aa” to any place of the string.
• Add “bbb” to any place of the string.
• Add “ababab” to any place of the string.

Your goal is to calculate the number of strings of length x that can be obtained by such operations. As the answer can be very large, find it modulo 998 244 353.

입력

The first line of the input contains one integer n: the length of the string (1 ≤ n ≤ 300 000).

The second line contains a string s of length n consisting of lowercase English letters “a” and “b”.

The third line contains one integer x (0 ≤ x ≤ 109), the length of the string you need to obtain.

출력

Print one integer: the number of strings of length x that can be obtained from string s by making the operations described above, taken modulo 998 244 353.

풀이

문자열에 "aaa", "bbb", "ababab"를 자유롭게 추가하고 제거할 수 있다. 이 작업이 항상 역연산이 가능하므로 equivalence class의 원소 개수를 세는 문제임을 알 수 있다.

free monoid의 equivalence class문제로 생각해보자. 이는 어떤 free monoid homomorphism의 kernel로 생각할 수 있고, 항등원 e, "aa", "bbb"가 같은 class로 대응되기 때문에 a의 위수가 2, b의 위수가 3인 군임을 알 수 있다.

 

이제 군 연산을 이용해서 class의 구조를 알아내면 된다. 이 구조가 군이기 때문에 right multiplicative automota는 Caley graph에 대응이 되고, 그래프를 손으로 열심히 그려보면 정점 12개의 regular directed graph를 얻을 수 있다.

 

마지막으로 우리가 구하고자 하는 것은 주어진 문자열과 같은 class의 원소이면서 길이가 x인 원소의 개수이므로 정확히 Caley graph에서 [e] class에서 시작하는 distinct walk의 개수이므로 인접행렬의 거듭제곱으로 얻을 수 있다.

 

주어진 문자열이 어떤 class에 속하는지 구분하는 방법은 여러가지가 있는데, 가장 쉬운 방법은 Caley graph가 automata인 점을 이용해 선형 시간에 어떤 클래스에 속하는지 추적하는 방법이 있고, 아니면 정말 단순하게 주어진 연산 중 문자열 길이를 줄이는 연산을 적절히 찾아 monotone deque를 이용해 문자열을 재구성하는 방법이 있다. 전자의 경우는 automata의 구조를 미리 가지고 있어야 하므로 구조를 이미 알고 있는 경우 적합하고, 후자의 경우는 일반적으로 사용할 수 있으나 이 구조가 유한 모노이드임을 모른다면 유한 시간에 끝나기 어려운 방법이다.

후자의 방법으로 문자열을 재구성하기 위해서 "aa"->e, "bbb"->e, "ababab"->e 외에도 "abba"->"bab", "aba"->"bbabb", "babba"->"bbab"의 3개의 연산을 추가로 사용했다. "aba"->"bbabb"는 문자열의 길이가 늘어나는 것이 아니냐고 생각할 수 있는데, automata의 구성 과정에서 얻어진 변환이라 정확한 근거는 모르겠지만 저렇게 변환하면 모든 class를 얻을 수 있었다.

 

추가로 이 군은 A4와 동형이고, 실제로 이 문제를 A4(isomorphic to PSL2Z3)임을 group representation <a,b|aa,bbb,ababab>만으로 알아내 해결한 사람도 있다. (링크) 하지만 group representation은 상당히 어려운 주제이고, 열심히 문자열을 분류하는 것이 가장 쉬운 방법이 아닐까 싶다.