분할 정복을 이용한 거듭제곱/행렬 거듭제곱 (61) 썸네일형 리스트형 백준 31987번: ESC와 쿼리 https://www.acmicpc.net/problem/31987문제에서 요구하는 것은 다음과 같습니다.$$ \sum_{x=i}^{j} a_{kx} + b_{kx} + c_{kx} \Longleftarrow \frac{d^{n}}{dx^{n}} \bigg ( e^{x}sin(x)cos(x) \bigg ) = a_{n} e^{x}sin^{2}(x) + b_{n} e^{x} cos^{2} (x) + c_{n} e^{x} sin(x) cos(x) $$ 그런데 $e^{x}$ 는 미분해도 자기 자신이며, $sin(x)$ 를 미분하면 $cos(x)$ 가 되고, $cos(x)$ 를 미분하면 $-sin(x)$ 가 된다는 것이 알려져 있습니다. 따라서, 이 값을 구하기 위해 초항부터 구해나가며 관찰을 해도 좋지만, $.. 백준 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 이전 1 2 3 4 ··· 8 다음 목록 더보기