본문 바로가기

전체 글

 (117)
백준 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 (Kitamasa) 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 이전 포스팅에서 $A_{N}$을 kitamasa법을 통해 구하는 방법에 대한 포스팅입니다. 우선 점화식을 다시 가져오면 다음과 같습..
백준 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 +..
백준 27308번: 창호의 유학 준비 https://www.acmicpc.net/problem/27308 27308번: 창호의 유학 준비 재우가 준 리스트의 단어가 각각 A, B, C이고 이 중 A, B가 Well-Known 단어라고 했을 때, 가능한 전체 경우를 문자열로 나타내면 AB, AC, BA, BC, CA, CB, CC로 그 경우의 수는 $7$가지이다. www.acmicpc.net 문제가 묻는 것은 간단해보이지만, 점화식을 이끌어내기가 생각보다는 힘들었습니다. 저는 처음에 state가 너무 많이 나와서 점화식을 유도하는 부분에서 에디토리얼을 보고 배웠습니다. 제가 틀렸던 접근은 $n$번의 공부를 했을 때 마지막으로 공부한 단어가 well-known인지 아닌지, 그리고 well-known이라면 몇 번 반복됐었는지에 따라 상태를 나누고..
Kitamasa 정답 코드 모음 복잡도 - 제목1 문제번호 - 속도 선형점화식 문제 중 행렬 곱으로도 통과하지만, kitamasa법을 사용했을 때 실행속도에서 이득을 본 문제들입니다. O(N^2) 백준 17272 - 8ms #include #include #include #define mod 1000000007 typedef long long element; typedef element* poly; // polynomial = sum poly[i] * x^i poly multiply_polynomial(poly A, int degree_A, poly B, int degree_B); poly remainder_polynomial(poly A, int degree_A, poly B, int degree_B, int* degree_resul..
백준 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..

티스토리툴바