본문 바로가기
반응형

전체

PS를 위한 정수론 - (4) 이항 계수 (nCr mod P) 구하는 다양한 방법 이항 계수 $_{n}C_r$을 소수 $p$로 나눈 나머지를 빠르게 구하는 다양한 방법들을 알아보자. 기본적으로 특정 $n$과 $r$에 대해서 이항 계수 $_{n}C_r$을 구하는 시간은 $O(1)$이 되어야 할 때, 즉, 많은 쿼리가 들어와도 문제가 없는 경우를 고려한다. 지금부터 소개하는 방법들의 시간복잡도는 전처리하는데 필요한 시간을 의미한다. 너무 작은 $n$과 $r$에 대해서 직접 분자와 분모를 모두 곱하는 경우는 생략한다. 1. $O(n^2)$ www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 파스칼의 삼각형을 이용하는 ..
[Codeforces] Round #552 (Div. 3) A ~ E 풀이 21.01.11 12:30 virtual 참가 (1시간 20분) / performance = 1816 A. Restoring Three Numbers (*800) 입력으로 a+b, a+c, b+c, a+b+c가 랜덤 순서로 들어온다. 이를 다 더하면 3(a+b+c) 이므로, a+b+c의 값을 구해줄 수 있다. 따라서 구한 a+b+c의 값과 동일한 입력을 찾은 뒤, 해당 입력에서 나머지 세 입력을 빼주면 각각 a,b,c가 나온다. [소스 코드] #include using namespace std; using ll = long long; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ll a, b, c, d..
PS를 위한 정수론 - (3) 페르마의 소정리와 활용 (이항 계수, 밀러-라빈) [목차] 1. 페르마의 소정리 2. 오일러 정리 3. 활용 1) 이항 계수 nCr 빠르게 구하기 4. 활용 2) 밀러-라빈(Miller-Rabin) 소수 판별법 1. 페르마의 소정리 (Fermat's little theorem) 페르마의 소정리는 다음과 같다. "소수 $p$와 정수 $a$에 대해서 $a^p \equiv a \; (mod\;p)$" 만약 $a$와 $p$가 서로소이면 $a^{p-1} \equiv 1 \; (mod \;p)$ 를 만족한다. 짧지만 생각보다 PS에서 되게 많이 사용되므로 꼭 알아두는 것이 좋다. 증명 과정은 수학적 귀납법을 이용한다. (이 블로그를 참고했다) 먼저, $a$가 $p$ 이상이면, modular의 성질에 의해서 $p$로 나눈 나머지로 계산해도 동일하므로, $0 \leq..
도메인 구매 완료! rebro.kr (링크) 블로그에 쓸 개인 도메인을 구매했다..! 기존 주소인 wogud6792.tistory.com은 내가 이용하는 핸들인 rebro도 아니고, 그렇다고 BOJ 핸들인 pjh6792도 아니라 뭔가 사람들이 내 블로그를 주소로 들어오기가 힘들다는 생각이 들었다. 그래서 호스팅kr 사이트에서 1년 이용에 약 12000원 정도로 도메인을 구매했다. 이정도면 1년동안 블로그 광고 수익이랑 비슷하겠다 싶어서 아깝게 생각안하고 질러버렸다. 원래는 rebro.com을 하고싶었으나 이미 있는 관계로 kr을 썼는데 나쁘지 않은 것 같다. 확실히 사고나니까 심플해서 좋고 매우 마음에 든다 :)
[Codeforces] Round #694 (Div. 2) 풀이 2021. 01. 05 23:35 본 라운드 참가 실력이 정체되어있다. 예전엔 더 올라갈 수 있는데 운이 안 따라주는 느낌이었다면 지금은 느낌이 좀 다르다.... 재활이 꽤 오래 걸릴 것 같다. 1471A. Strange Partition 주어진 배열에서 인접한 두 원소를 대신해서 두 원소의 합으로 대체할 수 있다. 배열의 원소는 1개만큼 줄어든다. 이 연산을 원하는 만큼 한 후에, 배열의 각 원소를 x으로 나눈 값을 올림 하여 모두 더한 합의 최솟값과 최댓값을 구해야 한다. 최대인 경우는 연산을 한번도 하지 않은 원래의 배열에서 합을 구해주는 경우이고, 최소인 경우는 연산을 n-1번 적용한, 즉 배열의 원소가 1개만 남았을 때이다. [소스 코드] #include using namespace std; u..
USACO 2020 US Open Contest [Bronze] 풀이 1. [BOJ 18880] Social Distancing I Gold V [문제 설명] 일렬로 N개의 공간이 있고, 각 공간은 소가 들어있거나(1) 들어있지 않다(0). 그리고 빈 두 공간을 골라 소를 넣어주는데, 이때 소가 들어있는 두 공간 사이의 간격의 최솟값을 D라고 하면 D가 최대가 되어야 한다. [풀이] Case work 문제이다. 경우들을 잘 처리해주어야 한다. 지금부터 말하는 '구간'은 소가 배정되어있지 않은 연속된 공간을 의미한다. 우선, 가장 긴 구간에서 하나를 뽑아서 구간을 나눈 후, 다시 가장 긴 구간에서 하나를 뽑는 것이 최적일 것이라고 생각할 수 있다. 하지만 이 문제에서는 공간을 두 개 고르기 때문에 단순히 이 방식으로는 D를 최대로 만들지 못한다. 예를 들어 1, 10, 13..
[Codeforces] Round #551 (Div. 2) A ~ D 풀이 2021.01.03. 15:00 virtual 참가 / performance = 1563 [풀이] 1153A. Serval and Bus (*1000) 버스별로 정류장에 처음 도착하는 시간과 배차간격이 주어질 때, 버스정류장에 t초에 도착했을 때 제일 먼저 탈 수 있는 버스를 구하는 문제이다. 처음에 A번치고 생각보다 까다로웠으나, n이 100이고 t가 10만이기 때문에 각 버스별로 정류장에 도착하는 시간을 모두 구해줘도 무방하다. 나는 priority_queue를 이용하여 현재 pq에 담겨있는 버스들의 도착 시간 중에 제일 빠른 것을 확인해서, t보다 작다면 배차간격만큼 더해줘서 다시 넣어주고, 처음으로 t보다 큰 값이 나온 경우에 출력을 해주었다. #include using namespace std;..
[Codeforces] Educational Round 76 (A ~ E) 풀이 2021.01.01 23:00 virtual 참가 / Performance = 1841 [풀이] 1257A. Two Rival Students 수직선상에 두 사람이 서있고, 한번 작업을 수행하면 두 사람의 거리를 1만큼 더 멀게 할 수 있다. 최대 x번 작업을 수행할 수 있으므로, 멀어질 수 있을 만큼 최대한 이동시켜준다. int main(void) { int T; cin >> T; while (T--) { int n, x, a, b; cin >> n >> x >> a >> b; if (a > b) swap(a, b); cout T; while (T--) { int x, y; cin >> x >> y; if (x >= y) cout > n; vector cnt(n + 1); int ans = MAX; f..

티스토리툴바