【2025广东省队集训day2】异或症测试 3 做题记录

给定一个集合 $B$ 和一个正整数 $X$，求有多少个集合 $S\subseteq \{1,2,3,\dots,X\}$ 满足 $B$ 是 $S$ 的线性基。

$1\le |B|\le 2000$，$B$ 中元素和 $X$ 以 01 串的形式给出，高位在前低位在后，所有 01 串的长度相等且 $\le 2000$。

设 $n=|B|$，$m$ 为 01 串长度。

首先可以使用 bitset 在 $O(\frac{nm^2}{\omega})$ 的复杂度内将 $B$ 变为最简线性基（每个基的最高位都满足这一位为 $1$ 的基只有它一个）并特判掉 $B$ 不是合法线性基的情况。

对于一个最简线性基 $M$，送一个 $|M|$ 位的二进制数 $x$ 进去就可以得到一个数 $M(x)$，其中 $x_i$ 为从大到小第 $i$ 个基的选择情况。再定义 $\text{mx}(M,x)$ 表示最大的 $y$ 满足 $M(y)\le x$。

注意到 $\forall 1\le y<x,B(y)<B(x)$，故 $\text{mx}$ 可以通过每个基从大往小能选就选来求出。那么求出 $x=\text{mx}(B,X)$ 后（显然 $x$ 是一个 $n$ 位二进制数）问题就变成了数有多少个集合 $S\subseteq\{1,2,3,\dots ,x\}$ 满足 $S$ 的线性基是满的（大小为 $n$）。

这个问题是困难的，但注意到一个集合只有一个最简线性基。故考虑容斥，转而去计算所有大小为 $i$ 的最简线性基 $M$ 的 $2^{\text{mx}(M,x)}$（其实就是其生成的数的集合和 $\{1,2,3,\dots,x\}$ 的交的子集数）的和 $sm_i$，则这 $sm_i$ 个集合生成的线性基的大小都 $\le i$。

设 $c_i$ 为 $sm_i$ 的容斥系数，则 $\sum c_i\times sm_i$ 是可以直接 dp 求的。具体的，朴素的想法是设 $f_{i,j,0/1}$ 表示考虑了前 $i$ 位，还剩 $j$ 个基没有填入，当前贪心选上的基的异或和有没有顶到 $x$ 的上界（$0$ 表示顶到了），然后容斥系数填进 dp 初始值。但是可能会出现在 $0\to 1$ 的那一位上存在基的情况，这时要钦定这个基选上后异或和大于 $x$，所以要记 $f_{i,j,0/1/2}$。并且转移的系数还要求记录之前是否选上基，故实际上是 $f_{i,j,0/1/2,0/1}$。转移是 $O(1)$ 的，故这部分的时间复杂度是 $O(n^2)$ 的。

现在问题变成求 $c_i$。首先显然有 $c_n=1$，然后有 $c_i=-\sum\limits_{j>i}c_j\times h_{i,j}$，其中 $h_{i,j}$ 表示对于某个大小为 $i$ 的最简线性基 $M$，其能被多少个大小为 $j$ 的最简线性基生成，即随便往 $M$ 里插入一些数使得其大小变为 $j$ 后有几个本质不同的，不难发现这个东西和 $M$ 的具体值无关。

具体的，考虑找一个值域为 $[0,2^{n-i}-1]$ 大小为 $j-i$ 的最简线性基 $K$ 和 $M$ 合并（考虑 $K$ 中的位其实是 $M$ “控制不了” 的），显然这样就能得到所有本质不同的能生成 $M$ 的大小为 $j$ 的最简线性基。

故只需要计算 $K$ 的个数，那么这个东西可以 dp，设 $g_{i,j}$ 表示加入了前 $i$ 位，现在有 $j$ 个基，则有转移：

$g_{i-1,j}\times 2^j\to g_{i,j}\\ g_{i-1,j}\to g_{i,j+1}$

通过某些高明的推导，可以求出 $g_{i,j}$ 的通项。但是在本题中 $O(n^2)$ 预处理足够了。

时间复杂度 $O(n^2)$，代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>

using namespace std;

const int S=2005;

#define p 998244353

int pw[S*S],inv[S*S],ppw[S];
int n,m;
int b[S];
int h[S][S];
int c[S],f[S][S][3][2];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

namespace init
{
	char str[S];
	bitset<S> tmp,a[S];
	int idx[S],cur[S];
	inline bool ins()
	{
		for(int i=1;i<=m;i++)
		{
			if(tmp[i]==0) continue;
			if(a[i][i]==0)
			{
				for(int j=i+1;j<=m;j++) if(tmp[j]==1) tmp^=a[j];
				for(int j=1;j<=i-1;j++) if(a[j][i]==1) a[j]^=tmp;
				a[i]=tmp;
				return true;
			}
			tmp^=a[i];
		}
		return false;
	}
	inline void build(){for(int i=1,t=0;i<=m;i++) if(a[i][i]!=0) idx[i]=++t;}
	inline bool input()
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>(str+1);
			for(int j=1;j<=m;j++) tmp[j]=str[j]-'0';
			if(!ins()) return cout<<"0\n",false;
		}
		build();
		cin>>(str+1);
		for(int i=1;i<=m;i++) tmp[i]=str[i]-'0';
		for(int i=1;i<=m;i++)
		{
			if(a[i][i]==0) continue;
			b[idx[i]]=1;
			for(int j=1;j<=m;j++) cur[j]^=a[i][j];
			bool fl=true;
			for(int j=1;j<=m;j++)
				if(cur[j]!=tmp[j])
				{
					fl=cur[j]<tmp[j];
					break;
				}
			if(!fl)
			{
				b[idx[i]]=0;
				for(int j=1;j<=m;j++) cur[j]^=a[i][j];
			}
		}
		return true;
	}
}

int main()
{
	pw[0]=1;
	for(int i=1;i<=S*S-3;i++) pw[i]=1ll*pw[i-1]*2%p;
	inv[S*S-3]=qpow(pw[S*S-3],p-2);
	for(int i=S*S-3;i>=1;i--) inv[i-1]=1ll*inv[i]*2%p;
	ppw[0]=2;
	for(int i=1;i<=S-3;i++) ppw[i]=1ll*ppw[i-1]*ppw[i-1]%p;
	freopen("basis.in","r",stdin);
	freopen("basis.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	if(!init::input()) return 0;
	if(b[1]!=1) return cout<<"0\n",0;
	h[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=i-1;j++)
			add(h[i][j],1ll*h[i-1][j]*pw[j]%p),
			add(h[i][j+1],h[i-1][j]);
	c[n]=1;
	for(int i=n-1;i>=0;i--)
		for(int j=i+1;j<=n;j++) add(c[i],p-1ll*c[j]*h[n-i][j-i]%p);
	for(int i=1;i<=n;i++) f[0][i][0][0]=c[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=n-i+1;j++)
			for(int k=0;k<=1;k++)
			{
				int f0=f[i-1][j][0][k],f1=f[i-1][j][1][k],f2=f[i-1][j][2][k];
				// 0->0
				if(b[i]==0||k!=0) add(f[i][j][0][k],f0); // no
				if(j>0) // yes
				{
					if(b[i]==0) add(f[i][j-1][0][1],1ll*f0*(k==0?1:pw[n-i-(j-1)])%p);
					else        add(f[i][j-1][0][1],1ll*f0*(k==0?1:pw[n-i-(j-1)])%p*ppw[j-1]%p);
				}
				// 0->1 or 0->2
				if(b[i]==1)
				{
					// 0->1(yes)
					if(j>0) add(f[i][j-1][1][1],1ll*f0*(k==0?1:pw[n-i-(j-1)])%p);
					// 0->2(no)
					if(j<=n-i)
						add(f[i][j][2][k],1ll*f0*(k==0?1:pw[n-i-j])%p);
				}
				if(k==1) // 1 when k=1
				{
					// 1->1
					add(f[i][j][1][1],f1); // no
					if(b[i]==0&&j>0) // yes
						add(f[i][j-1][1][1],1ll*f1*pw[n-i-(j-1)]%p*ppw[j-1]%p);
					// 1->2(no)
					if(b[i]==0) add(f[i][j][2][1],1ll*f1*pw[n-i-j]%p);
				}
				// 2->2
				add(f[i][j][2][k],f2); // no
				if(j>0) add(f[i][j-1][2][1],1ll*f2*pw[n-i-(j-1)]%p*ppw[j-1]%p); // yes
			}
	}
	int ans=0;
	add(ans,f[n][0][0][1]);
	add(ans,f[n][0][2][0]);
	add(ans,f[n][0][2][1]);
	add(ans,c[0]);
	cout<<ans<<'\n';
	return 0;
}