BOJ - 자연수로 만드는 자연수

• https://www.acmicpc.net/problem/30097

Idea

• 냅색을 쓰면 자명한 $O(N^2)$ dp로 문제를 풀 수가 있다.

• 0-1 냅색은 사실 생성 함수이다. $\prod_{K \nmid i}(1 + x^{i})$의 $x^{N}$의 계수가 합이 $N$인 집합 $S$의 개수이다.

• 이렇게만 되면 참 좋으려만, $S$의 크기가 짝수여야 한다는 조건이 걸린다.

  • 여기서 엄청난 관찰이 있는데, $a+b$와 $a-b$를 알면 $a, b$ 각각을 알 수 있다는 아이디어이다.
  • 크기가 짝수/홀수인 집합 $S$의 개수를 $a, b$라 두자. $a+b$는 쉽게 알 수 있다.
  • $a-b$는? 놀랍게도 $\prod_{K \nmid i}(1 - x^{i})$의 $N$차항의 계수이다!

• 이제 저 다항식을 계산하기만 하면 된다.

• 여기서 미친 관찰 하나 더

  • 냅색은 롤백이 가능하다!!
  • $new(x) = old(x) + old(x-w)$에서, $old(x) = new(x) - old(x-w)$임을 알 수 있다.
  • 또한 냅색과 역-냅색은 결합법칙이 성립한다. (ibm2006님의 설명)
  • 따라서 위 iteration을 그대로 포문으로 처리해주기만 하면 냅색의 역연산을 수행할 수 있다..

• 생성함수적으로는 이렇게 생각할 수 있다.

  • $\prod_{i}^{\infty} {(1+x^{i})}/ \prod_j^\infty{(1+x^{kj})}$의 $N$번째 계수를 구해야만 한다.
  • 분자는 그냥 냅색을 돌리면 알 수 있다.
  • $(1+x)^{-1}$은 $1-x+x^{2}-x^{3}+\dots$와 같다.
  • 이런 역연산들은 미리 곱해두어 역-냅색들의 누적을 통해 전처리해둘 수 있다. 이를테면 $(1+x^{5})^{-1}$의 $k$번째 항은 $(1+x)^{-1}$의 $\frac{k}{5}$번째 항과 같기 때문이다.

• 결국 냅색 다항식과 역-냅색 다항식을 곱하여 $N$번째 항 만을 얻어내면 되고, 이는 쿼리당 $O(N)$에 처리할 수 있다.

Takeaway

• 느낀 점, 교훈
  • 그냥 너무 신기하다.
  • 냅색을 다항식 곱셈의 관점에서 바라볼 수 있다.
  • 또한 냅색에서 물건을 제거하는 것을 역 다항식을 곱하는 것으로 생각할 수 있고, 이는 냅색과 아주 유사한 과정을 통해 처리해줄 수 있다. (for문 순서 주의)

Notes

• https://u.acmicpc.net/030e5df6-a8d3-43b0-91c8-8ecc1cf36342/2023%2BGSHS%2BCS%2BSeminar_editorial.pdf