(より詳しい解説は後日ブログで公開します)

次の \(2\) つの問題を組み合わせたような問題で，実際にこれらの解法を組み合わせると解けます．

• \(\det(A+xB)\)
  • https://yukicoder.me/problems/no/1907/
  • https://qoj.ac/problem/59
• \(\operatorname{pf}(A)\)
  • https://judge.yosupo.jp/problem/pfaffian_of_matrix

\(\operatorname{pf}(A+xB)^2 = \det(A+xB)\) なので，\(\det(A+xB)\) を求めて多項式として平方根をとることで，符号を除いて答えがわかります．符号は，\(x\) に適当な値を代入したとき \(0\) にならなければ，その値で Pfaffian を計算することで特定できます．

ところが，\(N \ge 101\) では \(x=0,1,\ldots,100\) のいずれでも Pfaffian が \(0\) になってしまうケースがあります．そこで，\(\mathbb{F}_{101}\) の代わりに例えば拡大体 \(\mathbb{F}_{101^2}\) を用いると，\(N < 101^2\) なので多項式として \(0\) でなければ非零点が必ず存在します．

非零点の存在を仮定したうえで，全体で \(O(N^3)\) 時間です．