블로그 옮겼습니다

https://oj.uz/problem/view/KRIII5P_3 \(1\leq{N}\leq{10^5},\,0\leq{s_{i},\,e_{i}}\leq{10^9}\)N개의 구간 \([s_{i},\,e_{i}]\) 가 입력으로 주어질 때(\(s_i\gt{e_i}\) 면 공집합)구간들의 교집합이란 \([max(s_1,\,s_2,\,\cdots,\,s_k),\,min(e_1,\,e_2,\,\cdots,\,e_k)]\)구간의 길이는 \(max(0,\,e_{i}-s_{i})\) 으로 정의 될 때선택된 구간들의 교집합의 길이가 1이상이도록 구간들을 선택할 때그 선택하는 방법의 수와 그 각각의 방법에서 교집합의 길이들의 합을 구하는 문제이다. 우선 방법의 수는 라인 스위핑으로도 풀 수 있고, 좌표압축+펜윅트리로도 풀..

https://oj.uz/problem/view/KRIII5P_2 \(0\le{N}\le{10^6},\,1\le{P}\le{10^3}\)N차 다항식 \(f(x) = a_{N}x^{N}+\cdots+a_{1}x+a_{0}\) 과 소수가 주어진다.이 때 \(f(0)\,mod\,P,\,f(1)\,mod\,P,\,\cdots,\,f(P-1)\,mod\,P\) 를 각각 구하는 것이다. 우선 가장 naive 하게 생각을 해보면f(x) 를 구하는데에 걸리는 시간을 생각해 보면 빠른 N제곱을 하는데에 O(lgN) 이 걸리기 때문에각 항을 계산하는데에는 O(lgN) 이걸리는데 항의 수가 N개 이기 때문에 O(NlgN) 이 걸린다는것을 알 수가 있다.그런데 P가지의 x 에 대해 계산을 하기 때문에 O(NPlgN) 의 시간..

http://codeforces.com/contest/803/problem/E N,K