行列 \(A,B\) に対し，\(A \otimes B\) で行列の Kronecker Product を表し，\(A \oplus B\) で行列の Kronecker Sum を表すものとします． またベクトル \(u,v\) についても \(u \otimes v\) で Kronecker Product を表すものとします．

有向全域木の個数の求め方は有名です． 例えばここ (http://www.mit.edu/~lindrew/matrixtree.pdf) に書いてあります．

結局この問題では，次のような問題が解ければよいです．

• サイズ \(N\) の正方行列 \(A\)，およびサイズ \(M\) の正方行列 \(B\) があり，\(ker(A) \geq 1,ker(B) \geq 1\) であるとする． \(C=A \oplus B\) とするとき，\(C\) の adjugate の対角成分をすべて求めよ．

以下の事実を用います．

• \(u_1,u_2,\cdots\) が線形独立，\(v_1,v_2,\cdots\) が線形独立の時，\(u_i \otimes v_j\) も線形独立．これは初等的に示せます．

以下，行列 \(A\) の adjugate の \(i\) 番目の対角成分を \(adj(A,i)\) と書くことにします． また，行列の成分は一旦複素数であると思って議論することにします．

\(C\) の adjugate をきれいな式で書くのが目標です．

\(ker(A) \times ker(B) \geq 2\) であった場合，それぞれの kernel から適当に基底をとって直積をとると，それらはすべて線形独立かつ \(ker(C)\) に含まれます．つまり \(ker(C) \geq 2\) であり，\(adj(C)=0\) になります．

Jordan 分解を行い，\(A=P_AJ_AP^{-1}_A\)，\(B=P_BJ_BP^{-1}_B\) とおきます． この時，\(J_A,J_B\) の対角成分では \(0\) が先頭に優先的に来るようにしておきます． \(ker(A)=1\) より，\(A\) の固有値 \(0\) の Jordan 細胞は \(1\) つで，\(B\) についても同様です． \(A,B\) の固有値 \(0\) の重複度をそれぞれ \(c,d\) とします． また，一般性を失わず，\(c \leq d\) であるとします．

まず \(c\geq 2\) であると仮定してみます．

仮定より，\(u_1 \neq 0, A \times u_1=0,A \times u_2=u_1\) を満たす \(u_1,u_2 \in \mathbb{C}^N\) が取れます． 同様に，\(v_1 \neq 0, B \times v_1=0,B \times v_2=v_1\) を満たす \(v_1,v_2 \in \mathbb{C}^M\) が取れます．

\(C \times (u_1 \otimes v_2)=0 \otimes v_2 + u_1 \otimes v_1= u_1 \otimes v_1\) です．同様に，\(C \times (u_2 \otimes v_1)= u_1 \otimes v_1\) であり，\(C \times (u_1 \otimes v_2 - u_2 \otimes v_1)=0\) が従います． また，\(C \times (u_1 \otimes v_1)=0\) です． ところで，\( (u_1 \otimes v_2 - u_2 \otimes v_1)\) と \((u_1 \otimes v_1)\) は互いに独立なので，\(ker(C) \geq 2\) が従い，\(adj(C)=0\) となります．

以下，\(c=1\) であるとします． \(C=(P_A \otimes P_B) \times (J_A \oplus J_B) \times (P^{-1}_A \otimes P^{-1}_B)\) と変形して議論しますが，これは Jordan 分解ではことに注意してください．

\((J_A \oplus J_B)\) を考えると，対角成分の最初の \(d\) 個は必ず \(0\) になります． それ以外に対角成分に \(0\) があった場合，\(ker(J_A \oplus J_B) \geq 2\) となり，\(adj(C)=0\) となります． 次に，\((J_A \oplus J_B)\) の対角成分は最初の \(d\) 個を除いてすべて非ゼロだとします．正数 \(\epsilon\) を任意にとり，\((J_A \oplus J_B)\) の最初の \(d\) 個の対角成分に \(\epsilon\) を加えたものを \(D\) と定義します． 以下で見るように，\(det(D) \times D^{-1}\) は \(\epsilon \to 0\) で収束します． よって，\(adj(C)=\lim_{\epsilon \to 0} adj((P_A \otimes P_B) \times D \times (P^{-1}_A \otimes P^{-1}_B))=\lim_{\epsilon \to 0} (P_A \otimes P_B) \times det(D)D^{-1} \times (P^{-1}_A \otimes P^{-1}_B)\) となります．

\(det(D)D^{-1}\) について考えます．\(det(D)\) に \(\epsilon^d\) の項があるので，\(D^{-1}\) の中で重要なのは \(\epsilon^{-d}\) の項だけです． \(D\) の左上は大きさ \(d\)，固有値 \(\epsilon\) の Jordan 細胞と同じ形をしているので，\(D^{-1}\) の \((1,1)\) 行目，\((1,d)\) 列目の要素は \((-1)^{d-1} \times \epsilon^{-d}\) です．これ以外に \(\epsilon^{-d}\) の項はないことが簡単に確認できます．

\(P_A\) の \(1\) 列目を \(al\)，\(P_B\) の \(1\) 列目を \(bl\)，\(P^{-1}_A\) の \(1\) 行目を \(ar\)，\(P^{-1}_B\) の \(d\) 行目を \(br\) とおきます． \(A\) の固有値を重複度を込めて \(\lambda_1,\lambda_2,\cdots,\lambda_N\) とし，\(B\) の固有値を重複度を込めて \(\mu_1,\mu_2,\cdots,\mu_M\) とします．ここで，\(0\) は必ず先頭に集まるようにします．この時， \(adj(C,(p,q))=al[p] \times bl[q] \times \prod_{c+1 \leq i \leq N} \lambda_i \times \prod_{d+1 \leq j \leq M} \mu_j \times \prod_{2 \leq i \leq N,2 \leq j \leq M} (\lambda_i+\mu_j) \times (-1)^{d-1} \times ar[p] \times br[q]\) と求まります．

ここで，\(al[p] \times \prod_{c+1 \leq i \leq N} \lambda_i \times ar[p] =adj(A,p)\) 及び \(bl[q] \times \prod_{d+1 \leq j \leq M} \mu_j \times (-1)^{d-1} \times br[q]=adj(B,q)\) が確認できます．これは，\(A,B\) の Jordan 分解に対して，\(C\) で行ったのと同様に逆行列\(\times\)行列式の極限を取ればいいです．

結局，\(adj(C,(p,q))=adj(A,p) \times adj(B,q) \times \prod_{2 \leq i \leq N,2 \leq j \leq M} (\lambda_i+\mu_j)\) となります．

また，途中で答えが \(0\) になるとして無視したすべてのケースについて，上の式でも正しく求まることが確認できます．

最後に，上の式を \(\bmod 998244353\) で実際に計算する方法を示します．

\(adj(A,p)\) を求めるには，\(A=PDQ\) (\(P,Q\) は正則，\(D\) は対角行列) と変形し，\(D\) の対角成分の \(0\) を \(\epsilon>0\) だと思って \(\epsilon \to 0\) の極限を取ればよいです．\(adj(B,q)\) も同じです．

\(\prod_{2 \leq i \leq N,2 \leq j \leq M} (\lambda_i+\mu_j)\) については \(A,B\) の固有多項式を求めたあと，resultant を用いることで計算できます．固有多項式は hessenberg form を使うと \(O(N^3)\) (or \(O(M^3)\))で計算可能です．resultant は互除法の要領で \(O(NM)\) で求められます．（writer 解を参照してください．）

結局，すべての操作は \(O(N^3+M^3)\) で可能となり，この問題が解けます．

おまけ：書いたけどよく考えたら使ってなかった事実

• \(A\) の固有値を重複度を込めて \(\lambda_1,\lambda_2,\cdots,\lambda_N\) とし，\(B\) の固有値を重複度を込めて \(\mu_1,\mu_2,\cdots,\mu_M\) とするとき，\(C\) の固有値は重複度を込めて \(\{\lambda_i+\mu_j\}\) (for all \(1 \leq i \leq N\), \(1 \leq j \leq M\)) になります．これは次のように示せます．Jordan 分解を行い，\(A=P_AJ_AP^{-1}_A\)，\(B=P_BJ_BP^{-1}_B\) とおくと，\(C=(P_A \otimes P_B) \times (J_A \oplus J_B) \times (P^{-1}_A \otimes P^{-1}_B)\) となります．よって \(C\) と \((J_A \oplus J_B)\) は相似になり，その固有値が一致します．\((J_A \oplus J_B)\) は上三角なので，固有値はその対角成分であり，それは \(\{\lambda_i+\mu_j\}\) です．