히농의 잡합다식

이산로그 (Dicrete Logarithm) 와 관련된 문제를 푸는 도중 매우 난감한 문제를 만났다. https://www.acmicpc.net/problem/21094 21094번: Discrete Logarithm is a Joke $M = 10^{18} + 31$ is a prime number. $g = 42$ is a primitive root modulo $M$, which means that $g^{1} \bmod M, g^{2} \bmod M, \ldots, g^{M-1} \bmod M$ are all distinct integers from $[1; M)$. Let's define a function $f(x)$ as the smallest positive integer www.acmic..

퀵소트가 O(n log n) 이라고 믿고있는, 지혜가 부족한 사람들을 위해서 저격 TC를 생성하는 코드를 올려보고자 한다. www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 이 문제가 O(n log n) 정렬 문제에서 가장 기초가 되는 문제일텐데 이 기초적인 문제에 퀵소트 저격 TC를 추가하면 공부를 하는 사람들이 '참교육'을 당할테니 아주 교육적인 데이터 되시겠다. 일단 급한대로 정리 안된 코드를 올린다. rand 가 복잡한 이유는, gcc ra..

이론적인 내용은 나보다는 여기나 여기같은 다른 사람들 블로그에 정리가 잘 되있다. 그냥 나중에 내가 코딩할 때 편하려고 코드 쟁여놓는 것이 글 쓰는 목적이라서 정리는 대충한다..... 기본적으로 Suffix Array는 문자열을 길이 1, 2, 4, 8, 16... 만큼 봐서 해당 길이에 대응되는 문자열끼리 정렬을 수행하는 방식이다. 이 때 2^k 문자열을 비교할 때 2^(k-1)번째 정렬된 결과를 바탕으로 정렬을 수행한다. 대충 pair[k][i] = pair(pa[k-1][i] , pa[k-1][i + 2^(k-1)]) 순서쌍을 만든 다음 이 순서쌍을 기준으로 정렬해서 최종적으로 pa[k][i] = {pair[k][i]의 순위} 가 된다.. 여기서 i+2^(k-1)이 기존 문자열을 넘어가버리면 사전순..