頂点 \(i\) から頂点 \(p_i\) に辺を張った \(N\) 頂点有向グラフを考えると、サイクル複数個からなるグラフになります。ここで、\(p_{p_i} \neq i\) という条件は長さ \(1,2\) のサイクルが存在しないことと同値です。

よって、そのようなグラフを数え上げることとします。ここで、突然ですがそのような \(n\) 頂点グラフのうち連結であるものの個数を考えましょう。これは簡単で、\(n \le 2\) なら \(0\)、\(n \ge 3\) なら \((n-1)!\) です。ここで、次のような連結性を exp/log を用いて扱うテクニックが存在します。

条件 $A$ を満たす連結グラフの個数の指数型母関数 $f(x)$ と、全ての連結成分が条件 $A$ を満たすグラフの個数の指数型母関数 $g(x)$ について、$g(x) = \exp(f(x))$

(ただし、$f(x)$ の定数項は空グラフを認めず $0$、$g(x)$ の定数項は空グラフを認めて $1$ とします。)

証明は https://maspypy.com/%E3%82%B0%E3%83%A9%E3%83%95%E6%95%B0%E3%81%88%E4%B8%8A%E3%81%92#toc4 などをお読みください。

この問題において条件 \(A\) とはサイクルであり、かつ長さが \(3\) 以上であることです。この時、答えは \(N! [x^N] g(x)\) です。\(f(x) = \sum_{n \ge 3} \frac{(n-1)!x^n}{n!} = \sum_{n \ge 3} \frac{x^n}{n}\) なのであとは FPS の exp を計算すればよいです。計算量は \(\mathrm{O}(N \log N)\) です。