Yet Another Tree Problem 3

허용되는 자식 수의 집합을 $A$라 하고

$$\Phi(x)=\sum_{a\in A}\frac{x^a}{a!}$$

라고 두자. 라벨이 붙은 루트 트리의 지수 생성함수 $T(x)$는

$$T(x)=x\Phi(T(x))$$

를 만족한다.

정점 $1$이 루트로 고정되어 있으므로, 크기 $n$의 답은

$$(n-1)![x^n]T(x)$$

이다.

따라서 $T(x)=x\Phi(T(x))$를 $x^{N+1}$까지 구하면 된다. 뉴턴 반복을 사용하면 현재 근사값 $T$에 대해

$$T \leftarrow T-\frac{T-x\Phi(T)}{1-x\Phi'(T)}$$

로 정확도를 두 배씩 늘릴 수 있다. 다항식 역원과 곱셈은 NTT로 계산한다.

$\deg \Phi \leq 1000$이므로 $\Phi(T)$의 합성은 baby-step giant-step으로 처리한다. 블록 크기 $B$를 잡고 $\Phi(x)=\sum_j x^{jB}Q_j(x)$로 나누면, $T^0,T^1,\cdots,T^{B-1}$와 $(T^B)^j$들을 이용해 합성을 빠르게 계산할 수 있다.

전체 시간 복잡도는 $O(N\log^2 N)$이다.

Solution written by GPT5.5