\(\det(A+xB)\) の計算を特性多項式の計算に帰着するアルゴリズム (https://yukicoder.me/problems/no/1907/) の解説で紹介されているものと同じ方法で、 Pfaffian の最高次の係数を計算できます。行基本変形を行う際に対応する列基本変形を続けて行うことに気を付けて \(B\) を掃き出すことによって、 Pfaffian の最高次の次数と係数が求まるか、 Pfaffian がゼロであるかのどちらかの結論が得られます。残った行列の行列式の計算は容易に特性多項式の計算に帰着するので、特性多項式の平方根のうちモニックなほうを求めて最高次の情報を与えれば解が得られます。

実装例