네 개의 무게 그룹 \(A\), \(B\), \(C\), \(D\) 가 있다. 각 그룹에는 정수로 적힌 무게들이 들어 있다 (음수, 양수, \(0\) 모두 가능하다).

당신은 각 그룹에서 정확히 하나씩 무게를 골라야 한다. 즉 \(A\) 에서 하나, \(B\) 에서 하나, \(C\) 에서 하나, \(D\) 에서 하나를 고른다. 고른 네 무게의 합이 정확히 \(0\) 이 되는 고르는 방법의 가짓수를 세는 것이 목표이다.

서로 다른 그룹의 같은 값이라도 다른 원소로 취급하며, 한 그룹 안에서도 위치(인덱스)가 다르면 서로 다른 선택으로 센다. 다시 말해 값이 같은 무게가 여러 개 있으면 각각을 따로 센다.

예를 들어 네 그룹이 모두 \(\{0, 0\}\) 이라면 각 그룹에서 두 가지로 고를 수 있으므로 합이 \(0\) 인 조합은 \(2^4 = 16\) 가지이다.

각 그룹의 크기는 최대 수백 개이므로 네 그룹을 모두 직접 곱하는 \(O(n^4)\) 완전탐색은 너무 느리다. 앞의 두 그룹에서 만들 수 있는 두 무게의 합을 모두 모아 두고, 뒤의 두 그룹에서 만든 합의 음수를 조회하는 중간에서 만나기(meet in the middle) 로 \(O(n^2)\) 에 해결할 수 있다.

\(1 \le n_A, n_B, n_C, n_D \le 800\)

각 무게는 \(-10^9 \le w \le 10^9\) 인 정수이다.

정답은 \(64\)비트 정수 범위에 들어간다.

첫째 줄에 네 그룹의 크기 \(n_A\), \(n_B\), \(n_C\), \(n_D\) 가 공백으로 구분되어 주어진다 (\(1 \le n_A, n_B, n_C, n_D \le 800\)).

둘째 줄에는 그룹 \(A\) 의 무게 \(n_A\) 개가, 셋째 줄에는 그룹 \(B\) 의 무게 \(n_B\) 개가, 넷째 줄에는 그룹 \(C\) 의 무게 \(n_C\) 개가, 다섯째 줄에는 그룹 \(D\) 의 무게 \(n_D\) 개가 공백으로 구분되어 주어진다.

모든 무게는 \(-10^9\) 이상 \(10^9\) 이하의 정수이다.

각 그룹에서 하나씩 골라 네 무게의 합이 정확히 \(0\) 이 되는 고르는 방법의 수를 한 줄에 출력한다. 이 값은 매우 클 수 있다.

riseoj 작성

출처 Original