분할 정복을 이용한 거듭제곱/행렬 거듭제곱 (61) 썸네일형 리스트형 백준 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.. 백준 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자리"를 출력해주어야 합니다. 이는.. 이전 1 ··· 5 6 7 8 다음