526互联

[QOJ6555] The 2nd Universal Cup. Stage 5. J : Sets May Be Good

发布时间 2023-10-19 09:56:07作者: 云浅知处

先给 EI 磕三个

首先考虑用 \(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_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 mod=998244353;
int ksm(int x,int y,int p=mod){
	int ans=1;
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}

const int N=1005;

bitset<N>G[N];
int n,m,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);
	}
	
	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++){
			add(g[0][y],f[x][y]);
			if(x==0)add(g[1][y],f[x][y^G[i][i]]);
			else add(g[1][y],f[x][y^G[i][i]^G[i][i-1]]);
		}
		for(int x=0;x<=1;x++)for(int y=0;y<=1;y++)f[x][y]=g[x][y];
	}
	
	int ans=f[0][0];add(ans,f[1][0]);
	cout<<ans<<endl;

	return 0;
}