-
Persistent Segment Tree
안녕하세요, 이번 글에서는 Persistent Segment Tree 에 대해 알아보도록 하겠습니다. Segment Tree Persistent Segment Tree를 이해하기 위해서는 Segment Tree에 대한 이해가 선행되어야 합니다. 이미 대다수의 독자분들이 Segment Tree에 대해 알고 있겠지만 다시 한 번 짚고 넘어가겠습니다. Segment Tree는 배열을 여러 구간으로 나누어 관리하는 구조로, $N$개의 원소가 있을 때 구현에 따라 2배에서 4배 정도의 추가 공간이 필요하지만 원소의 변경, 특정 범위 내의 원소의 연산을 $lgN$에 수행할 수 있습니다. 구체적으로 배열 1 2 3 4 3 2...
-
Counting the number of topologies on a finite set
Topology 수학에서, topological space란 다음 조건을 만족하는 집합 $X$와 $X$의 subset들의 collection $\tau$에 대해 ordered pair $ (X, \tau) $ 를 말한다. $ \phi, X \in \tau $ Any arbitrary union of members of $ \tau$ still belongs to $ \tau$. ($ \tau$의 원소들의 합집합은 $ \tau $의 원소이다) The intersection of any finite number of members of $ \tau$ still belongs to $ \tau$. ($ \tau$의 원소 유한개의 교집합은 $ \tau $의 원소이다) 이때...
-
PS Training 2
안녕하세요, 이번 달에도 Problem Solving 관련 글을 쓰게 되었습니다. 최근에는 참가한 대회가 없지만, 연습 과정에서 만난 문제들 중 괜찮은 문제들을 추려 모아 보았습니다. 이번에도 문제의 풀이와 소스 코드, 링크 등을 정리합니다. Circling Round Treasures Codeforces Round #221 (Div. 1)의 C번 문제입니다. $N * M$ 격자 그리드 안에 다음과 같은 것들이 놓여 있습니다. 폭탄 빈 칸 보물 장애물 주인공은 주어진 어떤 시작점에서 출발해, 상하좌우 중 빈 칸으로 이동할 수 있습니다. 이동하는 데는 1원이 듭니다. 이동을 마치고...
-
AtCoder Regular Contest 075 C Meaningful Mean 풀이
문제 요약 문제 링크 $N$개의 수가 있다. $i$번째 수를 $a_i$라 하자. 수열 $a$의 $N$개의 수에서 연속한 수들을 고르는 방법의 가지수는 $\frac{N \times (N+1)}{2}$ 개이다. $\frac{N \times (N+1)}{2}$ 개 중에서 평균이 $K$ 이상인 것이 몇개인지 구하라. $ 1 \le N \le 2 \times 10^5, 1 \le K \le 10^9, 1 \le a_i \le 10^9 $ 풀이 1. $O(N^3)$ Naive 한 방법. $\frac{N \times (N+1)}{2}$ 개의 모든 경우에 대해서, 직접 합을 구하고 평균이 $K$ 이상인지를 확인한다. 2....
-
N! mod P 의 빠른 계산
서론 $N!$ 은 1이상 $N$ 이하의 모든 정수를 곱한 수 이다. 이 $N!$는 다양한 조합론적 상황에서 많이 사용된다. 이 $N!$을 특정한 소수 $P$로 나눈 나머지를 빠르게 ($O(\sqrt{N} \log{N})$ 시간에) 계산 하는 방법에 대해서 알아본다. Naive 팩토리얼을 구하는 가장 쉬운 방법은 모든 1이상 $N$ 이하의 수를 곱해서 $P$ 로 나누는 것이다. $ab$를 $P$로 나눈 나머지와 $(a \bmod P)(b \bmod P) \bmod P$ 가 같다는 것을 이용하면, 사이에 나오는 숫자를 항상 $P^2$ 이하로 유지하면서 쉽게 구할 수...