FPS24 K - 順列

考え方

包除原理より、「いくつかの数を指定して、それらで違反しているパターン数を足し引き」で求まる。
具体的には、$1$ 以上 $N-1$ 以下の指定 $2^{N-1}$ パターンに対して、偶数個なら足して、奇数個なら引く。
足し引きする値は、各区間の長さの階乗。
最後の $N$ は強制的に条件違反とみなして、求めればよい。

ということで、 $1$ つの区間の母関数は以下。
$$
A(x) = x+2x^2+6x^3+24x^4+\dots
$$

これを任意の区間数で合計 $N$ 個になればよい。
最終区間も含めた区間数の偶奇も考えて、全体の母関数は以下。
$$
A(x)-\{A(x)\}^2+\{A(x)\}^3-\{A(x)\}^4+\dots = \dfrac{A(x)}{1+A(x)} = 1-\dfrac{1}{1+A(x)}
$$

これを逆数の級数展開にして、$x^N$ の係数を求めればよい。
具体的な求め方は「形式的冪級数」の記事参照。
計算量は $O(N\log N)$ である。

入力例1での動作

入力を受け取る。

n: 3

$3$ 次まで考えると、$1+A(x)$ は以下になる。
$$
1+A(x)=1+x+2x^2+6x^3
$$

この逆数を $x^3$ まで求めると、以下になる。
$$
\dfrac{1}{1+A(x)}
=1-x-x^2-3x^3+O(x^4)
$$

したがって、次の式になる。
$$
1-\dfrac{1}{1+A(x)}
=x+x^2+3x^3+O(x^4)
$$

$x^3$ の係数は $3$ なので、答えは $3$ となる。

注意点

形式的冪級数の逆数を求めるには定数項が $0$ でない必要がある。
今回は $1+A(x)$ の定数項が $1$ なので、この条件を満たす。
逆数計算で必要な逆元は繰り返し二乗法で求める。

別解

特になし。