[ABC267 Ex] Odd Sum

비정기적으로 ABC의 Ex 난이도에 해당하는 문제를 하나씩 풀고 포스팅해 볼 것이다. 고난이도 문제에서 교육적인 컨셉이나 개념을 얻어가서 공부 좀 해보자는데 의의를 두려고 한다.

---

https://atcoder.jp/contests/abc267/tasks/abc267_h

kenkoooo 레이팅: 2422 (오렌지지만, Ex 중에서는 가장 쉬운 편에 속하는 문제이다.)

체감 난이도: D5 ~ D4

Tag: FFT, Divide and Conquer

---

$N$개의 원소로 이루어진 수열 $A$가 주어진다. 이 수열에서 홀수 개의 원소를 골라, 그 합이 $M$이 되게 하는 경우의 수를 구하는 문제이다. $N$이 $100\ 000$으로 작지 않지만, $A$가 $10$밖에 되지 않는다는 점이 특이하다.

---

다항식을 이용해서 문제를 해결한다. $k$차 항의 계수를 합이 $k$가 되도록 원소를 뽑는 경우의 수라고 하자.

어떤 원소 $a$를 뽑는 것은 다항식에 $x^a$를 곱하는 것과 같고, 뽑지 않는 것은 다항식에 $1$을 곱하는 것과 같다. 따라서 $A$에서 원소를 선택해서 만들 수 있는 모든 합을 $\prod_{i=1}^N (x^{A_i} + 1)$의 계수로 나타낼 수 있다.

 

홀수 개의 원소를 사용해야 한다는 조건을 식에 녹여보자. 내가 푼 방식을 먼저 설명하고, 그다음 정해의 논리를 설명한다.

원소 $k$가 $A$에서 등장하는 횟수를 $S_k$라 하자. 그러면 $k$만을 골라서 만들 수 있는 합은 $(x^k + 1)^{S_k}$와 같이 나타낼 수 있다. 여기서 $k$를 짝수 개 사용하는 경우의 수는 다항식의 $x^0$, $x^{2k}$, $\cdots$ 계수에 해당하고 홀수 개 사용하는 경우의 수는 다항식의 $x^k$, $x^{3k}$, $\cdots$ 계수에 해당한다. 따라서 특정 원소를 짝수 개 사용하는 경우의 수와 홀수 개 사용하는 경우의 수를 분리해 줄 수 있다. 

 

이제 어떤 원소를 짝수 개 사용하고, 홀수 개 사용할 것인지를 정해준다. 짝수의 사용은 합의 Parity를 변화시키지 않으므로, $M$의 Parity와 사용한 홀수 원소 개수의 Parity는 동일하다. 따라서 오직 짝수 원소에 대해서만 그 수를 몇 개 사용할지를 정해주면 된다. 제한에서 짝수의 개수는 $5$개이므로, 홀짝을 정해주는 경우의 수는 $2^5 / 2 = 16$ 가지이다. 각 수마다 홀수 사용하는 경우랑 짝수 사용하는 경우를 각각 구한 뒤, FFT를 이용해 신나게 곱해주면 $O(2^4MlogM)$ 에 문제를 해결할 수 있다.

 

https://atcoder.jp/contests/abc267/submissions/47423326

---

정해는 Parity가 다른 두 값을 합치면 홀수가 되고, Parity가 같은 두 값을 합치면 짝수가 된다는 점을 이용한다.

분할 정복을 한다. 배열 $A$를 절반으로 가르고, 각 절반마다 홀수 개 사용하는 경우의 수랑 짝수 개 사용하는 경우의 수를 각각 계산한 뒤 FFT를 이용해 합친다. 모든 원소는 $O(logN)$번 합쳐지기 때문에 시간복잡도는 $O(MlogMlogN)$ 이다.

 

https://atcoder.jp/contests/abc267/submissions/47514410