[ABC309Ex] Simple Path Counting Problem

문제: https://atcoder.jp/contests/abc309/tasks/abc309_h

 

풀이:

$O(NM)$ 에 문제를 해결하는 것은 쉽습니다. $D_{r, c}$ 를 $A_1, \cdots, A_K$에서 출발해서 $(r, c)$로 도달하는 경우라고 합시다. 답은 $D_{N, B_1} + \cdots + D_{N, B_L}$입니다.

• $D_{1, c}$ 는 $A_i$에서 $c$가 등장하는 횟수입니다. $(1 \le c \le M)$
• $D_{r, c} = D_{r-1, c-1} + D_{r-1, c} + D_{r-1, c+1}$입니다. $(1 \le c \le M)$
  • 단, $D_{r, 0}$ 와 $D_{r, M+1}$ 은 항상 $0$으로 가정합니다.

이제 이를 다항식 형태로 바꿔봅시다. $D_r$과 관련된 생성함수 $f_{D_r}$ 은, $f_{D_{r-1}} \times \left(x + 1 + x^{-1}\right)$로 만들어지며, 계산 이후 $0$차항과 $M+1$차항을 제거해줘야합니다.

 

이 $0$차항과 $M+1$차항을 제거하는 연산은 다항식으로 표현하기 힘들기 때문에, 영상법(映像法, ja:鏡像法, en:method of images)를 사용합시다. $(*, M+1)$과 $(*, 0)$에 거울을 둔 이후, 거울에서 만난 것을 모두 소거해버리는 방법입니다.

거울에서 만난 것을 소거하려면, $D_{*, 0}$ 의 값의 음수를 항상 추적하고 있어야합니다. $D_{i, c}$의 "거울"을 $D_{i, -c}$에 놓는 것으로 문제를 해결할 수 있습니다. 구체적으로는 다음과 같습니다.

• $D_{1, -c} = -D_{1, c}$ $(1 \le c \le M)$
  • 거울상을 만들어서, 거울인 $D_{1, 0}$에서 만나는 것을 상쇄되게 만듭시다.

그럼, $D_{r, 0}$을 계산할 때 강제로 $0$으로 만들어 줄 필요가 없이 $D_{r, 0} = D_{r-1, -1} + D_{r-1, 0} + D_{r-1, +1}$ 이 되어서, $D_{r-1, -1}, D_{r-1, +1}$이 상쇄되어 $0$이 됩니다.

 

이를 $M+1$쪽에서도 해 주면 최종 DP식은 다음과 같습니다.

• 길이 $2M+2$인 행의 끝이 서로 이어져있다고 생각합시다. 즉, $D_{r, c} = D_{r, 2M+2 + c}$ 입니다.
• $D_{1, c}$는 $A_i$에서 $c$가 등장하는 횟수입니다. $(1 \le c \le M)$
• $D_{1, -c} = -D_{1, c}$ $(1 \le c \le M)$
• $D_{1, 0} = D_{1, M+1} = 0$
• $D_{r, c} = D_{r, c-1} + D_{r, c} + D_{r, c+1}$ $(0 \le c < 2M+2)$

위 DP식에서, $D_{r,0}$과 $D_{r, M+1}$은 상쇄되어서 항상 $0$이 되게 됩니다.

이제, 이를 다항식 형태로 바꿔봅시다. $f_{D_{r-1}} \times \left(x + 1 + x^{-1}\right) \pmod{x^{2M+2}}$가 됩니다. 이는 다항식 곱셈으로 쉽게 계산할 수 있으며, 구체적으로는 $f_{D_N} = f_{D_1} \left(x+1+x^{2M+1}\right)^{N-1} \pmod {x^{2M+2}}$와 같이 계산할 수 있습니다. 이는 $\mathcal{O}(M \log M)$ 혹은 $\mathcal{O}(M \log M \log N)$ 시간에 계산할 수 있습니다.

 

코드: https://atcoder.jp/contests/abc309/submissions/43404960