목록2017/09 (5)
블로그 옮겼습니다
시간복잡도가 \(4^N\) 일 것같지만 \(3^N\) 이라고한다. 이유는 잘모르겠음 걍 외우자ㅎ +이유를 깨달았다부분집합(1)의 부분집합(2)이니까부분집합(1) 에 포함되거나 안되거나고, 만약 된다면 부분집합(2)에 포함되거나 안되거나니까 결국1. 부분집합(1)에 포함되지만 부분집합(2)에는 포함되지않거나2. 부분집합(1)에도 포함되고 부분집합(2)에 포함되거나3. 둘다 안포함되거나셋중 하나이기때문에 3^N
\(N,M\le{10^5}\)인덱스 이외의 모든수는 \({10^6}\) 이하의 자연수 N개의 수로 이루어진 A[i] 가 주어지고, M개의 쿼리가 주어지는데 각 쿼리는 b, l, r 로 이루어지며구해야 할 것은 b의 약수들 중에 \(A_l, A_{l+1}, \dots, A_r\) 들을 모두 나눌 수 없는 약수들의 수 이다.이 각 쿼리들의 결과를 모두 합한 값을 출력하는 문제이다.어차피 각 수는 10^6 이하이기 때문에 이런 배열을 하나 만들 수 있다.last[i] : i로 나눌 수 있는 최대 인덱스그럼 오프라인으로 각 쿼리를 r 로 오름 차순 정렬한뒤 하나하나 봐주면서 현재 쿼리의 r까지 A[i]의 약수들에 대해 last[약수] 를 i로 업뎃해준다. 그런뒤 b의 약수들에 대해 last[약수] 가 l보다 크..
http://codeforces.com/contest/535/problem/D 길이가 n인 어떤 문자열 s 가있고, 이 s안에서 k번 등장하는 어떤 패턴 p가 있다.패턴 p가 등장하는 위치를 오름차순으로 정렬한 sequence 에서 m개의 숫자로 이루어진임의의 subsequence 를 sub 이라고하자.입력으로 n, m, p, sub 가 주어질 때, 가능한 원래의 문자열 s의 가짓수를 구하는 문제이다.\(1 \le n \le 10^6\)\(0 \le m \le n - |p| + 1\)\(1 \le |p| \le n\) 우선, 길이 n인 연속된 빈 칸을 생각해 보자 여기에 p가 등장하는 위치에 p를 넣고 난 뒤빈 칸의 개수를 x라고 할 때 \(26^x\) 를 \(10^9+7\) 로 나눈 나머지를 구하는 문..
Z algorithm 은 문자열관련 알고리즘이다. 우선 Z Array 라는 것이 있다. Z[i] 의 정의는 아래와 같다. Z[i] : S[i...] 의 prefix 들 중 S의 prefix이기도 한 녀석들 중 길이가 가장 긴녀석의 길이즉, i에서 시작하는 S의 부분 문자열들 중 S의 prefix 이기도 한 녀석들 중 가장 긴 길이이다. 이 Z Array 를 O(|S|) 의 시간에 구할 수 있게 해주는 것이 Z algorithm 이다. 우선 이 것을 알면 KMP와 같이 문자열 검색이 선형시간에 가능하다. 즉, 어떤 긴 문자열 S에서 특정 패턴 P가 등장하는 위치를 모두 구하는 것이 Z 알고리즘을 활용하여 O(S + P) 에 가능한데 이 방법은 나중에 아래에서 설명하겠다. 그리고 가끔 이런 문제들이 있다. ..
문제 링크 \(0\lt{N}\le{10^3}\)\(0\lt{K}\le{10^6}\)문제는 간단하다. N개의 사람이 있고 K개의 경기가 있다.모든 경기는 적어도 한명은 참가되어야하지만 딱 한사람만 참가할 수 있다.각 사람은 적어도 한 경기는 해야하고 한 사람은 여러개의 경기를 할 수가 있다.이 때 경기가 배정되는 경우의 수를 구하는 문제이다. 우선 K가 10^6인건 훼이크라는 것을 알 수가 있다. 왜냐하면 K가 N보다 크면 모든 사람에게 적어도한경기씩 배정할 수가 없기 때문이다. 그렇기 때문에 K > N 이면 바로 0 을 출력하고 넘어간다면K > T; while(T--){ memset(dp,0,sizeof(dp)); dp[0][0] = 1; cin >> N >> K; if(K > N){ cout