남남서의 블로그

(cms github; cms/server/static/cws_style.css#L525) before hover : RGB(153, 255, 153), RGBA(0, 255, 0, 0.4), HSLA(120˚ 혹은 85, 100%, 50%, 0.4)on hover : RGB(127, 255, 127), RGBA(0, 255, 0, 0.5), HSLA(120˚ 혹은 85, 100%, 50%, 0.5)

For a prime number \(p\), Let $$m=m_{k}p^{k}+m_{k-1}p^{k-1}+ \ldots + m_{0}p^{0},$$ $$n=n_{k}p^{k}+n_{k-1}p^{k-1}+ \ldots + n_{0}p^{0}$$ where \(0 \leq m_{i}, n_{i} < p\) Lucas' Theroem states that: $$\dbinom{m}{n} \equiv \displaystyle{\prod_{i=0}^{k}} \dbinom{m_{i}}{n_{i}} \mod p$$

Modular inverse란, 어떠한 M에 대해서, 곱셈에 대한 역원을 구하는 것이다. M이 소수이고, \(1 \leq x < M \)인 \(x\)가 있다고 하자. \(xy \equiv 1 \pmod M \)인 \(y\)를 찾을 수 있을까? Fermat's little theorem에 의해, \({x}^{M-1} \equiv 1 \pmod M\)이므로 \(y=x^{M-2}\)일 때 성립함을 쉽게 알 수 있다. 이는 combination 연산에 이용할 수 있다. \( \dbinom {n}{r} = \dfrac {n!} {r!(n-r)!} \equiv (n!) \cdot (r!)^{M-2} \cdot ((n-r)!)^{M-2} \)

거듭제곱 a의 b승을 c로 나눈 나머지를 구해야 할 때가 있습니다. 참고로 거듭제곱을 영어로는 power라고 합니다. 일단 단순히 구현하면 이렇게 할 수 있습니다. // integer power function int ipow(int a, int b, int c){ int ans = 1; for(int i = 0; i < b; ++i) { ans *= a; ans %= c; } return ans; } 한 가지 조심해야 하는 점은, 값의 범위에 따라서는 중간에 ans * a의 값이 int 범위를 넘어갈 수 있습니다. 이 문제를 피하기 위해선 중간에 잠깐 long long으로 캐스팅하면 됩니다. ... ans = ((long long) ans * a) % c; /* alternatively: ans = (..

다항식 찾기 (n+1)개의 점, 즉 $(x_i, y_i)$의 순서쌍이 (n+1)개 주어지면, 이 n개의 점을 모두 지나는 다항식을 하나 찾을 수 있다. 즉 $P(x_i) = y_i$를 모두 만족하는 $P(x)$를 찾을 수 있다. (일단 각각의 $x_i$는 모두 다르다고 하자.) 예를 들어 (1, 1)과 (2, 3)을 지나는 다항식은 $f(x)=2x-1$도 있고, $g(x)=x^2-x+1$도 있다. 이런 다항식은 여러 가지가 있고, 무한히 많다. 그런데 사실은, 그중 차수가 가장 낮은 건 n차이고, 게다가 이때의 n차 다항식은 무려 유일하다. 다항식을 왜 찾을까? ― 다항식 곱셈 문제 잠깐 다른 얘기를 해본다. 두 다항식의 곱을 계산하는 문제를 생각하자. 예를 들면 $(x^2 + x + 3)$과 $(x -..

Tree와 Heap의 합성어인 Treap은 확률적인 BST이다. Red-Black Tree, AVL Tree 등은 모든 연산에서 O(log N)의 시간복잡도를 보인다. Splay Tree 등은 평균적으로, amortized O(log N)의 시간복잡도를 보인다. Treap은 평균적으로 O(log N)이나, 최악의 경우 O(N)의 시간복잡도를 가진다. 이는 Problem Solving에서 생각보다 유용한데, 대부분의 데이터는 랜덤하게 만들기 때문에 최악의 경우가 나오기 쉽지 않다. 또한 이러한 Treap이나, 문자열의 hashing같은 경우 푸는 사람들이 사용할 소수나 알고리즘을 예측할 수 없기 때문에 임의로 최악의 경우를 만들기도 힘들다. 이제 treap이 무엇인지 설명하겠다. Treap이란 Binary..