가환 제곱근

$P$의 사이클 분해를 생각하자. $A_i^2=P$이면 $A_iP=PA_i$이므로, 모든 $A_i$는 $P$와 교환한다. 따라서 $A_i$는 $P$의 사이클을 같은 길이의 사이클로만 보낸다. 그러므로 사이클 길이별로 독립적으로 세고 곱하면 된다.

길이 $d$인 $P$-사이클의 개수를 $m$이라 하자. $K$개의 순열 $A_i$가 유도하는 사이클들 사이의 작용은 $\mathbb F_2^K$의 작용으로 볼 수 있다. 하나의 연결 성분에 포함되는 $P$-사이클의 개수는 항상 $2^r$ 꼴이다.

크기 $2^r$인 성분 하나를 고정된 $2^r$개의 사이클 위에 만드는 경우의 수를 $c_{d,r}$라 하자. 그러면 다음 식이 성립한다.

$d$가 홀수이면

$$c_{d,r} = {K \brack r}_2 (2^r-1)! d^{2^r-1}.$$

$d$가 짝수이면 $r=0$은 불가능하고, $r \ge 1$에 대해

$$c_{d,r} = {K-1 \brack r-1}_2 2^{K-r} (2^r-1)! d^{2^r-1}.$$

여기서

$${n \brack r}_2 = \prod_{i=0}^{r-1} \frac{2^{n-i}-1}{2^{r-i}-1}$$

는 이진 Gaussian binomial coefficient이다. 이 문제에서는 $r \le \log_2 N$이므로 $K$가 매우 커도 빠르게 계산할 수 있다.

이제 $F[n]$을 길이 $d$인 사이클 $n$개를 처리하는 경우의 수라고 하자. 첫 번째 사이클이 속한 성분의 크기가 $2^r$이면 나머지 $n-1$개 중 $2^r-1$개를 고르면 된다. 따라서

$$F[0]=1,$$ $$F[n] = \sum_{2^r \le n} \binom{n-1}{2^r-1} c_{d,r} F[n-2^r].$$

모든 $d$에 대해 이 DP 값을 곱하면 정답이다. 전체 시간복잡도는 $O(N\log N)$이다.