-
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번째 문자를 바꾼 횟수가 ai일 때 l∑i=1ai=s를 만족하는 0 이상 25 이하의 정수 a1,a2,a3,⋯,al의 경우의 수를 구하는 것과 같습니다. 따라서, 길이가 l인 문자열을 바꾼 수의 합이 s가 되도록 하는 경우의 수를 1,000,000,007로 나눈 나머지를 DP(l,s)라 하면 다음의 식이 성립합니다. DP(l,s)=min(25,s)∑k=0DP(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)≠0이면 선형 비동차점화식이라고 한다. an+k=g(n)+∑ki=0cian+i 이때 k를 점화식의 차수(order)라고 한다. 2. 간단한 경우의 계산 Calculation for a simple case 간단하게 an+2=αan+1+βan인 경우를 생각해보자. an+3=an+2=α2an+1+(αβ+β)이라고 표현할 수 있고, 다시 이때의 계수를 γ와 δ로 정의하면 an+3=γan+1+δan으로 표현할 수 있다. 즉, 계수가 달라졌을 뿐 수학적으로 근본적인 상황은 계산하고자 하는...