問題文だと頂点 \(i\) から出る辺の行き先が \(x_i\) になっていますが，\(x\) が変数かぶりしたので \(p_i\) で書くことにします． また，頂点は \(0\)-indexed とします．

\(N\) を固定します． \(i<x_i\) なる \(i\) の個数 \(K\)，連結成分数 \(C\) に対する答えを \(f_{N,K,C}\) とし，\(2\) 変数多項式 \(f_N(x,y)=\sum_{K,C} f_{N,K,C} \ x^K y^C\) を定義します．

結論から述べると，\(f_N(x,y)\) は以下の閉じた式で書くことができます．

\(f_N(x,y)=\sum_{0 \leq k \leq N-1} C(N-1,k) (\prod_{0 \leq i<k} ((N-i)x+i)) (\prod_{0 \leq i<N-k} (i+y))\)

なお，\(C(a,b)\) は \(a\) choose \(b\) を表します． 各 \(k\) ごとに \([x^K]\prod_{0 \leq i<k} ((N-i)x+i)\) および \([y^C]\prod_{0 \leq i<N-k} (i+y)\) を求められればよいです． これは分割統治+FFTで計算でき，計算量は全体で \(O(N \log^2N)\) になります．

以下，\(f_N(x,y)\) の閉じた式の証明を行います．

まず \(C=1\) のときの答え \(g_N(x)=[y^1]f_N(x,y)\) を求めることにします． 答えは

\(g_N(x)=\sum_{0 \leq k \leq N-1} (N-1)!/k! (\prod_{0 \leq i<k} ((N-i)x+i))\)

になります．

\(g_N(x)\) の式の証明: 上の式は，以下のオブジェクトを数えていると解釈できます．

• \(N\) 頂点のグラフを用意し，ある \(k\) を特殊頂点として固定する． \(k\) 以外の頂点からは \(1\) 本ずつ辺を伸ばす． 頂点 \(i\) (\(i<k\)) については，そこから出る辺を自由に選べる． 頂点 \(i\) (\(i>k\)) については，自分より小さな番号の頂点に辺を伸ばす． このグラフの \(K\)-value を \(i \leq p_i\) を満たす \(i\) の個数と定義する．(\(i=p_i\) を含むことに注意)

ある \(k\) に対応するオブジェクトの集合を \(A_k\) とおきます． \(A_k\) は以下の集合 \(B_k\) と一対一対応します．

• connected functional graph であって，以下の”いずれかの”条件を満たす頂点 \(i\) の番号の最大値が \(k\) のもの．

  • (i) \(i\) がサイクルに含まれる
  • (ii) \(i<p_i\)

なお，\(k\) がこれらの条件を同時に満たすことがないことが確認できます． このグラフの \(K\)-value を \(i <p_i\) を満たす \(i\) の個数とします．(今度は \(i=p_i\) を含まない)

\(A_k\) と \(B_k\) の間に一対一対応，つまり全単射が存在しますが，特に \(K\)-value を保つような全単射が存在します．

全単射の詳細

$A_k$ 内のグラフを一つ取り，$G$ とおきます． $G$ のサイクルを $S_1,S_2,\cdots,S_l$ とします． 各サイクル $S_i$ は，番号最小の頂点が末尾にくるようにサイクルの頂点番号を並べた列だとします． さらに，末尾の頂点番号の昇順でサイクルの順番を決めることにします． 列 $Z$ を $Z=S_1+S_2+\cdots+S_l$ と定義し，$Z=(Z_1,Z_2,\cdots,Z_m)$ と表すことにします．
まず，サイクル内の辺をすべて削除します． $Z$ 内に $k < Z_i$ となる頂点 $Z_i$ が存在する場合としない場合で場合分けします．
(i) 存在しない場合: 列 $Z'=Z+(k)$ をサイクルとしてつなぎなおします． こうして得られるグラフは，集合 $B_k$ の case (i) のグラフに対応します．
(ii) 存在する場合: $k< Z_i$ を満たす最小の $i$ を $c$ とおき，$L=(Z_1,\cdots,Z_{c-1})$, $R=(Z_{c},\cdots,Z_m)$ とおきます． $L$ の先頭，$L$ の末尾，$R$ の末尾をそれぞれ $x,y,z$ とおきます． まず，$k \to R_1 \to R_2 \to \cdots \to z$ と辺を張ります． さらに以下に示すように辺を張ることで，$B_k$ の case (ii) のグラフを得ることができます．
(ii-1) $z<\min(x,y)$ or $\max(x,y)< z$ のとき． $z \to x \to L_2 \to \cdots \to y \to z$ とサイクルを作ります．
(ii-2) $y< z< x$ のとき． $z < L_i$ を満たす最大の $i$ を $d$ とおきます． そして，$x \to L_2 \to \cdots \to L_d \to z \to L_{d+1} \to \cdots \to y \to x$ とサイクルを作ります．
(ii-3) $x< z< y$ のとき． $z > L_i$ を満たす最大の $i$ を $d$ とおきます． そして，$x \to L_2 \to \cdots \to L_d \to z \to L_{d+1} \to \cdots \to y \to x$ とサイクルを作ります．
以上の操作によって $K$-value が保たれていることと，および逆操作が可能であることは，丁寧に議論すると確認できます．

一般の \(C\) について解きます．

ここで唐突ですが，以下の条件を満たす根付き木を考えます．

• 頂点数 \(N\)
• 根は \(k\)
• 頂点 \(i>k\) の親は \(i-1\)

この木の \(K\)-value を \(i<p_i\) を満たす \(i\) の個数とします． すべての根付き木に対して \(x^K\) をかけて足し合わせた多項式を \(T_k(x)\) とおき，これを求める問題を考えます．

結論として，\(T_k(x)\) は以下の式で計算できます．

\(T_k(x)=(\prod_{0 \leq i<k} ((N-i)x+i)) \times (N-k) / N\)

証明： \(T_k(x) \times N =(\prod_{0 \leq i<k} ((N-i)x+i)) \times (N-k) \) を示します． つまり，（根付き木をとり，更に \(1\) 頂点に印をつけたもの）と右辺で数えられる”なにか”との間の全単射を作ります． “なにか”とは，以下の条件を満たす functional graph (ただし \(k\) だけ出次数\(0\))の集合です．

• \(k \leq i < N\) を満たす \(i\) を一つ選び，頂点 \(w\) と呼ぶことにする．
• 頂点 \(k\) からは辺を伸ばさない．
• 頂点 \(i\) (\(i>k\)) の行き先は \(i-1\)
• 頂点 \(i\) (\(i<k\)) の行き先 \(p_i\) は自由に選べる．
• このグラフの \(k\)-value を \(i \leq p_i\) を満たす \(i\) の個数とする．(\(i=p_i\) を含むことに注意)
• このグラフが連結とは限らないことに注意せよ．

今，上の条件を満たすグラフ \(G\) があったとします． \(G\) は，\(k\) を根とする木と functional graph が並んだ形をしています． functional graph のサイクルを \(S_1,S_2,\cdots,S_l\) とします． 各サイクル \(S_i\) は，番号最小の頂点が末尾にくるようにサイクルの頂点番号を並べた列だとします． さらに，末尾の頂点番号の昇順でサイクルの順番を決めることにします． 列 \(Z\) を \(Z=S_1+S_2+\cdots+S_l\) と定義し，\(Z=(Z_1,Z_2,\cdots,Z_m)\) と表すことにします．

\(G\) を変形して，\(T_k(x) \times N\) の要素へ対応させます． まず，サイクル内の辺をすべて削除します． 次に，\(Z_1 \to Z_2 \to \cdots \to Z_m \to w \to Z_1\) というサイクルを作ります． 最後に，頂点 \(Z_1\) に印をつけます． するとこれは（根付き木をとり，更に \(1\) 頂点に印をつけたもの）になっています．

以上の操作によって \(K\)-value が保たれていることと，および逆操作が可能であることは，丁寧に議論すると確認できます．

\(g_N(x)\) を \(T_k(x)\) を使って書き直すと

\(g_N(x)=\sum_{0 \leq k \leq N-1} T_k(x) \times C(N,k) \times (N-k-1)!\)

となります． これは，以下の性質を持った根付き木を数えていると解釈できます．

• まず，\(N\) 頂点を赤と青に塗り分けます． 赤頂点の個数を \(k\) とします． 赤頂点の番号を \(r_1,\cdots,r_k\) とし，青頂点の番号を \(b_1,\cdots,b_{N-k}\) とする． そして，頂点 \(b_1\) を根とする根付き木をつくります． 各赤頂点については，その親を自由に選べます． 各青頂点 \(b_i\) については，その親を \(b_1,\cdots,b_{i-1}\) の中から選びます． この木の \(K\)-value は，\(r_i \to r_j\) (\(i<j\)) となる辺の個数 + 赤\( \to \)青の辺の個数とします．

この根付き木を \(C\) 個並べたものを数えてみます． まず，\(N\) 頂点を赤と青に塗り分けます． そして，青頂点内だけで，ちょうど \(C\) 個の成分に別れた根付き森を作ります． 最後に赤い頂点の辺の行き先を決める必要があります． これはちょうど \(T_k(x)\) 通りになります．

以上をまとめると，

\(f_N(x,y)=\sum_{0 \leq k \leq N-1} C(N,k) \times T_k(x) \times (\prod_{0 \leq i<N-k} (i+y))\)

になります． \(T_k(x)\) を展開すると

\(f_N(x,y)=\sum_{0\leq k\leq N-1} C(N-1,k) (\prod_{0 \leq i<k} ((N-i)x+i)) (\prod_{0 \leq i<N-k} (i+y))\)

という最初の式になっています． これで証明ができました．

writer解(C++)