Codeforce #765 (Div. 2)의 D. Binary Spiders를 풀다가 익혀두면 좋을 것 같은 trie의 활용법이 있어 정리해보고자 한다.

Splay tree는 비교적 간단한 동작 방식을 가지고 있다. 단순히 접근한 노드를 splay할 뿐인데 어떻게 각 쿼리가 (쿼리의 개수가 충분히 많을 때) $amortizedO(\log n)$의 시간복잡도를 가질 수 있는 것일까? Potential method를 사용해 분할상환분석을 해보자.

BST(Binary Search Tree)의 한 종류인 Splay tree는, Splay라는 rotation 기반의 간단한 연산을 통해 쿼리를 할 때마다 Self Balancing을 수행한다. Splay tree는 다른 Balanced Binary Search Tree보다 구현이 (알고리즘 대회에서 구현 할 수 있을 만큼) 간단하고, 다양한 종류의 쿼리를 $amortizedO(\log n)$시간에 수행 할 수 있다.

길이가 $n$인 문자열 $s$의 Z 배열 $z[i]$는 $s[i]$에서 시작하는 부분 문자열이면서 $s$의 prefix이기도 한 가장 긴 문자열의 길이를 담는 배열이다. Z 배열을 통해서 패턴 매칭 문제 등을 해결할 수 있다.

Z 알고리즘을 사용해 Z 배열을 $O(n)$시간에 구하는 방법을 알아보자.

오일러 피(파이) 함수 $\varphi (n)$는 $1$부터 $n$까지 정수 중 $n$과 서로소인 수의 개수를 세는 함수이다.

뤼카의 정리는 음이 아닌 정수 $m,n$ 소수 $p$에 대해 $(\genfrac{}{}{0ex}{}{m}{n})modp$를 쉽게 구할 수 있게 해주는 정리다.