-
PS 20220220-20220223
목차 1. BOJ8217 유성 2. BOJ16074 Mountaineers 3. BOJ5542 JOI 국가의 행사 4. BOJ13361 최고의 대장장이 토르비욘 5. BOJ16977 히스토그램에서 가장 큰 직사각형과 쿼리 6. BOJ13208 승현이와 승현이 BOJ8217 유성 PBS 문제이다. $x$ 일에 목표를 달성했다면 $x<y$인 임의의 $y$에 대해 $y$일에도 목표가 달성된 상태임이 보장된다. 따라서 매일의 운석 수를 빠르게 online으로 관리해주며 이분탐색 해주면 시간복잡도를 줄일 수 있다. 이때 매일의 운석 수를 빠르게 관리하는 것은 세그먼트 트리 혹은 펜윅 트리를 활용할 수 있는데, PBS 자체가...
-
[BOJ14437] 준오는 심술쟁이!!
BOJ14437 DP 연습용 문제입니다. 출력은 문자열을 구성하는 문자 자체에는 관계 없이, 오직 문자열의 길이에 영향 받습니다. 본 문제는 앞에서부터 $i$번째 문자를 바꾼 횟수가 $a_i$일 때 $\displaystyle\sum_{i=1}^{l}a_i = s$를 만족하는 0 이상 25 이하의 정수 $a_1,a_2,a_3,\cdots,a_l$의 경우의 수를 구하는 것과 같습니다. 따라서, 길이가 $l$인 문자열을 바꾼 수의 합이 $s$가 되도록 하는 경우의 수를 1,000,000,007로 나눈 나머지를 $DP(l,s)$라 하면 다음의 식이 성립합니다. \[DP(l,s) = \sum_{k=0}^{\min(25,s)} DP(l-1,s-k)\] 또한 위 식을 만족하도록 $DP(0,k)$를 정의하면 $k=0$일 때 1, 그렇지 않을...
-
CryptoHack - Elliptic Curves : Double And Broken Writeup
LOCKED PAGE
-
Extension of FLT to Matrix base
Extension of FLT to Matrix base / 페르마 소정리의 행렬로의 확장 1. 다항식의 곱셈과 행렬 다항식은 수 사이의 관계를 표현하며, 다항식의 계수만을 적어 다항식을 벡터로 표현할 수 있습니다. 다항식을 곱하면 새로운 다항식으로 전이되며 벡터에 행렬을 곱하면 새로운 벡터로 전이된다는 사실을 생각해보면 다항식의 곱셈을 행렬로 표현하는 것이 새로운 관찰을 제공할 수 있을 듯 합니다. 우선 다음과 같이 다항식 $f$와 벡터 $v$를 대응시켜봅시다. \[f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0 \\ v =...
-
Efficient Calculation of Linear Homogeneous recurrence with Matrix power
1. 선형 동차 점화식이란 What’s the Linear Homogeneous recurrence 수열의 점화식이 아래와 같이 표현될 때 $g(n)=0$이면 선형 동차점화식, $g(n)\ne0$이면 선형 비동차점화식이라고 한다. \(a_{n+k} = g(n)+\sum_{i=0}^{k} c_ia_{n+i}\) 이때 $k$를 점화식의 차수(order)라고 한다. 2. 간단한 경우의 계산 Calculation for a simple case 간단하게 $a_{n+2}=\alpha a_{n+1}+\beta a_n$인 경우를 생각해보자. $a_{n+3} = a_{n+2} = \alpha^2a_{n+1}+(\alpha\beta+\beta)$이라고 표현할 수 있고, 다시 이때의 계수를 $\gamma$와 $\delta$로 정의하면 $a_{n+3}=\gamma a_{n+1}+\delta a_{n}$으로 표현할 수 있다. 즉, 계수가 달라졌을 뿐 수학적으로 근본적인 상황은 계산하고자 하는...