2021.01.17 problem solving

서울대학교 2020 Div2 C. 넴모넴모 2020

각각의 쿼리에 대해서, $a_x > y$ 이면 답은 자명히 0입니다. 아니면, $a_j \le y$ 를 만족하는 최소 $j$ 를 찾음으로써 간단한 수식으로 문제를 해결할 수 있습니다. 이러한 $j$는 이진탐색을 사용하여 찾으면 됩니다.

VKOShP 2017 D. Equal Maximums

두 구간이 공통으로 가지는 최댓값 $X$ 를 고정하고 문제를 해결해 봅시다. $X$ 의 등장 위치를 배열에 모두 마킹하면, 두 구간은 $X$ 를 하나 이상 포함하는 겹치지 않는 구간의 모습을 보입니다. 왼쪽 구간에서 가장 오른쪽에 등장하는 $X$ ($X_1$ 로 표기합니다.), 오른쪽 구간에서 가장 왼쪽에 등장하는 $X$ ($X_2$ 로 표기합니다.) 를 고릅시다. 이는 $X$ 의 등장 횟수의 제곱에 비례하니, 이러한 후보는 전체 배열에 $O(N^2)$ 가지 있습니다.

이 두 값이 고정되었을 때 문제의 답을 계산합시다. 다음과 같은 두 가지 경우로 케이스를 나눕니다.

• 독립된 구간 쌍: 이 경우 $X_1, X_2$ 의 사이에 $X$ 이상의 값이 존재합니다. 고로 $X_1, X_2$ 가 각 구간에서 가장 오른쪽 / 왼쪽에 등장한다는 제약 조건만 지켜주면, 어떻게 골라도 두 구간이 겹치는 것은 불가능합니다. 즉, 문제의 답을 따로 세어줄 수 있습니다.

  모든 수 $1 \le x \le N$ 에 대해서 다음과 같은 4가지 배열을 정의합시다.

  • $l[x]$: $x$ 의 왼쪽에 있으며 값이 $x$ 초과인 가장 오른쪽에 있는 수의 위치.

  • $le[x]$: $x$ 의 왼쪽에 있으며 값이 $x$ 이상인 가장 오른쪽에 있는 수의 위치.

  • $r[x]$: $x$ 의 오른쪽에 있으며 값이 $x$ 초과인 가장 왼쪽에 있는 수의 위치.

  • $re[x]$: $x$ 의 오른쪽에 있으며 값이 $x$ 이상인 가장 왼쪽에 있는 수의 위치.

  이 배열이 있을 경우, $X_1$, $X_2$ 가 고정되어 있을 때 왼쪽 / 오른쪽 구간을 고르는 경우의 수를 $O(1)$ 에 쉽게 계산할 수 있습니다. 이를 합해주면 됩니다.

• 종속적 구간 쌍: 이 경우 $X_1, X_2$ 사이에 $X$ 이상의 값이 존재하지 않습니다. 이 때는 $X_1, X_2$ 가 등장하며, 구간이 겹치지만 않으면, 이들이 각 구간에서 가장 오른쪽 / 왼쪽에 등장한다는 제약 조건이 성립됩니다. 왼쪽 구간의 왼쪽 끝점의 경우의 수, 오른쪽 구간의 오른쪽 끝점의 경우의 수를 위에서 계산한 4개의 배열로 계산합시다. 이제 $X_1, X_2$ 사이에 왼쪽 구간의 오른쪽 끝, 오른쪽 구간의 왼쪽 끝점을 배치해야 합니다. 이는 두 원소의 길이에 비례하는 수식입니다. 역시 $O(1)$ 에 계산됩니다.

이 때, 종속적 구간 쌍 이 등장하는 경우는 $X$ 의 인접한 등장 위치를 $X_1, X_2$ 로 골랐을 때 뿐이니, $O(N)$ 개 밖에 없어서 단순히 계산해 줄 수 있습니다. 독립된 구간 쌍은, 답의 경우가 (왼쪽 구간) * (오른쪽 구간) 과 같이 나오므로 나름대로 독립적으로 생각할 수 있습니다. 오른쪽 구간의 위치를 고르면 가능한 왼쪽 구간의 위치는 $X$ 의 등장 횟수를 기준으로 prefix를 이룹니다. 고로 부분합으로 계산할 수 있습니다.

고로 $O(N)$ 에 모든 경우를 계산할 수 있습니다. 추가로, 각 수에 대해서 등장 위치를 증가순으로 알아야 하기 때문에 정렬이 필요합니다. 전체 문제는 $O(N \log N)$ 에 풀립니다.

VKOShP 2017. Circuit

지문에도 나와있듯이 문제의 그래프는 재귀적으로 작은 그래프를 합쳐나감으로써 만들어 낼 수 있습니다. 이 재귀적인 병합 과정을 루트 있는 트리로 나타내 봅시다. 트리의 리프는 Base case인 정점 하나이고, 내부 노드는 두 개의 자식을 가지고 있으며 (합치는 대상이 되는 그래프) 이들을 직렬 혹은 병렬 연결로 합칩니다. 루트 노드는 가장 마지막에 한 연산이 될 것입니다.

이 병합 과정을 나타낸 트리가 있다면 문제를 간단한 DP로 해결할 수 있습니다. 그래프를 지문의 형태로 분해하면 DP 값이 깔끔하게 합쳐지기 때문입니다.

• $connect[G]$ 를 $G$ 의 MST 개수.
• $disconnect[G]$ 를 $G$ 에서 소스 노드와 싱크 노드가 이미 연결되어 있다고 볼 때 MST 개수 라고 합시다. 다른 말로, 사이클이 없으면서 소스를 포함하는 컴포넌트와 싱크를 포함하는 컴포넌트 두개만 존재하게 하는 간선의 부분집합입니다.

이렇게 정의한 후 점화식을 적으면 됩니다. $G$ 의 케이스는 간선 하나, 직렬 연결, 병렬 연결, 이렇게 3가지가 있습니다. 간선 하나일 때는 $connect[e] = disconnect[e] = 1$ 이라는 자명한 점화식이 나옵니다. 그 외 경우에는 둘 다 연결하거나, 하나만 연결하거나, 둘 다 하지 않거나, 정도로 식이 나와서 역시 간단하게 구할 수 있습니다.

병합 과정을 찾는 것이 핵심입니다. Top down 형태로 루트 노드의 자식을 찾아서 내려가는 방식의 Decomposition은 잘 안 됩니다. 하지만 트리는 Bottom-up으로도 떼어낼 수 있습니다. 병합 과정을 나타낸 트리에서, 리프 두 개를 합친 노드를 찾아서, 이를 리프로 변환하는 과정을 반복합시다. 이렇게 될 경우 최종적으로 트리는 하나의 리프 (간선 하나) 로 줄어들 것이고, 변환 과정을 역추적하면서 원래 트리도 찾을 수 있습니다. 이러한 노드는 두 간선을 합친 길이 2의 경로거나 (직렬), 다중 간선 (병렬) 의 형태를 띕니다.

이 관찰을 역으로 사용해서, 길이 2의 경로나 다중 간선을 반복해서 하나의 간선으로 묶어주는 방법으로 트리를 줄여나갈 것입니다. 이것이 가능하려면 더 강한 조건이 성립해야 합니다. 단순히 "리프를 합치면 길이 2의 경로나 다중 간선이 나온다" 말고, "길이 2의 경로나 다중 간선은 항상 리프 두개를 합친 것이라고 볼 수 있다" 는 것을 보여야 합니다. 이 명제 자체는 사실이 아니지만, 만약에 리프 두개를 합친 것이 아니라면, 해당 위치의 LCA를 기준으로 연산 순서를 잘 바꿔서 두개를 합친 것으로 바꿔줄 수 있습니다. 그래서 위 명제는 성립합니다.

이를 통해서 간단한 $O(M^2)$ 풀이를 만들 수 있습니다. 다중 간선은 정렬 후 hashmap 등으로 찾고, 길이 2의 경로는 degree 2의 노드를 찾으면 $O(M)$ 시간에 간선 개수를 하나 줄일 수 있기 때문입니다. 최적화를 하기 위해서는, degree 2인 노드들을 queue로 관리하고, 다중 간선을 만들 때마다 바로 합쳐주는 연산을 수행하는 식으로 구현해 주면 $O(M)$ 에 풀립니다.

여담으로 이러한 그래프는 Series-parallel graph 라고 불립니다. Series는 직렬, Parallel은 병렬이라는 뜻입니다. Treewidth가 2 이하인 그래프는 항상 Series-parallel graph의 트리로 표현할 수 있다는 중요한 성질이 있어서, Polynomial time에 Recognition할 수 있으며 다양한 문제가 다항 시간에 풀립니다. Treewidth가 2 이하이기 때문에, 트리 DP, Centroid decomposition, HLD, Sparse table과 같은 트리에서 사용하는 전통적인 테크닉 역시 그대로 사용할 수 있습니다. Treewidth가 2 이하인 그래프가 입력으로 주어지는 그래프의 예시는 UCPC 2019 예선 %, NEERC 2015 Distance on triangulation, JOISC 2017 Railway Trip 등이 있습니다.

BOJ 20655. Wind Of Change 2020

2018 중국 IOI 선발고사 기출입니다.

두 트리에 대해서 $dep(LCA(u, v))$ 의 합을 최소화한다는 것은 불편한 조건입니다. 하지만 문제에도 적혀 있는 식인 $dep(u) + dep(v) - 2dep(LCA(u, v)) = dist(u, v)$ 을 사용하면, 결국 최대화해야 하는 것이

$dist_1(u, v) + dist_2(u, v) + (dist_1(1, u) - dist_2(1, u)) + (dist_1(1, v) - dist_2(1, v))$

를 2로 나눈 값이라는 것을 알 수 있습니다. 편의상 $f(v) = dist_1(1, v) - dist2_(1, v)$ 라고 두면

$dist_1(u, v) + dist_2(u, v) + f(u) + f(v)$

가 됩니다. 이는 Wind of Change 문제에서 나온 식과 유사하며, 실제로 비슷하게 풀립니다.

$T_1$ 에 대해서 Centroid decomposition을 한 후, 서로 다른 서브트리에서 온 $u, v$ 쌍을 모두 고려해 줍시다. (이렇게 할 경우 $u = v$ 인 케이스는 고려가 안 되는 문제가 있는데, 마지막에 예외 처리 해 줘야 합니다.) $u, v$ 가 Centroid 기준으로 서로 다른 서브트리에서 왔다면 $dist_1(u, v) = dist_1(u, c) + dist_1(c, v)$ 가 됩니다. 고로 $g(u) = f(u) + dist_1(c, u)$ 라고 정의하면, 서로 다른 서브트리에서 온 쌍에 대해서 $dist_2(u, v) + g(u) + g(v)$ 를 최소화 해 줘야 합니다.

만약에 이를 $O(n)$ 에 해 주고 싶다면, 각각의 서브트리 $v$ 에 대해서, 해당 서브트리 자식 중 $dist_2(v, w) + g(w)$ 의 최댓값을 들고 있는 식으로 해결할 수 있습니다. 서로 다른 서브트리에서 왔다는 조건을 맞춰줘야 하기 때문에, 서브트리 라벨을 기준으로 두 번째 최댓값 역시 관리해야 합니다. 이를 그대로 하면 느리지만, Centroid에서 현재 도달 가능한 쌍에 대해서만 이를 해 줘도 상관이 없습니다. 고로, JOI 2014 Factories와 유사하게, 트리 압축을 한 후, 위에서 말한 DP를 그대로 돌려주면 $O(n \log n)$ 에 Centroid $c$ 를 지나는 모든 쌍을 고려햘 수 있어, 전체 문제가 $O(n\log^2 n)$ 에 풀립니다.

OpenCup 2019/2020 GP of Moscow. Deja Vu

문제에서 구하는 것은 결국 LIS (Longest Increasing Subsequence) 를 4 이상으로 만드는 최소 끝점입니다. LIS를 구하는 방법 중 길이 $i$ 의 증가 수열 중 마지막 원소의 최솟값 을 저장하는 DP가 잘 알려져 있습니다 (이분 탐색 한 후 원소 바꾸는 알고리즘을 뜻합니다.) 여기서는 LIS의 값이 4 이상인지만 중요하니까, 이 DP의 첫 4개 값만 중요합니다.

고로 각각의 쿼리에 대해서 다음과 같은 식으로 Naive하게 문제를 해결할 수 있습니다. $x = l$ 에서 시작하여:

• $a_i \geq x$ 일 경우 $a_i = x$ 로 설정.
• 그렇지 않고 $b_i \geq x$ 일 경우 $b_i = x$ 로 설정.
• 그렇지 않고 $c_i \geq x$ 일 경우 $c_i = x$ 로 설정.
• 그렇지 않을 경우 LIS가 4가 되었으니 해당 시점을 보고.

초기 $(a_i, b_i, c_i) = (\infty, \infty, \infty)$ 이고, $a_i < b_i < c_i$ 가 매 시점에 성립함을 관찰합시다.

이제 문제를 오프라인으로 해결합시다. $a_i = x$ 라는 갱신 쿼리가 있다는 시점에서 오프라인 풀이가 나오는 게 새롭지만, 생각보다 오프라인 풀이가 잘 맞는 설정입니다. 각 쿼리를 시간 순으로 정렬하고, 쿼리마다 $(a_i, b_i, c_i)$ 값을 관리합니다. 오프라인 쿼리니까, 결국 우리는 $x_i$ 가 어떤 시간 구간에 어떠한 값을 가지는지를 전부 알 수 있습니다. $1, 2, \ldots, N$ 에 대해서 순서대로 각 구간에 대해서 $a_i, b_i, c_i$ 를 위 방법대로 갱신하는 구간 쿼리를 하고, 구간 쿼리 과정에서 LIS가 4가 되는 지점을 보고하는 식의 풀이를 사용합니다.

이 과정에서 어떠한 쿼리들은 무시해야 합니다. 예를 들어서 이미 LIS가 4가 된 쿼리들이나, 아직 구간의 왼쪽 끝인 $l$ 에 도달하지 않은 쿼리들은 중요하지 않습니다. 이들은 $(-\infty, -\infty, -\infty)$ 로 설정될 경우 위 알고리즘에 의해서 갱신되지 않습니다. LIS = 4로 보고하지만 않게 주의해서 구현하면 됩니다.

이제 위 알고리즘을 구현해 봅시다. 위 알고리즘은 4개의 독립적인 프로시저로 나눌 수 있습니다. 즉, 4개 사이에서는 어떤 순서로 실행하던 상관이 없습니다. (물론 그래도 순서대로 실행할 겁니다.)

• $a_i > x$ 일 경우 $a_i = x$ 로 설정.
• $a_i < x, b_i > x$ 일 경우 $b_i = x$ 로 설정.
• $b_i < x, c_i > x$ 일 경우 $c_i = x$ 로 설정.
• $-\infty < c_i < x$ 일 경우 $(a_i, b_i, c_i) = (-\infty, -\infty, -\infty)$ 로 갱신 후 해당 위치 보고.

첫 번째는 사실 아무 Lazy propagation으로 하면 되지만, 두 번째 쿼리로 확장이 잘 안 됩니다. 고로 Segment Tree Beats를 사용합시다. $a_i < x$ 가 아니면 $a_i = x$ 이니, $a_i$ 의 최댓값과 두 번째 최댓값을 가지고 있으면 됩니다. 이러면

• 1번 쿼리는 일반적인 Segment Tree Beats의 요령으로 $a_i$ 의 최댓값, 두 번째 최댓값을 관리하면 가능합니다.
  • 둘 다 자신보다 크면 서로 다른 $a_i$ 를 줄일 수 있고, 그것이 아니라면 Lazy하게 밀 수 있습니다.
• 2번 쿼리는 $a_i$ 의 최댓값 중 $b_i$ 의 첫 / 두 번째 최댓값, $a_i$ 의 최댓값이 아닌 것 중 $b_i$ 의 첫 / 두 번째 최댓값 을 관리합니다.
  • 둘 다 자신보다 크면 서로 다른 $b_i$ 를 줄일 수 있고, 그것이 아니라면 Lazy하게 밀 수 있습니다.
• 3번 쿼리는 $a_i$의 최댓값 / 최댓값이 아닌 것 중 $b_i$ 의 최댓값 / 최댓값이 아닌 것 중 $c_i$ 의 최댓값을 관리하면 됩니다.
  • 여기서는 Beats의 요령은 딱히 필요 없고 그냥 Lazy하게 밀어주면 됩니다.
• 4번 쿼리는 $c_i$ 의 최솟값을 관리하면 됩니다.
  • 구현 팁은, $c_i$ 의 최솟값을 관리할 때 $-\infty$ 는 무시해 주는 것입니다. 정확히는, $-\infty$ 를 $\infty$ 로 저장해 줘도 사실 상관이 없습니다. 3번 쿼리에서 보는 $c_i$ 와 4번 쿼리에서 보는 $c_i$ 가 다르기 때문입니다.

Ptz Winter 2020 Day5 L. Wizards Unite

금 키 하나로 시간이 가장 짧은 $N-K$ 개의 상자를 열고 나머지를 은 키로 열면 됩니다. 수열을 $O(N \log N)$ 에 정렬하면 문제를 해결할 수 있습니다. 혹은 수열에서 $N-K$ 번째로 큰 수를 $O(N \log N)$ 정도에 찾아도 됩니다.

BOJ 20654. 음료수는 사드세요 제발

2018 중국 선발고사 기출입니다.

모든 액체의 맛이 1이라고 가정하면, 음료수를 대접할 수 있는 지 없는지만 확인하면 됩니다. 이는 단순 그리디로 가능합니다. 각 액체들을 $p_i$ 가 증가하는 순으로 정렬한 후, 그 순서대로 음료수를 최대한 만들며, $L_j$ 만큼의 음료수를 채웠을 때 가격이 원하는 값 이하인지를 확인하면 됩니다.

음료수의 맛은 액체의 맛의 최솟값이 결정하니, 액체들을 맛이 감소하는 순으로 정렬한 후 위 그리디 전략이 참을 반환하는 최소 길이 prefix를 찾으면 됩니다. 이는 이분 탐색으로 찾을 수가 있겠으나 쿼리마다 문제를 해결해야 하니, parallel binary search를 사용합시다.

Parallel binary search를 사용하면, 특정 쿼리는 한 prefix에 대해서 해당 그리디가 만족하는 지를 판별합니다. 결국, 액체를 적당히 추가하고, 현재 액체 집합에 대해 위의 그리디가 $(g, L)$ 에 대해서 참을 반환하는 지 아닌지를 판별하는 자료구조가 있으면 될 것입니다. $p_i$ 를 key로 하고, $p_i \times l_i$ 를 값으로 하는 Fenwick tree를 만들면, $O(\log N)$ 시간에 $g$ 만큼의 양을 채우는 첫 $p_i$ 지점을 찾을 수 있습니다. 이 때의 음료수 양이 $L$ 인지는 $l_i$ 를 값으로 하는 Fenwick tree를 또 만들면 단순 수식으로 계산이 가능합니다.

Parallel binary search의 각 반복을 이 방식으로 $O((N+M) \log N)$ 에 해결할 수 있고, 결국 전체 문제는 $O((N+M) \log^2 N)$ 에 해결됩니다.

Ptz Summer 2020 Day1 H. Islands

문제의 첫 부분은 CEOI 2011 Traffic과 비슷합니다. 각 대피소에 대해서, 해당 대피소에 도달 가능한 거주지의 집합은 항상 다음 세 경우 중 하나라는 것을 관찰할 수 있습니다:

• 도달 가능한 거주지가 없음
• 모든 거주지에서 도달 가능함
• 둘 다 아니고, 대신 어떠한 연속한 거주지 원호 구간에서 도달 가능함 ($l, l+1, \ldots, r$ 혹은 $l, l+1, \ldots, a, 1, \ldots, r$)

이러한 성질이 관찰되는 것은 그래프가 평면 그래프이기 때문입니다. 만약에 거주지의 집합이 첫 두 조건이 아니라면, 도달할 수 있는 가장 "왼쪽" 과 "오른쪽" 거주지로 가는 경로 두 개를 찾을 수 있습니다. 그 사이에 있는 거주지에서는 임의의 대피소로 갈 수 있으며, 만약 그 대피소가 현재 대피소가 아니라고 하면, 두 경로 중 하나에 무조건 부딪혀야 합니다. 고로 이 성질은 항상 성립합니다.

이를 구하는 방법은 SCC를 사용하여 가능합니다. 전체 그래프에 대한 SCC를 만듭시다. 한 SCC에서 도달 가능한 거주지의 집합도 위 세 조건 중 하나를 만족합니다. 고로 위상 정렬 순서대로 DP를 돌려 합집합을 관리할 수 있습니다. 위 세 경우는 모두 $O(1)$ 크기의 공간으로 관리할 수 있고, 여러 집합의 합집합을 취하는 것 역시 정렬 후 가능합니다. 고로 거주지 집합을 $O((n + m) \log n)$ 에 찾을 수 있습니다.

두 번째 부분은 이제 이 집합들 중 합집합을 취했을 때 모든 거주지가 나오는 경우를 세는 것입니다. 먼저 첫 번째 경우와 두 번째 경우는 입력에서 무시해 줄 수 있습니다. 첫 번째 경우의 구간은 답에 상관이 없기 때문에 있던 답을 $2$ 배 해 주는 역할만 수행합니다. 두 번째 경우의 구간은 하나라도 존재하면 항상 모든 거주지가 나오니까, 두 번째 경우의 구간이 존재하지 않는 경우로 환원한 후, 두 번째 구간을 하나라도 뽑는 경우를 세어 주면 됩니다. 고로 모든 구간이 비지 않았고, 그렇다고 전체도 아닌, 경우를 가정합시다.

어떠한 구간도 원호를 한 바퀴 넘어가지 않는다고 하면, 다음과 같은 DP를 사용하여 해결할 수 있습니다. 모든 구간을 시작점 순으로 정렬한 후

$dp_{i, j} = (i$ 번 구간까지 고려했고, 현재 $[1, j]$ 구간을 다 덮었을 때 가능한 선택의 경우)

점화식을 써 보면, $dp_i$ 배열에 대한 구간 곱셈과 구간 합을 구하는 식으로 상태 전이를 할 수 있음을 알 수 있습니다. 고로 Segment tree로 $O(n \log n)$ 에 해결할 수 있습니다.

원호에서는 원을 한 바퀴 넘어가는 구간이 존재합니다. $a, 1$ 을 모두 포함하는 구간을 모두 모읍시다. 이 중 집합에 넣을 것이 없다면, 직선의 경우로 그대로 하면 됩니다. 그렇지 않다면, 집합에 넣을 것 중 가장 시작점이 오른쪽인 것, 여러 개라면 끝점이 가장 작은 것을 고릅시다. 평면 그래프의 성질을 사용하여, 어떠한 구간에 완전히 포함되는 (즉, $l < l^\prime \le r^\prime < r$ 을 만족하는 다른 구간 $[l^\prime, r^\prime]$) 구간은 존재하지 않음을 관찰할 수 있습니다. 고로, $a, 1$ 을 포함하며 집합에 넣을 수 있는 모든 다른 구간들은 정확히 해당 구간의 왼쪽에 존재하는 거주지를 새로 커버하거나, 오른쪽을 커버합니다. 고로 이들 역시 직선 상의 구간으로 환원되며 똑같은 DP를 사용하면 됩니다. 여기까지가 $O(n^2 \log n)$ 풀이입니다.

이 풀이를 최적화해 봅시다. 사실 구간의 개수를 최소화하는 식의 문제는 이런 방식을 최적화할 수 있지만, 여기서는 딱히 좋은 방법이 떠오르지 않습니다. 한 가지 알 수 있는 것은, 원호를 넘어가는 구간의 개수가 작다면 문제를 빠르게 풀 수 있습니다. 굳이 $a, 1$ 을 기준으로 돌릴 필요 없으니, 가장 원호가 덜 쌓인 곳을 기준으로 돌리는 전략을 생각해 볼 수 있습니다.

하지만 이 전략의 반례는 아주 쉽게 만들 수 있습니다. 구간이 $[1, a/2], [2, a/2+1], \ldots, [a/2+1, a], \ldots, [a, a/2-1]$ 같이만 들어와도 어떤 위치에서 돌려도 곤란해지기 때문입니다. 이 경우를 생각하는 것이 최적화의 핵심인데, 실제로 평면에 이 구간 집합이 나오도록 그림을 그려보면 그것이 불가능함을 알 수 있습니다. 두 겹치는 구간이 항상 새로운 정점을 만들어서, $a^2$ 개의 정점이 나오기 때문입니다. 두 겹치는 구간 $[l, r], [l^\prime, r^\prime]$ 이 $l< l^\prime, r < r^\prime$ 을 만족한다면, 첫번째 구간에서 $r$ 로 가는 경로와 두번째 구간에서 $l^\prime$ 으로 가는 경로는 만나게 되어 있으며, 두 구간이 만나는 시점에 다른 구간의 경로가 간섭할 수 없습니다. 이는 구간 사이의 교차가 많지 않음을 뜻합니다.

만약에 각 구간의 끝점이 다르다면, 어떠한 구간은 $m/n$ 개의 다른 구간과 겹치기 때문에, 이 구간의 어떠한 점에서도 최대 $m/n$ 개의 구간이 있어서, 해당 점을 기준으로 돌리면 문제가 해결됩니다. 문제가 되는 경우는 각 구간의 끝점이 같을 수 있는 경우입니다. 일단 이러한 충돌을 무시하고 위에서와 같이 겹치는 구간의 개수가 최소인 구간을 하나 고릅시다. 이 구간과 교차하는 구간은 적으나, 왼쪽 끝점이 같거나 오른쪽 끝점이 같은 구간이 여럿 있을 수 있습니다. 이러한 구간의 경우가 크게 4가지가 있을 수 있는데 (해당 구간보다 크고 / 작은 구간 중 왼쪽 / 오른쪽을 공유하는 경우), 왼쪽 / 오른쪽을 공유하는 경우가 동시에 많은 것은 불가능합니다 - 적어도 최소 둘 중 하나는 $\sqrt m$ 개 이하여야 합니다. (실제로 이보다 훨씬 더 작은 bound, 아마 $m/n$ 이 가능할 것 같으나 증명은 잘 모르겠습니다.) 이런 식으로 관찰해 보면, 겹치는 구간 의 개수를 최소화하지는 못해도 겹치는 구간 중 서로 다른 시작점 혹은 끝점 의 개수는 최소화할 수 있습니다. 이것을 최소화하는 것을 적절한 sweep line으로 해 주시면, 문제가 해결됩니다. 시간 복잡도는 $O(n \sqrt m \log n)$ 정도인데, 증명을 못 해서 그렇지 서사실은 $O(m \log n)$ 일 것이라고 생각합니다.

마지막으로, 위 세그트리를 사용한 DP가 느릴 수 있는데, 위에서 관찰한 구간의 단조성 때문에 그냥 부분합으로도 DP를 해결할 수 있어서, 이렇게 최적화하면 됩니다.

PA 2014. Drużyny

$dp[i] = $ ($1 \ldots i$ 번 학생이 팀을 이뤘을 때 최대 팀의 수와 그 경우의 수) 라고 정의하면 아주 쉬운 $O(N^2)$ 점화식을 유도할 수 있습니다. 이를 최적화 해 봅시다.

점화식에는 두 가지 조건이 있습니다.

• $B$ 의 최솟값이 구간의 길이 이상이어야 한다
• $A$ 의 최댓값이 구간의 길이 이하여야 한다

만약 첫 번째 조건만 있다면 문제를 $O(N \log N)$ 에 풀 수 있습니다. 어떠한 구간 $[i, j]$ 가 해당 조건을 만족한다면, $[i + 1, j], [i, j - 1]$ 구간도 해당 조건을 만족하기 때문입니다. $B$ 의 구간 최솟값을 구하는 세그먼트 트리를 사용한 후, 모든 $i$ 에 대해서 위 조건이 만족되는 최소 $j$ 를 two pointer로 구합시다. 구간 최솟값을 위에서 만든 세그먼트 트리로 구해주면 전체 과정이 $O(N \log N)$ 에 해결됩니다. 이러한 최소 $j$ 를 $f(i)$ 라고 할 경우, $[f(i) - 1, i - 1]$ 구간에 대한 DP 배열의 최댓값 (그리고 최댓값을 이루는 경우의 수) 를 또 다른 세그먼트 트리로 관리해 주면 전체 문제가 $O(N \log N)$ 에 해결됩니다.

두 번째 조건은 복잡합니다. 결국 위 DP를 해결하는 과정은 $DP[i] \leftarrow DP[j]$ 와 같은 전이를 반복하는 것입니다. 일반적으로는 단순히 이를 $(i, -j)$ 쌍을 사전순으로 열거하면서 계산하기 마련인데, 꼭 이렇게 계산할 필요는 없습니다. 정확히 여기서는, 구간 최댓값이 같은 $(i, j)$ 쌍에 대해서 한번에 DP를 전이해 주는 식의 방법을 사용할 것입니다.

다음과 같은 3가지 사실에 기반해서 문제를 효율적으로 해결합니다.

• 사실 1: 구간 $[i, j]$ 의 최댓값은 Cartesian Tree에서 $i$ 번 노드와 $j$ 번 노드의 구간 최댓값이다.
• 사실 2: DP 상태를 전이할 때 분할 정복의 요령으로, $[l, m]$ 구간에 있는 모든 쌍에 대해서 전이한 후, $[l, m] \times [m+1, r]$ 구간에 있는 모든 쌍에 대해서 전이하고, $[m+1, r]$ 구간에 있는 모든 쌍에 대해서 전이하는 방법을 택할 수 있다. (설명이 부족한데, https://koosaga.com/232 의 마지막 문제의 만점 풀이 부분을 참조하십시오).
• 사실 3: $T(n) = T(x) + T(n - x) + min(x, n - x)$ 일 경우, $T(n) = O(n \log n)$ 이다.

이제 분할 정복을 사용하여 문제를 해결합니다. 전체 구간 $[1, n]$ 에 대해서 상태 전이를 하는 함수를 생각해 봅시다. 이 구간에서 $A$의 최댓값이 나오는 지점을 $m$ 이라고 합시다. 이는 Segment tree를 사용해서 구할 수 있습니다. 이제 $m$ 을 기준으로 배열을 잘라서 다음과 같이 분할 정복을 합니다.

• 최댓값을 기준으로 왼쪽에 있는 원소들 쌍에 대해서 DP 상태 전이
• $[s - 1, m - 1] \rightarrow [m, e]$ 방향으로 DP 상태 전이
• 최댓값을 기준으로 오른쪽에 있는 원소들 쌍에 대해서 DP 상태 전이

(이 분할 정복은 Cartesian tree를 inorder로 타고 내려간다고 볼 수도 있습니다.)

첫 번째 과정과 세 번째 과정은 재귀적으로 잘 처리될 테니, 두 번째 과정을 잘 해결해 봅시다. 사실 3에 의해서, 두 번째 과정을 처리할 때 잘린 두 구간 중 작은 쪽의 구간에 비례하는 시간 복잡도에 전이를 완성하면 전체 문제를 $O(n \log n)$ 에 해결할 수 있습니다. 여기서는 (작은 구간 길이) $\times \log n$ 에 문제를 해결하여 전체 문제를 $O(n \log^2 n)$ 에 해결합니다.

두 가지 케이스를 따로 처리합니다. 첫 번째 케이스는 왼쪽 구간이 오른쪽 구간보다 긴 경우인데, 이 경우에는 각 오른쪽 원소에 대해서 취할 수 있는 왼쪽 원소가 $[s - 1, m - 1] \cap [f(i) - 1, i - A[m]]$ 과 같은 하나의 구간으로 나옵니다. 고로 위에서 말한 것처럼 세그먼트 트리를 사용하여 구간 최댓값과 최댓값 등장 수를 관리할 수 있습니다.

두 번째 케이스의 경우에는, 왼쪽 구간에서 오른쪽 구간으로 뿌려주는 식으로 비슷한 결과를 얻을 수 있습니다. 이 경우, 고정된 $j$에 대해서 $B$ 의 최댓값 조건이 만족되는 최대 $i$ 를 찾아야 하는데 이는 $f$ 배열이 있으면 간단히 전처리 할 수 있습니다. 이 전처리를 하면 취할 수 있는 오른쪽 원소가 구간의 형태로 나옵니다. 고로 해당 구간의 최댓값을 갱신해 주면 됩니다. 이 역시 세그먼트 트리로 관리할 수 있습니다.

여기서 곤란한 것은, 세그먼트 트리에 최댓값 갱신과 구간 최댓값을 같이 관리해야 한다는 점입니다. 이러한 세그먼트 트리를 구현할 수는 있지만, 상수가 매우 커져서 (10배 이상) 이렇게는 문제를 풀지 못합니다. 여기서 관찰해야 할 것은, 분할 정복의 첫 번째 과정을 거치면 $dp[0], \ldots, dp[m - 1]$ 까지의 원소는 값이 완전히 계산되며 더 이상 변하지 않는다는 것입니다 (분할 정복의 깊이가 어딘지와 상관 없이 참입니다). 고로 구간 최댓값을 찾는 세그먼트 트리에, 각 시점에서 변하지 않는 원소만 넣게 된다면 한번 들어간 원소가 다시 갱신될 필요는 없습니다. 이렇게 하면 구간 최댓값을 찾는 세그먼트 트리와, 구간 갱신을 하는 세그먼트 트리를 따로 둘 수 있으며, $dp[m]$ 을 계산하기 전까지에는 구간 갱신을 하는 세그먼트 트리에서만 $m$ 번 엔트리를 담당하고, 그 후에는 구간 최댓값을 찾는 세그먼트 트리에서만 $m$ 번 엔트리를 담당하게 하면 됩니다.

NERC 2019 C. Cactus Revenge

다음 경우를 예외 처리 합시다.

• 차수 합이 홀수면 당연히 답이 없습니다.
• 간선 개수가 $n-1$ 개 이상이어야 합니다. 상한도 있지만 지금은 고려하지 않습니다.
• 간선 개수가 $n - 1$ 개면 트리입니다. 트리에서는 항상 답이 존재함이 잘 알려져 있습니다. $n > 2$ 일 경우 리프와 리프가 아닌 노드를 임의로 이어주고, $n = 2$ 일 경우 두 노드를 이어주면 됩니다. 이후 풀이가 사이클을 중심으로 진행되기 때문에 트리 경우가 자연스럽게 처리되지 않습니다. 이 방법을 따로 구현해 줍시다. $O(n)$ 에 구현할 수 있습니다.

이제 $n \geq 3$ 을 가정할 수 있습니다.

그래프의 임의의 스패닝 트리에 속하지 않는 간선의 개수는 $c = (m - 2n + 2) / 2$ 입니다. 이 간선들은 모두 서로 다른 사이클에 속해 있습니다. 선인장 상의 한 단순 사이클은 스패닝 트리에 속하지 않은 간선을 정확히 하나만 사용합니다. 사이클의 길이가 3이고, 단순 사이클이 겹치지 않으니, $c \le \lfloor (n-1)/2 \rfloor$ 라는 상한을 하나 찾을 수 있습니다.

모든 정점의 차수가 짝수인 경우를 생각해 봅시다. 이 경우에는 그래프에 절선이 없고, 사이클의 합집합으로만 이루어져 있습니다. 이 때는 위 상한만 만족하면 다음 알고리즘으로 항상 선인장을 찾을 수 있습니다. $(n, c)$ 쌍에 대해서 다음과 같은 귀납적 알고리즘을 사용합니다.

• 만약 모든 정점의 차수가 2이면 ($c = 1$) 단순 사이클 하나로 묶어줌.
• 그렇지 않다면, 상한에 의해 차수가 2인 정점이 최소 2개 존재함을 보일 수 있으며, 차수가 4 이상인 정점이 존재. 차수가 2인 정점 2개와, 차수가 4 이상인 임의의 정점을 잇는 길이 3의 사이클을 만든 후, 차수가 2인 정점을 지우고 반복. 이 경우 $n$ 은 2 줄고 $c$ 는 1 줄며 귀납 조건은 계속 만족.

이 알고리즘은 $O(n)$ 에 구현할 수 있습니다.

이제 차수가 홀수인 경우를 생각해 봅시다. 홀수 차수가 존재하는 경우에는 그래프 상에 절선이 무조건 존재합니다. 모든 절선이 홀수 차수 정점에 인접한 것은 아니지만, 홀수 차수 정점은 항상 절선에 인접해 있습니다. 홀수 차수 정점의 수를 $O$ 라고 하고, 절선의 개수를 $B$ 라고 하면, 이로 인해 $2B \geq O$ 가 만족합니다. 절선 하나는 두 개의 홀수 차수 정점을 커버할 수 있기 때문입니다. 여기서 또 하나 신경써야 할 것은 차수 1인 정점 (리프) 인데, 절선 하나는 리프를 하나밖에 커버하지 못합니다. 고로 리프의 개수를 $L$ 이라고 하면 $B \geq max(O/2, L)$ 이 성립합니다. 절선은 사이클에 속하지 않으므로 $c \le \lfloor (n - 1 - max(O/2, L)) / 2 \rfloor$ 이라는 조금 더 강한 상한을 유도할 수 있습니다.

이제 이 상한만 만족하면 항상 선인장을 찾을 수 있음을 증명합니다. 케이스를 두 가지로 나눕니다.

• $O \ge 2L$: 홀수 차수 정점들을 두 개씩 짝지어 주는데, 리프 두 개가 짝이 되지 않도록 잘 매칭해 줍니다. 개수 조건 때문에 이런 매칭이 항상 가능합니다. 이제 홀수 차수 정점 $u, v$ 의 차수가 각각 $d_u, d_v$ 일 때, $d_u + d_v - 2$ 를 차수로 가지는 하나의 정점으로 이들을 묶어줍니다. 이 과정에서 홀수 차수 정점은 2개씩 줄고 $n$은 하나씩 줄어듭니다. 고로 $(n - 1, c - 1)$ 로 상태가 변하며 귀납 조건도 그대로 유지됩니다. 줄어든 그래프는 모든 차수가 짝수이니, 위 짝수 알고리즘을 사용하고, 다시 정점을 두 개로 분리하면 됩니다. 분리할 때, 짝수 차수에서 만든 사이클이 한 끝점을 $u$ 에, 한 끝점을 $v$ 에 가지지 않게 주의해서 분리해야 합니다 (이 경우 선인장이 아니게 됩니다).
• $O < 2L$: 리프 $2L - O$ 개를 제외하고, 위 방식대로 짝수 차수를 만들어 줍시다. 문제 조건에 따라서, 리프가 존재한다면, 항상 차수가 4 이상인 짝수 정점이 존재합니다. 이 정점에 리프 두 개를 매달아서 차수를 2씩 줄여주는 것을 반복할 수 있습니다. $(n - 2, c)$ 로 귀납이 반복됩니다. 귀납 조건도 유지됨을 확인할 수 있습니다. 이렇게 리프를 모두 제거한 후 짝수 알고리즘을 사용하고, 리프 2개를 붙여주는 것을 포함해서 정점을 분리하면 됩니다.

구현 디테일은 생략하지만 모두 $O(n)$ 에 구현할 수 있습니다.

Facebook Hacker Cup 2020 Finals C

왼쪽에서 오른쪽으로 읽으면서 높이의 최솟값이 갱신되는 지점을 기준으로 연못을 나눌 수 있습니다. 각 경우를 살펴보면 다음과 같습니다.

• 최솟값을 찍는 지점이 잠기지 않았다면, 1번 열을 제외하고 왼쪽으로 무조건 물이 흐릅니다.
• 최솟값을 찍는 지점 사이에는 골짜기 가 있습니다. 골짜기는 특정한 용량의 물을 모아주며, 넘칠 경우 왼쪽으로 물이 넘칩니다.
• 1번 열은 $D_1 < D_2$ 면 바로 잠기고, 그 외에는 오른쪽으로 무조건 물이 흐릅니다.

사실 최솟값을 찍는 지점도 용량이 0인 골짜기라고 생각해 주면 되기 때문에, 결국 1번 열을 제외하고 각 구간은 특정한 용량을 가진 물 저장고라고 볼 수 있습니다. 1번 열도 $D_1 < D_2$ 면 용량이 0인 골짜기이며, 그렇지 않다면 오른쪽 골짜기에 합쳐주면 됩니다.

결국 문제는 다음과 같이 변형됩니다.

• 서로 다른 넓이와 용량을 가진 골짜기들이 있다. 골짜기에서는 물이 넘치면 왼쪽으로 흐르게 된다. 1번 골짜기가 완전히 잠기기 전까지 떨어진 물방울의 기댓값은 얼마인가?

$C_1, C_2, \ldots, C_m$ 을 각 골짜기의 용량이라고 하고, $B_1, B_2, \ldots, B_m$ 을 각 골짜기에 떨어진 물의 양이라고 합시다. 이 때 떨어졌다는 것은 "맨 처음" 떨어졌음을 의미하고, 떨어진 이후 물이 넘쳐서 왼쪽으로 흐르는 동작을 고려하지 않은 양입니다.

만약 모든 점에 대해서 $C_i \ge B_i$ 를 만족한다면 물이 전혀 넘치지 않았으니 문제가 없습니다. $C_i < B_i$ 가 만족된다면 $B_i - C_i$ 만큼의 물이 왼쪽으로 넘치게 됩니다. 이것이 $C_1$ 에 도달할 때까지 해소가 되지 않으면 물이 넘쳤다는 뜻입니다. 물이 $i$ 번 점에서부터 넘쳐서 1번 점까지 계속 남는다는 것은 들어온 물 양의 합이 용량 합을 초과했다는 것입니다. 이러한 식으로 조건을 정리하면, 모든 $i$ 에 대해서 $\sum_{j \le i} B_j \le \sum_{j \le i} C_j$ 가 만족되면 물이 넘치지 않고, 하나라도 만족이 되지 않으면 물이 넘칩니다.

이 조건을 토대로 기댓값을 계산해 봅시다. 또 다른 관찰이 필요한데, 기댓값은 모든 $1 \le t$ 에 대해서 (시점 $t$ 까지 물이 넘치지 않을 확률) 의 합과 동일하다는 것입니다. 이 변환을 사용해서, $\sum B_i = t$ 인데, $\sum_{j \le i} B_j \le \sum_{j \le i} C_j$ 가 만족되는 확률을 계산합시다. 각 골짜기에 물이 떨어질 확률을 $p_1, p_2, \ldots, p_m$ 이라 두면,

$\frac{t!}{B_1! B_2! \ldots B_m!} p_1^{B_1} p_2^{B_2} \ldots p_m^{B_m}$

이라는 식을 유도할 수 있습니다. 이 식을 위 조건을 만족하는 모든 배열 $B$ 에 대해서 더해야 합니다. 여기서는 $\sum C_j$ 가 적다는 사실을 활용합시다. $dp[i][j] = (B_1 \ldots B_i$ 까지 채웠으며 그 합이 $j$ 인 확률) 이라고 하면

$dp[i][j] = \sum_{k = 0}^{min(C_i, j)}\frac{dp[i-1][j-k] (p_i)^k}{k!}$

라는 점화식을 세울 수 있고, 답은 $t! dp[m][t]$ 가 됩니다. 위 점화식은 상태가 $O(N^2D)$ 이며 각 항을 채우는 데 $O(ND)$ 의 시간이 드므로 $O(N^3 D^2)$ 정도의 시간에 계산할 수 있습니다. 입력이 작아 널널하게 통과합니다.

Facebook Hacker Cup 2020 Finals F

양의 정수 가중치를 가진 조각 $N$ 개가 있고, 각 조각이 겹칠 경우 간선을 이은 그래프에서 Maximum Weighted Clique를 찾는 문제입니다.

단순하게 문제를 해결하기 위해서는 간선이 있을 조건, 즉 두 조각이 겹칠 조건부터 알아야 하는데, 문제에서 조각을 주는 방식이 복잡하여 이것 조차도 쉽지 않습니다. 겹칠 조건은 쉽게 표현이 안 될 것 같으니, 하지 않을 조건을 생각해 봅시다. 두 아이가 친구를 하지 않았다면, 두 아이가 좋아하는 케익 영역은 겹치지 않습니다. 이 사이를 잘 잘라주면, 케익 상에서 한 아이가 좋아하는 영역과 다른 아이가 좋아하는 영역이 다른 조각으로 들어가게끔 할 수 있습니다. 이제 이 조건을 사용해서, 최대한 대칭적으로 성립하게끔 교차 조건을 만들어줍시다. 교차 조건이 대칭적이라는 것은, 두 개의 현을 고려할 때 굳이 방향성 을 고려하지 않아도 된다는 것입니다.

어떠한 아이가 좋아하는 조각이 $a - b, c - d$ 를 잇는 현으로 둘러싸였다고 합시다. $b - c - d - a$ 를 순서대로 잇는 호(circular arc)과, $d - a - b - c$ 를 순서대로 잇는 호를 그려봅시다. 이 경우, 두 조각이 겹치지 않을 경우, 서로 교집합이 없는 호가 하나 존재합니다. 좋아하는 케익 영역이 분리되도록 자른 후, 분리된 쪽을 바라보지 않는 호 두개를 고려하면 이 둘이 다른 조각에 완전히 들어가 있기 때문입니다. 만약 겹치지 않는 호가 두 개 있다면 이 조각을 기준으로 분리할 수도 있기 때문에, 이 조건은 필요 충분입니다. 이를 통해 다음과 같은 교차 판별 알고리즘을 제시할 수 있습니다:

• 어떠한 아이가 좋아하는 조각을 토대로 두 개의 호 (circular arc) 을 만듭니다.
• 가능한 4가지 호의 쌍 중, 3개가 교차할 경우 교차하지 않습니다. 4개가 교차할 경우 교차합니다.

이 방법에서 다음과 같은 Theorem을 유도하면, 이제 문제를 원호에 관한 문제로 완전히 변환해 줄 수 있습니다.

• Theorem. 각 아이 $i$ 에 대해서 위에서 나온 방식대로 가중치 $c_i$ 의 원호를 $2$ 개 만들자. $2n$ 개의 원호들을 정점으로 하고, 원호가 교집합이 존재할 때 간선을 이어주자. 이 그래프의 Weighted Maximum Clique에서 $\sum_{i = 1}^{n} c_i$ 를 빼면 최적해의 가중치가 된다.

• Proof. Weighted Maximum Clique의 가중치 합을 $W $ 라고 하고, 최적해의 가중치를 $A$ 라고 하자.

  • $W - \sum c_i \le A$: 클리크에서 호가 두 번 골라진 조각들을 모아서 최적해를 만들자. 이 조각들의 가중치 합은 최소 $W - \sum c_i$ 이며, 클리크이기 때문에 골라진 조각 쌍은 모두 서로 교차한다.

  • $W - \sum c_i \geq A$: 문제의 정답 집합을 $S$ 라고 하자. $S$ 에 포함된 조각은 호를 두 개 모두 골라주자. $i \notin S$ 에 대해서, 정답에 포함되지 않은 조각을 $i$ 라고 두자. 가정에 의해 최적해에는 이 조각과 겹치지 않는 조각 $j$ 가 존재한다. 조각 $i$ 와 조각 $j$ 에서 겹치지 않는 원호 쌍을 찾을 수 있다. 아무 $j$나 골라서 이 쌍에 들어가지 않은 조각을 골라주자. 이렇게 하면 $A + \sum c_i$ 가중치의 원호 집합을 찾을 수 있다. 이제 이것이 Clique임을 증명한다.

    만약 Clique가 아니라고 하면, 해당 원호 집합에서 겹치지 않는 두 원호 $a, b$ 를 찾을 수 있다. 가정에 의해 $a, b$ 가 모두 $S$ 에서 오지는 않았다. 일반성을 잃지 않고 $a$ 가 $S$ 에서 오지 않았다고 하자. 가정에 의해 $a$ 를 반대쪽으로 이은 원호 $a^R$ 에 대해서, 이 원호와 겹치지 않고, $S$ 에서 유래한 구간이 존재한다. 이 구간을 $c$ 라고 하자. $c$는 $a$ 의 부분집합이니, $c$ 역시 $b$ 랑 겹치지 않는다. 만약 $b$ 가 $S$ 에서 왔다고 하면, 여기서 바로 모순을 보일 수 있다. $S$ 에서 오지 않았다면, 위 과정을 다시 한번 함으로서 모순을 보일 수 있다.

이제 크기 $N$ 의 원호 구간 집합이 있을 때 이들의 Maximum Clique를 어떻게 찾아 줄 지 생각해 봅시다. Weight가 모두 1이라고 생각하면 이 풀이를 사용하면 됩니다. 지금 푸는 문제에서는 Weight가 존재하는데, Maximum Clique기 때문에 Weight가 있을 경우에는 Weight의 개수만큼 가중치 1의 구간을 만들어 준 후 위 문제를 그대로 풀 수 있습니다. 시간 복잡도가 문제인데, 그리디를 시뮬레이션할 때 자료 구조 안에 특정 위치의 빨간 점의 존재 여부 뿐만 아니라 그것의 개수까지 저장해 줍시다. 이 경우 빨간 점 여러개를 한번에 추가해 줄 수 있으며, 파란 점 여러개를 매칭해 줄 때 같은 위치의 빨간 점들을 빠르게 매칭해 줄 수 있습니다. 빨간 점을 매칭해 주는 과정이 amortization된다는 것을 감안하면 시간 복잡도는 여전히 같은 $O(n^2 \log n)$ 입니다.

Ptz Winter 2020 Day5 B. Binomial

홀짝 여부를 찾는 것이기 때문에, 이항 계수를 소수로 나눈 나머지를 구하는 Lucas Theorem을 사용할 수 있습니다. Lucas Theorem에 의하면, $\binom{n}{k}$ 가 홀수일 조건은, $n$ 과 $k$ 를 같은 길이의 수로 이진 전개 했을 때 $n$ 의 어떠한 자리수가 0이고 $k$ 의 어떠한 자리수가 1인 일이 없다는 것과 동일합니다. 이는 비트마스크로 두었을 때 $k$ 가 $n$ 의 서브마스크 (부분집합) 이라는 것과 동일합니다.

이제 문제는 각 수 $a_i$ 에 대해서 이 수의 서브마스크인 $a_j$ 를 빠르게 세는 것으로 환원됩니다. 여기서는 $a_i < 2^{20}$ 임을 활용해서, 각 $x$ 에 대해 이 수의 서브마스크를 빠르게 세는 접근을 활용합시다.

$dp[i][j]$ 를, 배열 $a$ 에서 $0 \ldots i - 1$ 번째 비트가 $j$ 의 서브마스크이고, $i \ldots 19$ 번째 비트는 $j$와 정확히 일치하는 원소 수라고 합시다. $i > 0$ 일 떄, $dp[i][j]$ 는 $j$ 의 $i-1$ 번째 비트가 0이면 $dp[i-1][j]$ 이고, 그렇지 않을 경우에는 $dp[i-1][j - 2^{i-1}] + dp[i-1][j]$ 라는 간단한 점화식이 성립합니다. 이 점화식을 사용하면 $dp[20][i]$ 에 우리가 원하는 값들이 모두 계산되게 됩니다. 고로 $O(20 \times 2^{20})$ 에 문제가 해결됩니다. 이러한 풀이 방법은 https://codeforces.com/blog/entry/45223 에서 더 공부해 볼 수 있습니다.