분할 정복을 이용한 거듭제곱/행렬 거듭제곱 (60) 썸네일형 리스트형 백준 24415번: 편지 https://www.acmicpc.net/problem/24415 24415번: 편지 첫번째 줄에는 공백을 사이에 두고 현수가 작성한 편지의 길이 $N$, 규칙 목록의 길이 $C$, 데미지를 입은 횟수 $K$ 가 정수로 주어진다. $(1 \le N \le 100, 1 \le C \le 10^5, 1 \le K \le 10^{12})$ 두번째 줄에 www.acmicpc.net 이 문제가 생각나기도 합니다. 기본적인 아이디어는 $C$개의 규칙을 모두 합친 것을 $\lfloor \frac{K}{C} \rfloor$ 번 반복하고, $1$번째 규칙부터 $K \;\; \% \;\; C$ 번째 규칙까지 마저 진행한다는 것입니다. 각각의 규칙을 행렬로 나타내는 아이디어는 기본적으로 identity matrix에서 특.. 백준 10961번: School canteen (Matrix) https://www.acmicpc.net/problem/10961 10961번: School canteen On the standard input, you will find a single line containing three space-separated integers: n, ℓ, and k. Here n is the number of days (0 ≤ n ≤ 2,000,000,000), ℓ the impatience of the students (the number of repeats of a single meal, which causes www.acmicpc.net 아이디어가 기존에 포스팅한 문제와 똑같아서 운 좋게 풀이 시간을 크게 단축할 수 있었습니다. 우선 조건에 맞게 $N$일동안 식사를 .. 백준 30165번: Product Oriented Recurrence https://www.acmicpc.net/problem/30165 30165번: Product Oriented Recurrence The only line contains five integers $n$, $f_{1}$, $f_{2}$, $f_{3}$, and $c$ ($4 \le n \le 10^{18}$, $1 \le f_{1}$, $f_{2}$, $f_{3}$, $c \le 10^{9}$). www.acmicpc.net 고등학교 수학에서 종종 다루는 형태의 점화식입니다. $c$에 대한 로그를 씌우면 점화식은 다음과 같이 변형됩니다. $$ \log_{c}f_{x} = 2x-6 + \log_{c}f_{x-1} + \log_{c}f_{x-2} + \log_{c}f_{x-3} $$ 이제 $A_{x}$와 .. 백준 29705번: 문자열 만들기 https://www.acmicpc.net/problem/29705 29705번: 문자열 만들기 알파벳 대문자 ‘A-Z’, 알파벳 소문자 ‘a-z’, 숫자 ‘0-9’를 원소로 가지는 집합 $C$의 부분 집합 $P$를 정의역으로 하는 함수 $f(c)$가 있다. $f(c)$의 값은 $1$ 이상 $9$ 이하의 자연수이다. $1$ 이상 $ www.acmicpc.net Notation이 좀 난해한 문제였습니다. 그러나 25962번과 아이디어가 비슷하다는 걸 캐치하면, 풀이의 앞 부분은 쉽게 해결됩니다. 우선 자연수 $N$에 대해 $g(x)=N$인 $x$의 개수를 $A_{N}$으로 놓으면 $$ A_{N+9} = |S_{1}| \times A_{N+8} + |S_{2}| \times A_{N+7} + \cdots +.. 백준 24660번: High Powers https://www.acmicpc.net/problem/24660 24660번: High Powers It can be shown that the answer can be represented as a rational number $p/q$ where $p$ and $q$ are integers, $(p,q)=1$, $q>0$ and $q$ is not divisible by $998\,244\,353$. www.acmicpc.net 문제의 생김새와는 다르게 풀이는 매우 깔끔했습니다. 문제가 요구하는 것은 결국 $$ \frac{a^{n}(b^{m}-c^{m}) + b^{n}(c^{m}-a^{m}) + c^{n}(a^{m}-b^{m}}{(a-b)(b-c)(c-a)} $$ 의 값을 modulo 998244.. 백준 8506번: Leonardo's Numbers https://www.acmicpc.net/problem/8506 8506번: Leonardo's Numbers The famous Fibonacci numbers are not the only discovery of Leonardo of Pisa, also known as Fibonacci. Let us denote L0 = L1 = 1 and Li+1 = Li + Li-1 + 1 for i ≥ 1. The sequence (Li) is also called Leonardo's numbers. Today, 800 years after Leonardo Fib www.acmicpc.net 이 문제를 풀 때 크게 두 가지 방향으로 접근할 텐데, Berlekamp - Massey 같은 방법론으로 점화식을 얻어.. 백준 6673번: Firepersons https://www.acmicpc.net/problem/6673 6673번: Firepersons The input consists of several instances. Each instance is described on a single line containing the following integers separated by a single space: k, a0, , ak-1, b1, , bk, i. Here 1 백준 27318번: 세상에서 가장 달달한 디저트 만들기 (matrix) https://www.acmicpc.net/problem/27318 27318번: 세상에서 가장 달달한 디저트 만들기 한별이는 튀르키예와 그리스의 전통 젤리인 로쿰을 만들고 있다. 로쿰은 녹말, 물, 설탕, 레몬즙 등을 냄비에 넣고 끓여서 걸쭉해질 때까지 저어준 다음, 겉에 슈가파우더를 뿌려서 굳히는 디저 www.acmicpc.net 문제에서는 $N$과 $M$이 달라질 때마다 완전히 꽉 차있는 $\left ( N^{M} \right )^{3}$짜리 정육면체로부터 시작하지만, 어차피 최종 결과물은 $N,M$값에 상관없이 부피 1짜리 정육면체들로 이루어져있습니다. 즉, $N$을 고정시킨 뒤, $M$을 하나씩 늘리며 이전 단계의 로쿰이 몇 번 나타나는지 확인하는 게 떠올리기 쉬운 풀이 같습니다. 그림으로 주어.. 이전 1 2 3 4 ··· 8 다음