구사과

A. Strange Device Subtask 1 (10점) 문제에 적힌 대로 모든 순서쌍을 나열한 후, 정렬하여 서로 다른 순서쌍의 개수를 세자. Subtask 4/5 (20점) 고정된 $0 \le y < B$ 에 대해서 쌍이 겹칠 수 없으니, 각각 따로 문제를 해결한 후 합쳐주자. $t = qB + y$라고 하면, $x = qB + y + q$ 로 표현 가능하다. 이때, $y$ 는 상수이고, $q(B+1) + y \mod A$라는 식은 $q$가 $T = A / gcd(A, B + 1)$ 주기로 반복됨을 알 수 있다. 각각의 구간 $[L_i, R_i]$ 에 대해서, 가능한 $q$ 의 구간을 계산할 수 있다. 가능한 $q$ 의 구간을 계산했다면, 가능한 $q \mod T$ 의 구간 역시 알 수 있다. (..

Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던 옛 시간은 이젠 안녕. 이제는 백트래킹 짜고 하드 코딩해서 넣으면 끝난다. 이 글은 알고리즘의 구현법, 동작 원리나 증명에 대해서 거의 설명하지 않는다. 그 이유는 내가 구현법과 동작 원리, 증명을 모르기 때문이다. 알고리즘 구현은 여기에서 복붙해서 사용하면 된다. 이론적 배경지식이 상당히 깊지만, 그 활용도가 매우 높기 때문에, 일단 이해하지 말고 작동법부터 제대로 깨우친 후, 나중에 다시 돌아와서 방법을 이해하는 것을 추천한다. 1967년 이 알고리즘을 개발한 수학자 Elwyn Berlek..

(So, 1986)가사