Crush

이미 공개된 정보만으로 확정된 서로 좋아하는 쌍의 수를 $\mathrm{fixed}$라 하자. 아직 짝사랑 상대가 공개되지 않은 학생 수를 $m$이라 하자.

공개되지 않은 학생 $u$에 대해, 이미 공개된 학생 중 $u$를 좋아한다고 알려진 학생 수를 $d_u$라 하자. $u$가 이들 중 한 명을 고르면 새로운 서로 좋아하는 쌍이 하나 생긴다. 또한 공개되지 않은 두 학생 $u,v$가 서로를 고르는 경우에도 새로운 서로 좋아하는 쌍이 하나 생긴다.

가능한 추가 이벤트는 다음 두 종류이다.

• 공개되지 않은 학생 $u$가 자신을 좋아한다고 이미 공개된 학생 중 한 명을 고르는 경우. 이 이벤트의 가중치는 $d_u$이고, 공개되지 않은 학생 하나를 사용한다.
• 공개되지 않은 두 학생 $u,v$가 서로를 고르는 경우. 이 이벤트의 가중치는 $1$이고, 공개되지 않은 학생 둘을 사용한다.

정확히 $k$개의 이벤트를 직접 세는 대신, factorial moment를 먼저 구한 뒤 이항 반전을 적용한다. 한 학생의 가능한 선택 수는 $R=N-1$이다.

$d_u$들의 elementary symmetric polynomial을

$$\prod_u(1+d_u x)=\sum_s e_s x^s$$

라 하자. 이를 빠른 다항식 곱셈으로 구한다. 이후 문제는 사용한 단일 이벤트 수와 쌍 이벤트 수를 합쳐 세는 형태가 되며, 필요한 합은 Fibonacci형 변환

$$Z_n=\sum_{u=0}^{n}\binom{n}{u}A_{n+u}$$

으로 정리된다. 이 변환은 $t^2=z(t+1)$ 관계를 이용하여 분할정복과 NTT로 계산할 수 있다.

추가 이벤트 수에 대한 factorial moment를 $g_q$라 하면, 정확히 $k$개의 추가 서로 좋아하는 쌍을 만드는 경우의 수 $f_k$는 다음 이항 반전으로 얻는다.

$$f_k=\sum_{q\geq k}(-1)^{q-k}\binom{q}{k}g_q.$$

마지막으로 이미 확정된 쌍의 수 $\mathrm{fixed}$만큼 답을 오른쪽으로 밀면 된다. 전체 시간복잡도는 각 테스트 케이스에 대해 $O(m\log^2 m)$ 수준이다.

Solution written by GPT5.5