此处应该有「笔记」。link
似乎很难有多项式做法,但是一个强大的线性代数能巧妙地解决这个问题。
原题相当于求解
\[\sum\limits_{x\in \mathbb F_2^n} \left [\sum\limits_{(i, j)\in E} x_ix_j \equiv 0 \pmod 2 \right]
\]
我们很容易将其表示为
\[\begin {aligned}
\sum\limits_{x\in \mathbb F_2^n} \left [\sum_{i = 1} ^ n \sum_{j = 1} ^ n A_{i, j}x_ix_j \equiv 0 \pmod 2 \right]
&= \sum\limits_{x\in \mathbb F_2^n} \left [x^TAx \equiv 0 \pmod 2 \right]
\end {aligned} \]
令 \(Q\) 为一个模 \(2\) 意义下的可逆矩阵,那么 \(Qx\) 取遍 \(\mathbb F_2^n\),可以表示为
\[\begin {aligned}
\sum\limits_{x\in \mathbb F_2^n} \left [(Qx)^TA(Qx) \equiv 0 \pmod 2 \right]
&= \sum\limits_{x\in \mathbb F_2^n} \left [x^TQ^TAQx \equiv 0 \pmod 2 \right] \\
&= \sum\limits_{x\in \mathbb F_2^n} \left [x^T(Q^TAQ)x \equiv 0 \pmod 2 \right]
\end {aligned} \]
\(Q/Q^T\) 可以表示为若干个初等变换的矩阵乘积,我们