操吴戈兮披犀甲

· · 题解

先给 EI 磕三个

上回书说到有一个 O(\frac{n^3}{w}) 的做法，下面给出其详细过程。由于作者本人在写这篇题解的时候现学的线代，所以可能某些地方比较显然的事实也会反复说几遍，见谅！/wq

首先考虑用 n 个变量 x_1,x_2,\cdots,x_n\in\{0,1\} 表示第 i 个点选不选，那么导出子图的边数的奇偶性就是

f(x_1,x_2,\cdots,x_n)=\left(\sum_{(i,j)\in E}x_i^2+x_j^2+x_ix_j\right)\bmod 2

这是二次型，考虑把 f(v) 写成 v^\textsf{T}Av 的形式，其中 v 是 x_1,\cdots,x_n 的列向量，A_{i,j} 是上面这个多项式中 x_ix_j 项的系数。我们需要求出所有列向量 v\in\mathbb F_2^n 的 f(v) 之和。

我们考虑对 A 做一些变换来简化问题。考虑取矩阵 Q，使得当 v 取遍 \mathbb F_2^n 的时候，Qv 也取遍 \mathbb F_{2}^n。那么就有

\sum_vv^\textsf{T}Av=\sum_{v}(Qv)^{\mathsf{T}}AQv=\sum_{v}v^{\mathsf T}(Q^{\mathsf T}AQ)v

于是我们就可以把 A 变成 Q^{\mathsf T}AQ。这里直接给出这三种变换：

注意到 x_ix_j 的系数与 x_jx_i 的系数本质没有区别，因此我们可以对每个 i=2,\cdots,n，令 A_{i,1}\leftarrow A_{i,1}+A_{1,i},A_{1,i}\leftarrow 0。容易发现这不会影响结果。这样一来，我们就把第一行除了 A_{1,1} 以外的数都变成了 0。如下：

\begin{bmatrix}A_{1,1}&A_{1,2}&A_{1,3}&\cdots &A_{1,n}\\A_{2,1}& &\cdots&\\A_{3,1}&&\cdots\\\vdots&&\ddots&&\vdots\\A_{n,1}&&\cdots&&A_{n,n}\end{bmatrix}\to\begin{bmatrix}A_{1,1}&0&0&\cdots &0\\A_{2,1}+A_{1,2}& &\cdots&\\A_{3,1}+A_{1,3}&&\cdots\\\vdots&&\ddots&&\vdots\\A_{n,1}+A_{1,n}&&\cdots&&A_{n,n}\end{bmatrix}

当然运算都在模意义下进行。

取 Q 为交换 x_i,x_j 对应的变换，即 Q_{k,k}=1(k\neq i,k\neq j),Q_{i,j}=Q_{j,i}=1。

那么考虑 Q^{\mathsf T}AQ 是啥，发现就是先交换 i,j 两行，再交换 i,j 两列。这样就实现了交换两行。

那么这样一来，我们找到 i\ge 2 使得 A_{i,1}\neq 1，然后就可以把 A_{i,1} 交换到 A_{2,1} 的位置。如果不存在这样的 i，我们的目标就已经达成了，可以直接对第 2 行开始重复这个过程。

为什么不直接换到第一行？如果换到第一行，那么第一列也要被换走，然后就寄了

下面还要用这个去消掉别的 A_{i,1}，其中 i\ge 3。假设要消掉第 j 行，方法是：取 Q 为 x_j\leftarrow x_j+x_i 对应的变换，即 Q_{i,i}=1（1\le i\le n），以及 Q_{i,j}=1。那么 Q^{\mathsf T}AQ 是啥呢，发现造成的影响就是，先把所有 A_{j,k}\leftarrow A_{j,k}+A_{i,k}，然后再把所有 A_{k,j}\leftarrow A_{k,j}+A_{k,i}。

这样一来，我们就能把矩阵中除了 A_{1,1},A_{2,1} 之外，第一行第一列的位置都消成 0。于是考虑一直这样做下去，就能在 O(n^3) 的时间内把矩阵变成只有 A_{i,i},A_{i,i-1} 非零的情况。

这种情况相当于图是一个带有若干自环的链，那么直接 DP 即可。

然后我们发现复杂度的瓶颈在消元那一步，考虑我们依次施加若干个变换 Q_1,Q_2,\cdots,Q_k，那么原本的 A 就变成 Q_k^{\mathsf T}Q_{k-1}^{\mathsf T}\cdots Q_1^{\mathsf T}AQ_1\cdots Q_k=(\prod_{i=1}^k Q_i)^{\mathsf T}A(\prod_{i=1}^k Q_i)，于是这个等价于一起做。

考虑先做行，发现如果我们维护的是行的 bitset 那可以直接做；然后再做列，注意到这个是把第 i 列异或到后面的某些列上面，考虑算出来这些列的 bitset，然后把对第 i 列上的每个 1，就把这一行异或上这个 bitset。

这样总复杂度就是 O(\frac{n^3}{w})。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

const int N=45;

bitset<N>G[N];
int n,m;
ll f[2][2],g[2][2];

signed main(void){

#ifdef YUNQIAN
    freopen("in.in","r",stdin);
#endif

    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        G[u].flip(v),G[u].flip(u),G[v].flip(v);
    }

    for(int i=1;i<=n;i++){
        // step 1
        for(int j=i+1;j<=n;j++)if(G[i][j])G[j].flip(i),G[i][j]=0;

        // step 2
        int p=-1;
        for(int j=i+1;j<=n;j++)if(G[j][i]!=0)p=j;
        if(p==-1)continue;
        swap(G[p],G[i+1]);
        for(int j=i+1;j<=n;j++){
            bool t=G[j][p];
            G[j][p]=G[j][i+1],G[j][i+1]=t;
        }

        // step 3
        bitset<N>f;f.reset();
        for(int j=i+2;j<=n;j++)if(G[j][i])G[j]^=G[i+1],f[j]=1;
        for(int j=i+1;j<=n;j++)if(G[j][i+1])G[j]^=f;
    }

    f[0][0]=1;
    for(int i=1;i<=n;i++){
        memset(g,0,sizeof(g));
        for(int x=0;x<=1;x++)for(int y=0;y<=1;y++){
            g[0][y]+=f[x][y];
            if(x==0)g[1][y^G[i][i]]+=f[x][y];
            else g[1][y^G[i][i]^G[i][i-1]]+=f[x][y];
        }
        for(int x=0;x<=1;x++)for(int y=0;y<=1;y++)f[x][y]=g[x][y];
    }

    ll ans=f[0][0];ans+=f[1][0];
    cout<<ans<<endl;

    return 0;
}