求める数を$a_n$とする。長さ$n$の順列を先頭$k$要素が$1, 2, ..., k$の順列であるような最小の$k$で分類して数えると、それぞれ$a_k(n-k)!$通りある。長さ$n$の順列から長さ$n+1$の順列を作ることを考えると、$n+1$は$k$箇所に挿入可能なので$a_{n+1} =\sum_{k=1}^{n}ka_k(n-k)! = \sum_{k=0}^nka_k(n-k)!$。$a_0=0, a_1=1$としてオンラインFFTすると${O}(N \log^2 N)$で解ける。
