Codeforce #765 (Div. 2)의 D. Binary Spiders를 풀다가 익혀두면 좋을 것 같은 trie의 활용법이 있어 정리해보고자 한다.
$$a_i = c_i + \Phi(s_i) - \Phi(s_{i-1})$$Splay tree는 비교적 간단한 동작 방식을 가지고 있다. 단순히 접근한 노드를 splay할 뿐인데 어떻게 각 쿼리가 (쿼리의 개수가 충분히 많을 때) $amortized \space O(\log n)$의 시간복잡도를 가질 수 있는 것일까? Potential method를 사용해 분할상환분석을 해보자.
BST(Binary Search Tree)의 한 종류인 Splay tree는, Splay라는 rotation 기반의 간단한 연산을 통해 쿼리를 할 때마다 Self Balancing을 수행한다. Splay tree는 다른 Balanced Binary Search Tree보다 구현이 (알고리즘 대회에서 구현 할 수 있을 만큼) 간단하고, 다양한 종류의 쿼리를 $amortized \space O(\log n)$시간에 수행 할 수 있다.
길이가 $n$인 문자열 $s$의 Z 배열 $z[i]$는 $s[i]$에서 시작하는 부분 문자열이면서 $s$의 prefix이기도 한 가장 긴 문자열의 길이를 담는 배열이다. Z 배열을 통해서 패턴 매칭 문제 등을 해결할 수 있다.
Z 알고리즘을 사용해 Z 배열을 $O(n)$시간에 구하는 방법을 알아보자.
$$\phi(n) = \prod p_i^{a_i - 1} (p_i - 1)$$오일러 피(파이) 함수 $\phi(n)$는 $1$부터 $n$까지 정수 중 $n$과 서로소인 수의 개수를 세는 함수이다.
$$\binom m n \equiv \prod_{i=0}^k \binom {m_i} {n_i} \pmod p $$뤼카의 정리는 음이 아닌 정수 $m, n$ 소수 $p$에 대해 $\binom m n \bmod p$를 쉽게 구할 수 있게 해주는 정리다.