公式解説 のラプラシアン行列から答えを得る部分を補足します．

例えば，\(N = 4\) のとき，頂点 \(i < j\) 間に \(a_i b_j + b_i a_j\) 本の辺を張るので，ラプラシアン行列は以下のようになります．

\[ \begin{bmatrix} a_1(b_2 + b_3 + b_4) + b_1(a_2 + a_3 + a_4) & -(a_1 b_2 + b_1 a_2) & -(a_1 b_3 + b_1 a_3) & -(a_1 b_4 + b_1 a_4) \\ -(a_2 b_1 + b_2 a_1) & a_2(b_1 + b_3 + b_4) + b_2(a_1 + a_3 + a_4) & -(a_2 b_3 + b_2 a_3) & -(a_2 b_4 + b_2 a_4) \\ -(a_3 b_1 + b_3 a_1) & -(a_3 b_2 + b_3 a_2) & a_3(b_1 + b_2 + b_4) + b_3(a_1 + a_2 + a_4) & -(a_3 b_4 + b_3 a_4) \\ -(a_4 b_1 + b_4 a_1) & -(a_4 b_2 + b_4 a_2) & -(a_4 b_3 + b_4 a_3) & a_4(b_1 + b_2 + b_3) + b_4(a_1 + a_2 + a_3) \\ \end{bmatrix}\\ = \begin{bmatrix} Ba_1 + Ab_1 & & & \\ & Ba_2 + Ab_2 & & \\ & & Ba_3 + Ab_3 & \\ & & & Ba_4 + Ab_4 \\ \end{bmatrix} - \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix}\begin{bmatrix} b_1 & b_2 & b_3 & b_4 \\ \end{bmatrix} - \begin{bmatrix} b_1 \\ b_2 \\ b_3 \\ b_4 \end{bmatrix}\begin{bmatrix} a_1 & a_2 & a_3 & a_4 \\ \end{bmatrix} \]

この行列の余因子として，\(1\) 行目と \(1\) 列目を取り除いた行列の行列式を求めます． ここで，行列式の多重線形性を用いて行列式を展開します．これは，以下のような性質です．

\[ \det\begin{bmatrix} a_1 + b_1 & a_2 + b_2 & a_3 + b_3 \\ c_1 & c_2 & c_3 \\ d_1 & d_2 & d_3 \\ \end{bmatrix} = \det\begin{bmatrix} a_1 & a_2 & a_3 \\ c_1 & c_2 & c_3 \\ d_1 & d_2 & d_3 \\ \end{bmatrix} + \det\begin{bmatrix} b_1 & b_2 & b_3 \\ c_1 & c_2 & c_3 \\ d_1 & d_2 & d_3 \\ \end{bmatrix} \]

したがって，求めるべき行列式は，\(2, 3, \dots, N\) 行目のそれぞれについて，その行を

\[ \begin{aligned} L_1 &:= \begin{bmatrix} Ba_2 + Ab_2 & & & \\ & Ba_3 + Ab_3 & & \\ & & Ba_4 + Ab_4 & \\ & & & \ddots \\ \end{bmatrix}\\ L_2 &:= -\begin{bmatrix} a_2 \\ a_3 \\ a_4 \\ \vdots \end{bmatrix}\begin{bmatrix} b_2 & b_3 & b_4 & \cdots \\ \end{bmatrix}\\ L_3 &:= -\begin{bmatrix} b_2 \\ b_3 \\ b_4 \\ \vdots \end{bmatrix}\begin{bmatrix} a_2 & a_3 & a_4 & \cdots \\ \end{bmatrix} \\ \end{aligned} \]

のいずれかから持ってくる \(3^{N-1}\) 通りについて行列式を求めたときの，その総和となります．

ここで， \(L_2\) から行を複数回持ってくると，それらの行ベクトルがいずれも \(\begin{bmatrix} b_2 & b_3 & b_4 & \cdots \\ \end{bmatrix}\) の定数倍なため，線形従属になって行列式が \(0\) となります．したがって，\(L_2\) から行を \(1\) 個以下持ってくるような行列のみを考えれば良いことがわかります． これは \(L_3\) に対しても同様です．

まとめると，以下の \(1 + 2(N-1) + (N-1)(N-2)\) 個の行列に対して行列式を求め，その総和を求めれば良いです．

• \(L_1\)
• \(L_1\) の \(i\) 行目を \(L_2\) で置き換えた行列 \((2 \le i \le N)\)
• \(L_1\) の \(j\) 行目を \(L_3\) で置き換えた行列 \((2 \le j \le N)\)
• \(L_1\) の \(i\) 行目を \(L_2\) で，\(j\) 行目を \(L_3\) で置き換えた行列 \((2 \le i,j \le N,\ i \ne j)\)

ここから，\(A + B\) 個の整数を \(N\) 個のラベル付き集合に分割するすべての方法について，行列式の総和を取ります． \(\det L_1\) の部分について考えます．\((a_1, \dots, a_N),\ (b_1, \dots, b_N)\) が固定されたとき，そのように整数を割り振る方法は多項係数 \(\dbinom{A}{a_1, \dots, a_N}\dbinom{B}{b_1, \dots, b_N}\) となるので，求めるべき総和は

\[ \begin{aligned} &\quad\sum_{\substack{A = a_1 + \dots + a_N \\ B = b_1 + \dots + b_N}}\dbinom{A}{a_1, \dots, a_N}\dbinom{B}{b_1, \dots, b_N} \left(\prod_{i=2}^NBa_i + Ab_i\right)\\ &=A!B!\sum_{\substack{A = a_1 + \dots + a_N \\ B = b_1 + \dots + b_N}}\frac{1}{a_1!b_1!} \left(\prod_{i=2}^N\frac{Ba_i + Ab_i}{a_i!b_i!}\right)\\ \end{aligned} \]

となります． 和の制約 \(A = a_1 + \dots + a_N,\ B = b_1 + \dots + b_N\) がある上での積の総和なので，この和をそれぞれ \(x\) の指数部分，\(y\) の指数部分で管理する \(2\) 変数 FPS を考えると良さそうです．

\[ \begin{aligned} &\quad A!B!\sum_{\substack{A = a_1 + \dots + a_N \\ B = b_1 + \dots + b_N}}\frac{1}{a_1!b_1!} \left(\prod_{i=2}^N\frac{Ba_i + Ab_i}{a_i!b_i!}\right)\\ &=A!B!\left([x^Ay^B]\left(\sum_{a_1 = 0}^\infty\frac{1}{a_1!}x^{a_1}\right)\left(\sum_{b_1 = 0}^\infty\frac{1}{b_1!}y^{b_1}\right)\left(\prod_{i=2}^N\left(\sum_{a_i = 0}^\infty\sum_{b_i = 0}^\infty\frac{Ba_i + Ab_i}{a_i!b_i!}x^{a_i}y^{b_i}\right)\right)\right)\\ &=A!B!\left([x^Ay^B]e^xe^y\prod_{i=2}^N\left(\left(\sum_{a_i = 0}^\infty\sum_{b_i = 0}^\infty\frac{Ba_i}{a_i!b_i!}x^{a_i}y^{b_i}\right) + \left(\sum_{a_i = 0}^\infty\sum_{b_i = 0}^\infty\frac{Ab_i}{a_i!b_i!}x^{a_i}y^{b_i}\right)\right)\right)\\ &=A!B!\left([x^Ay^B]e^xe^y\prod_{i=2}^N\left(B\left(\sum_{a_i = 0}^\infty\frac{a_i}{a_i!}x^{a_i}\right)\left(\sum_{b_i = 0}^\infty\frac{1}{b_i!}x^{b_i}\right) + A\left(\sum_{a_i = 0}^\infty\frac{1}{a_i!}x^{a_i}\right)\left(\sum_{b_i = 0}^\infty\frac{b_i}{b_i!}x^{b_i}\right)\right)\right)\\ &=A!B!\left([x^Ay^B]e^xe^y\prod_{i=2}^N\left(B \cdot xe^x \cdot e^y + A \cdot e^x \cdot ye^y\right)\right)\\ &=A!B!\left([x^Ay^B]e^{Nx}e^{Ny}\left(Bx + Ay\right)^{N-1}\right)\\ &=A!B!\left([x^Ay^B]e^{Nx}e^{Ny}\left(\sum_{i = 0}^{N-1}\binom{N-1}{i}(Bx)^i(Ay)^{N-1-i}\right)\right)\\ &=A!B!\left(\sum_{i = 0}^{N-1}\binom{N-1}{i}B^iA^{N-1-i}\left([x^{A-i}y^{B-N+1+i}]e^{Nx}e^{Ny}\right)\right)\\ &=A!B!\left(\sum_{i = 0}^{N-1}\binom{N-1}{i}B^iA^{N-1-i}\left([x^{A-i}]e^{Nx}\right)\left([y^{B-N+1+i}]e^{Ny}\right)\right)\\ &=A!B!\left(\sum_{i = 0}^{N-1}\binom{N-1}{i}B^iA^{N-1-i} \cdot \frac{N^{A-i}}{(A-i)!} \cdot \frac{N^{B-N+1+i}}{(B-N+1+i)!}\right)\\ &=A!B!N^{A+B-N+1}\left(\sum_{i = 0}^{N-1}\binom{N-1}{i}\frac{A^{N-1-i}}{(A-i)!} \cdot \frac{B^i}{(B-N+1+i)!}\right)\\ \end{aligned} \]

この値は \(O(A + B + N + \log \text{MOD})\) 時間で求めることができます．

続いて，\(L_1\) の \(i\) 行目を \(L_2\) で置き換えた行列 \((2 \le i \le N)\) について考えます．\((a_1, b_1), \dots, (a_N, b_N)\) は対称的なので，\(i = 2\) の場合の答えを \((N-1)\) 倍すればよいです．

\[ \det\begin{bmatrix} -a_2b_2 & -a_2b_3 & -a_2b_4 & \cdots \\ & Ba_3 + Ab_3 & & \\ & & Ba_4 + Ab_4 & \\ & & & \ddots \\ \end{bmatrix} = -a_2b_2\left(\prod_{i=3}^N Ba_i + Ab_i\right) \]

ですから，求めるべき総和は

\[ \begin{aligned} &\quad A!B!\sum_{\substack{A = a_1 + \dots + a_N \\ B = b_1 + \dots + b_N}}\frac{1}{a_1!b_1!} \frac{-a_2b_2}{a_2!b_2!} \left(\prod_{i=3}^N\frac{Ba_i + Ab_i}{a_i!b_i!}\right)\\ &= -A!B!\left([x^Ay^B]e^x e^y \cdot xe^x ye^y \cdot \left(B \cdot xe^x \cdot e^y + A \cdot e^x \cdot ye^y\right)^{N-2}\right)\\ &= -A!B!\left([x^{A-1}y^{B-1}]e^{Nx} e^{Ny} \left(Bx + Ay\right)^{N-2}\right)\\ &= -A!B!\left([x^{A-1}y^{B-1}]e^{Nx}e^{Ny}\left(\sum_{i = 0}^{N-2}\binom{N-2}{i}(Bx)^i(Ay)^{N-2-i}\right)\right)\\ &= -A!B!\left(\sum_{i = 0}^{N-2}\binom{N-2}{i}B^iA^{N-2-i}[x^{A-1-i}y^{B-N+1+i}]e^{Nx}e^{Ny}\right)\\ &= -A!B!\left(\sum_{i = 0}^{N-2}\binom{N-2}{i}B^iA^{N-2-i} \cdot \frac{N^{A-1-i}}{(A-1-i)!} \cdot \frac{N^{B-N+1+i}}{(B-N+1+i)!}\right)\\ &= -A!B!N^{A+B-N}\left(\sum_{i = 0}^{N-2}\binom{N-2}{i} \frac{A^{N-2-i}}{(A-1-i)!} \cdot \frac{B^i}{(B-N+1+i)!}\right)\\ \end{aligned} \]

となります． \(L_1\) の \(i\) 行目を \(L_3\) で置き換えた行列 \((2 \le i \le N)\) は，対角成分が \(L_2\) の場合と同一なため，行列式も同じになります．

\(L_1\) の \(i\) 行目を \(L_2\) で置き換え，\(j\) 行目を \(L_3\) で置き換えた行列 \((2 \le i,j \le N,\ i \ne j)\) について考えます．\((a_1, b_1), \dots, (a_N, b_N)\) は対称的なので，\((i, j) = (2, 3)\) の場合の答えを \((N - 1)(N - 2)\) 倍すればよいです．

\[ \det\begin{bmatrix} -a_2b_2 & -a_2b_3 & -a_2b_4 & \cdots \\ -b_3a_2 & -b_3a_3 & -b_3a_4 & \cdots \\ & & Ba_4 + Ab_4 & \\ & & & \ddots \\ \end{bmatrix} = (a_2b_2 \cdot a_3b_3 - (a_2b_3)^2)\left(\prod_{i=4}^N Ba_i + Ab_i\right) \]

です．\(\displaystyle a_2b_2a_3b_3\left(\prod_{i=4}^N\frac{Ba_i + Ab_i}{a_i!b_i!}\right)\) の部分について総和を取ると，

\[ \begin{aligned} &\quad A!B!\sum_{\substack{A = a_1 + \dots + a_N \\ B = b_1 + \dots + b_N}}\frac{1}{a_1!b_1!} \frac{a_2b_2}{a_2!b_2!} \frac{a_3b_3}{a_3!b_3!} \left(\prod_{i=4}^N\frac{Ba_i + Ab_i}{a_i!b_i!}\right)\\ &= A!B!\left([x^Ay^B]e^x e^y \cdot xe^x ye^y \cdot xe^xye^y \cdot \left(B \cdot xe^x \cdot e^y + A \cdot e^x \cdot ye^y\right)^{N-3}\right)\\ &= A!B!\left([x^{A-2}y^{B-2}]e^{Nx} e^{Ny} \left(Bx + Ay\right)^{N-3}\right)\\ &= A!B!\left([x^{A-2}y^{B-2}]e^{Nx}e^{Ny}\left(\sum_{i = 0}^{N-3}\binom{N-3}{i}(Bx)^i(Ay)^{N-3-i}\right)\right)\\ &= A!B!\left(\sum_{i = 0}^{N-3}\binom{N-3}{i}B^iA^{N-3-i}[x^{A-2-i}y^{B-N+1+i}]e^{Nx}e^{Ny}\right)\\ &= A!B!\left(\sum_{i = 0}^{N-3}\binom{N-3}{i}B^iA^{N-3-i} \cdot \frac{N^{A-2-i}}{(A-2-i)!} \cdot \frac{N^{B-N+1+i}}{(B-N+1+i)!}\right)\\ &= A!B!N^{A+B-N-1}\left(\sum_{i = 0}^{N-3}\binom{N-3}{i} \frac{A^{N-3-i}}{(A-2-i)!} \cdot \frac{B^i}{(B-N+1+i)!}\right)\\ \end{aligned} \]

となります．また，\(\displaystyle -(a_2b_3)^2\left(\prod_{i=4}^N\frac{Ba_i + Ab_i}{a_i!b_i!}\right)\) の部分について総和を取ると，

\[ \begin{aligned} &\quad A!B!\sum_{\substack{A = a_1 + \dots + a_N \\ B = b_1 + \dots + b_N}}- \frac{1}{a_1!b_1!} \frac{{a_2}^2}{a_2!b_2!} \frac{{b_3}^2}{a_3!b_3!} \left(\prod_{i=4}^N\frac{Ba_i + Ab_i}{a_i!b_i!}\right)\\ &= -A!B!\left([x^Ay^B]e^x e^y \cdot (x^2+x)e^x e^y \cdot e^x(y^2+y)e^y \cdot \left(B \cdot xe^x \cdot e^y + A \cdot e^x \cdot ye^y\right)^{N-3}\right)\\ &= -A!B!\left([x^{A-1}y^{B-1}]e^{Nx} e^{Ny} (1 + x) (1 + y) \left(Bx + Ay\right)^{N-3}\right)\\ &= -A!B!\left([x^{A-1}y^{B-1}]e^{Nx}e^{Ny}(1 + x)(1 + y)\left(\sum_{i = 0}^{N-3}\binom{N-3}{i}(Bx)^i(Ay)^{N-3-i}\right)\right)\\ &= -A!B!\left(\sum_{i = 0}^{N-3}\binom{N-3}{i}B^iA^{N-3-i}[x^{A-1-i}y^{B-N+2+i}]e^{Nx}e^{Ny}(1 + x)(1 + y)\right)\\ &= -A!B!\left(\sum_{i = 0}^{N-3}\binom{N-3}{i}B^iA^{N-3-i} \left(\frac{N^{A-1-i}}{(A-1-i)!} + \frac{N^{A-2-i}}{(A-2-i)!}\right) \left(\frac{N^{B-N+2+i}}{(B-N+2+i)!} + \frac{N^{B-N+1+i}}{(B-N+1+i)!}\right)\right)\\ \end{aligned} \]

となります．