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