본문 바로가기

전체 글

 (117)
백준 2749번: 피보나치 수 3 www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 전에 올렸던 피보나치 수 6, Immortal Porpoises와 거의 동일한 문제입니다. ( 백준 11524번: Immortal Porpoises , 백준 11444번: 피보나치 수 6 ) 차이점으로는 modulo 값이 $ 10^{6} $ 으로 상당히 작다는 점입니다. 따라서 피사노 주기가 $ 15\times 10^{5} $ 이므로 이를 활용하여 코드를 짤 수 있습니다. (피사노 주기란, 피보나치 수의 mod 값의 주기를 말합니다.) 먼저 정석적으로, $ O \left ( logN \rig..
백준 11524번: Immortal Porpoises www.acmicpc.net/problem/11524 11524번: Immortal Porpoises For each data set there is a single line of output. The line consists of the data set number, K, a single space, and the number of immortal porpoise pairs alive at the end of Y years. www.acmicpc.net 본문이 매우 깁니다. 핵심 문장은 가장 마지막에 있는데, $ \cdots $ In fact, for any given year, Y, the number of living porpoise pairs is fib(Y) mod $ 10^{9} $, wher..
백준 11444번: 피보나치 수 6 www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이전에 올렸던 피보나치 문제와 거의 같은 문제입니다. (2021/01/23 - [분할 정복을 이용한 거듭제곱/행렬 거듭제곱] - 백준 7677: Fibonacci) mod $ 10^{9}+7 $ 이므로 배열을 long long으로 선언해주기만 하면 충분합니다. ( $ \left ( 10^{9}+7 \right )^{2}
백준 5095번: Matrix Powers www.acmicpc.net/problem/5095 5095번: Matrix Powers The input consists of a number of problems. Each problem starts with a line holding three numbers (N, M, and P) separated by single spaces. 1 = 1; } return result; } (C11, 1304KB, 140ms, 제출번호 28022852)
백준 10830번: 행렬 제곱 www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2021/01/23 - [분할 정복을 이용한 거듭제곱/이론] - 기본 이론2 이 글에서 다룬 것과 같은 방식으로 진행하면 됩니다. 행렬의 각 원소가 1000 이하의 숫자이므로, 오버플로우 걱정할 필요 없이 int 내에서 해결 가능합니다. #include typedef struct { int array[5][5]; } Matrix; Matrix matrix_multiply_modular (Matrix A, Matrix B, i..
백준 4862번: 마지막 자리 www.acmicpc.net/problem/4862 4862번: 마지막 자리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 b(1 ≤ b ≤ 100), 둘째 줄에는 i(1 ≤ i ≤ 100), 셋째 줄에는 n(1 ≤ n ≤ 7)이 주어진다. 마 www.acmicpc.net 기본 이론1 글에서 잠깐 언급했던 Euler's Theorem을 활용하는 문제입니다. 코드를 제시하기에 앞서, Euler's Theorem은 다음과 같습니다. $ \LARGE a^{b} \equiv a^{b mod \varphi \left ( N \right )} \left ( mod N \right ) $ 이때 $ \varphi \left ( N \right ) $ 을 Eu..
백준 7677: Fibonacci www.acmicpc.net/problem/7677 7677번: Fibonacci For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000). www.acmicpc.net 문제에서 친절하게 어떤 행렬을 n 제곱하면 $F_{n}$이 나오는지, 잘 설명해주었습니다. 따라서 기본 이론2 에서 작성한 바와 같이 접근해주면 됩니다. (2021/01/23 - [분할 정복을 이용한 거듭제곱] - 기본 이론2) 그러나 특이사항으로 "마지막 4자리"를 출력해주어야 합니다. 이는..
기본 이론2 기본 이론 1 이 글에서는 Exponentiation By Squaring을 이용하여 정사각행렬 A의 N 제곱을 구하는 방법을 알아보도록 하겠습니다. 1. Identity Matrix of Order N (한: N차 단위 행렬) Matrix라는 대상은 C/C++ 환경에서 보통 array 또는 vector로 구현됩니다. int array[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i == j) { array[i][j] = 1; } else { array[i][j] = 0; } } } (tutorial for getting an identity matrix) 위 코드에서 array를 바로 N차 단위 행렬이라고 할 수 있습니다..

티스토리툴바