まず、グラフの連結という条件を無くした問題を考えます。

\(A_i \neq 0\)であるようなiについて、\(i \rightarrow A_i\)という辺を張った有向グラフ\(H\)を考えます(この有向グラフ\(H\)を数えれば良いです)。

\(H\)の連結成分の再帰的定義を考えます。

頂点番号が最大の頂点との間の辺は全てその頂点に向かっているので、連結成分としてありうる成分をいくつか集めて、そこに最大ラベルとなる頂点を追加して辺を追加したり削除したりして新しく連結成分を作るという再帰的定義が考えられます。

ゆえに、連結成分1個の個数の、頂点数をパラメータとした指数型母関数を\(f\)とすると、

\(f=\int \exp(2f-x) dx\)

が成り立ちます(\(1\)頂点の連結成分の場合、その連結成分の最大ラベルの頂点の行き先は存在しないためそこだけ係数は\(1\)、他の場合は\(2\)通りあるので係数は\(2\)で、\([x^1]f=1\)であることに注意し、\(2f-x\)をexpすれば良いです)。この方程式を満たす\(f\)は、relaxed expを使って\(O(N \log^2 N)\)時間で\(N\)項目まで求めることができますし、微分方程式を解くことにより、\(O(N \log N)\)時間で計算できる形になります\((f=-\frac{1}{2} \log(2\exp(-x)-1))\)。

\(\exp(f)\)が連結という条件を無くした時の答えの指数型母関数です。

ここで、連結という条件を追加した場合を考えます。

まず、\(N>1\)より、明らかに\(1\)頂点の連結成分は存在し得ないです。

また、\(H\)において異なる\(2\)つの連結成分の頂点のラベルの集合が、交差しない時その\(2\)つの連結成分に含まれる頂点に対応する頂点の間に辺を張ることはできないです。よって、頂点ラベルの連結成分ごとの割り振りが分割できないようなラベルの割り振りが行われているものの個数が求める個数です。 だから、答えの通常型母関数を\(g\)とすると、\(\exp(f-x)\)に対応する通常型母関数を\(h\)として、

\(h-1=\displaystyle\frac{g}{1-g}\)

が成り立ちます。明らかに、全体\(O(N \log N)\)時間で答えが計算できます。