ABC220Ex O(N^3)解法

これを読解した
Submission #27805654 - AtCoder Beginner Contest 220

参考にしたツイート

これやっと読解できた気がする
適切に行列作ると求めたいものは二次形式の値が偶数になるような01ベクトルの個数になる
問題の性質から作れる操作と直交変換かますことで3重対角行列になる
あとはDP https://t.co/TQmiButUHQ
— さんせん (@akakimidori) 2022年6月13日

なお以下の説明は、これらを自分なりに再解釈したものであり、#27805654の実際の実装は異なっているので混乱のなきよう

・ $A_{i,j}$ を、 $i< j$ かつ $i,j$ 間に辺があるとき1、それ以外0とする。 $X_i$ を頂点 $i$ にカメラを置かないとき1、それ以外0とする。
・監視されていない辺の個数は $Q_A(X):=\sum_{i,j}A_{i,j}X_iX_j={}^tXAX$ なので、 $Q_A(X)$ が偶数になるようなXの個数がわかれば十分。
・行列の成分を $\mathbb{F}_2$ とみなして、 $Q_A(X)=0$ を考えれば良い。
・正則行列PによってAを ${}^tPAP$ に置き換えても $Q_A(X)=0$ を満たすXの個数は変わらない。
・適切な正則行列Pを取ることで ${}^tPAP$ を二重対角行列にできる（←？）
・二重対角行列に変換したあとの行列を元の問題に戻すと、「パスグラフに自己辺がいくつかついたものの上で問題を解いてください」となり、自明にO(N)DPができる

「適切な正則行列Pを取ることで ${}^tPAP$ を二重対角行列にできる」というのは嘘です。
しかし、よく考えると、任意の $(i,j)$ で $A_{i,j}$ と $A_{j,i}$ をswapしても $Q_A(X)$ の値は変わらないので、「i行目を使ってi-1列目の成分を掃き出すとき、i行目に溜まった邪魔な成分はi列目に押しつける」とする掃き出し法で二重対角行列にできます。