黒板に書きこむ整数集合には \(1\) から \(N\) の相異なるラベルを適当に割り振ることにし、操作の際は \(S_0\) のラベルを \(S_1\) に引き継がせることにします。ラベルの割り振り方は \(N!\) 通りであるため、この設定の下での答えを \(N!\) で割れば正しい答えが得られます。

一連の操作を終えた後黒板に書かれている整数集合 \(T_1,T_2,\dots,T_N\) が固定されている場合の操作の数え上げを考え、それらをすべて足しあわせて答えを求めます。

操作を逆順にみて数えると以下のような問題になります。

$N$ 個の集合に対して

• $A$ 以下、 $A+1$ 上の整数の組 $(a,b)$ であって、 $a,b$ が相異なる集合に属すものを選ぶ。 $a,b$ が属する集合をマージする

という操作を $N-1$ 回行うことで $1$ つの集合にするとき、操作として考えられるものの数を求めよ。

ここで、 \(N\) 個の集合を \(N\) 頂点のグラフに、集合のマージを辺の追加に置き換え、合併状況をグラフの連結性で管理することを考えます。このような言いかえの元で操作について考えると、 \(a,b\) を選ぶ際、重要なのは \(a,b\) が初期状態においてどの集合に属していたかです。初期状態において各集合 \(T_i\) に属している \(A\) 以下の整数、 \(A+1\) 以上の整数の個数をそれぞれ \(a_i,b_i\) とおくと、問題は以下のように言い換えられます。

$N$ 頂点 $0$ 辺のグラフに対して

• 連結でない頂点 $i,j$ を選び、頂点 $i,j$ 間に辺を張る。このとき辺には $a_ib_j+b_ia_j$ 種類のラベルから $1$ つ選んで付与する

という操作を $N-1$ 回行うことで連結グラフにするとき、操作として考えられるものの数を求めよ。

これは頂点 \(i,j\) 間に辺が \(a_ib_j+b_ia_j\) 本あるようなグラフにおける全域木の数え上げであり、行列木定理から答えはラプラシアン

\[L=\mathrm{diag}(Ba_i+Ab_i) - \boldsymbol{a} \boldsymbol{b}^{T} - \boldsymbol{b} \boldsymbol{a}^{T}\]

の余因子 \(\times (N-1)!\) となります（ \(\times (N-1)!\) は辺を追加する順番の分です）。ここで、 \(\mathrm{diag}(Ba_i+Ab_i)\) は \(i\) 行 \(i\) 列目の要素が \(Ba_i+Ab_i\) であり、対角成分以外が \(0\) であるような行列であり、 \(\boldsymbol{a},\boldsymbol{b}\) はそれぞれ \(i\) 行目の要素が \(a_i,b_i\) であるような列ベクトルです。

この余因子について、 \(\boldsymbol{a} \boldsymbol{b}^{T} + \boldsymbol{b} \boldsymbol{a}^{T}\) のランクは \(2\) であることを利用すると、この問題の答えは

\[\displaystyle \left(\prod_{i=2}^{N} (Ba_i+Ab_i) \right) \left(1 - \sum_{i=2}^{N}\frac{2a_ib_i}{Ba_i+Ab_i} + \sum_{2 \leq i \neq j \leq N} \frac{a_ib_ia_jb_j}{(Ba_i+Ab_i)(Ba_j+Ab_j)} - \sum_{2 \leq i \neq j \leq N} \frac{a_i^2b_j^2}{(Ba_i+Ab_i)(Ba_i+Ab_j)}\right) \times (N-1)!\]

と求まります（この部分や下で行う計算についての詳細はtatyamさんのユーザー解説 を参照）。

さて、この値をありうるすべての \(T_1,T_2,\dots,T_N\) の組に対して足し合わせます。 \(a_i,b_i\) はそれぞれ \(A\) 以下、 \(A+1\) 以上の値から \(a_i,b_i\) 個選ぶと考えると最終的な答えは

\[\displaystyle \frac{A!B!}{N} \sum_{\sum a_i = A, \sum b_i = B} \frac{1}{a_1!b_1!} \left(\prod_{i=2}^{N} \frac{Ba_i+Ab_i}{a_i!b_i!} \right) \left(1 - \sum_{i=2}^{N}\frac{2a_ib_i}{Ba_i+Ab_i} + \sum_{2 \leq i \neq j \leq N} \frac{a_ib_ia_jb_j}{(Ba_i+Ab_i)(Ba_j+Ab_j)} - \sum_{2 \leq i \neq j \leq N} \frac{a_i^2b_j^2}{(Ba_i+Ab_i)(Ba_i+Ab_j)}\right) \]

です。

この値について形式的べき級数を用いて計算しましょう。 \(\sum_{}\frac{x^n}{n!}=e^x, \sum_{}\frac{nx^n}{n!}=xe^x, \sum_{}\frac{n^2x^n}{n!}=(x^2+x)e^x\) であることからこの値は

\[\displaystyle \frac{A!B!}{N} [x^A y^B] (Bx+Ay)^{N-1}e^{N(x+y)}-2(N-1)xy(Bx+Ay)^{N-2} e^{N(x+y)} + (N-1)(N-2)x^2y^2 (Bx+Ay)^{N-3} e^{N(x+y)} - (N-1)(N-2)(x^2+x)(y^2+y)(Bx+Ay)^{N-3}e^{N(x+y)}\]

となり、結局は定数個の \(i,j,k\) の組に対して \([x^{A-i}y^{B-j}](Bx+Ay)^{N-k}e^{N(x+y)}\) を求める問題になります。これは \((Bx+Ay)^{N-k}\) を展開して各項について \(e^{N(x+y)}\) の係数を計算することができるので、\(N,A,B\) のべき乗や階乗などの前計算の下で \(O(N)\) で計算することができます。