CF Round #635 Div.1 Chiori and Doll Picking (hard version)

考虑对于 \(a_i\) 建立线性基 \(d\) ，并且通过高斯消元重整，使得 \(d\) 中 每一个元素的最高位 仅自己包含

不妨设 \(k=|d|\) ，一个基底的生成集合为 \(S(d)\) ，设 \(A=S(d)\) ，预处理部分复杂度为 \(O(nm+k^2)\)

\[ \ \]

根据线性基的基本性质，我们知道任何一个 \(x\in S(d)\) 有 \(2^{n-k}\) 种生成方法

因此我们只需要计算线性基元素异或的答案即可，这样我们将问题规模降低到了 \(k\)

\[ \ \]

\[ \ \]

暴力1

对于 \(k\leq 27\) ，暴力枚举每个元素是否选择，可以通过预处理让复杂度降至 \(O(2^k)\)

暴力2

\(m\leq 35，k>27\) 时

由于线性基包含 \(k\) 个关键01位， \(m-k\) 个非关键01位

通过高斯消元可以使得基的每一位仅包含一个关键01位

令 \(dp_{S,i}\) 表示选择了 \(i\) 个基，非关键01位异或和为 \(S\) 的方案数

复杂度为 \(O(2^{m-k}m^2)\)

---

对称暴力

由于 \(m\leq 53\) ，而我们能够暴力解决 \(k\leq 27\) ，则可以考虑剩下的 \(m-k\) 个位，想办法在 \(O(2^{m-k})\) 时间内求解

\[ \ \]

考虑计算个数为 \(c\) 的方案数，我们用一个卷积形式来描述，令 \(\displaystyle F_c(x)=\sum_{|T|=c}x^{T}\)

则容易发现 \(ans_c=[x^{\empty}](A\bigoplus F_c)\) ，其中 \(\bigoplus\) 表示 异或 (集合对称差) 卷积

显然我们需要 \(\text{FWT}\) 来计算这个东西，也就是计算

\([x^{\empty}]\text{FWT}(\text{FWT}(A)\cdot \text{FWT}(F_c))\)

先考虑比较复杂的 \(G=\text{FWT}(A)\) 的计算

下面你需要良好掌握 \(\text{FWT}\) ，参考

1: \(G(x)\) 中每一非零项系数为 \(2^k\)

考虑线性基 \(A\) 的元素是封闭的，则有 \(A\bigoplus A=A\cdot |A|\)

即 \(G\cdot G=G\cdot 2^k\) ，解方程得到 \([x^S]G\in\{0,2^k\}\)

2: \([x^S]G(x)=2^k\Longleftrightarrow \forall T,|S\cap T|\equiv 0\pmod 2\)

由 \(\text{FWT}\) 式子

\([x^S]G(x)=\sum (-1)^{|S\cap T|} [x^T]A(x)\)

而 \(A(x)\) 由 \(2^k\) 个1构成，故得结论

确定非零项

由恒等式 \(|X\cap S|+|Y\cap S|\equiv|(X\oplus Y)\cap S|\pmod 2\) ，得到简化

1.若 \(X,Y\) 对于 \(S\) 合法，则 \(X\oplus Y\) 同样合法，只需要考虑线性基 \(d\) 中元素对于 \(S\) 的限制

2.假设已知 \(S,T\) 非零，则 \(S\oplus T\) 非零，因此可以考虑用一个线性基 \(d'\) 来描述合法元素

确定 \(|d'|\) 大小

则 \(2^kS(d')=G\) ， \(\text{IFWT}(2^k\cdot S(d'))=A\)

带入两边 \(x^{\empty}\) 项的值，容易得到 \(|S(d')|=2^{m-k}\) ，故 \(|d'|=m-k\)

\(|d'|=m-k\) 是接近前面猜想的一大跳跃

构造 \(d'\) ?

考虑用0/1矩阵形式描述线性基 \(d\)

将 \(d\) 中的元素中的最高位移动到主对角线上最高的 \(k\) 个位置，此时每一行一定是一个主对角线元素后面跟上一些位置 \(\ge k+1\) 的元素

此时 \(d'\) 的构造即：主对角线取反，其余位置为转置

\(\color{blue} 1\)	0	0	\(\color{blue} 1\)	0
0	\(\color{blue} 1\)	0	0	\(\color{blue} 1\)
0	0	\(\color{blue} 1\)	\(\color{blue} 1\)	0
\(\color{red}1\)	0	\(\color{red}1\)	\(\color{red}1\)	0
0	\(\color{red}1\)	0	\(\color{red}1\)	\(\color{red}1\)

Proof:

显然这样构造出的 \(d'\) 元素最低位独立，因此不线性相关，只需要证明满足限制即可

首先 \(d_i\) 与 \(d'_j\) 在主对角线上无交，有交部分一定是一个主对角线元素与一个非主对角线元素交

若 \(d_{i}\) 与 \(d'_j\) 在 \(d_{i,j},d'_{j,j}\) 有交，则在其关于主对角线对称的位置 \(d_{i,i},d'_{i,j}\) 处同样有交

因此交都是成对出现的

\[ \ \]

\[ \ \]

---

由此我们可以在 \(2^{m-k}\) 时间内通过暴力枚举得到 \(G\) 中每个非零项

下面考虑 \(\text{FWT}(F^c)\) 的贡献的部分实际极其简单

可以根据 \(G\) 中每一项 \(x^S\) 的 \(|S|\) 确定 \(\text{FWT}(F^c)\)

\([x^S]\text{FWT}(F^c)=\sum_{|T|=c}(-1)^{|S\cup T|}\)

对于 \(G\) 中不同的 \(|S|\) 分类，对于 \(|T|=c\) ，枚举 \(|S\cup T|\) ，添加组合数系数即可计算贡献

注意最后求出的答案 \([x^{\empty}]\) 为对应项相乘之后求和除去 \(\text{IFWT}\) 的 \(2^k\)

复杂度为 \(O(2^{m-k}+m^3+nm)\)

const int N=210,P=998244353;

int n,m,c;
ll d[62],e[63],C[62][62],W[63][63];
ll qpow(ll x,ll k=P-2){
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

vector <int> Enum(ll *d){
	static ll a[N],S[1<<15],T[1<<15],bin[1<<15];
	int n=0,m;
	rep(i,0,61) if(d[i]) a[n++]=d[i];
	m=n/2;
	rep(i,0,m) bin[1<<i]=i;
	rep(i,1,(1<<m)-1) S[i]=S[i&(i-1)]^a[bin[i&-i]];
	rep(i,1,(1<<(n-m))-1) T[i]=T[i&(i-1)]^a[bin[i&-i]+m];
	vector <int> res(::m+1);
	int X=(1<<m)-1;
	rep(i,0,(1<<n)-1) res[__builtin_popcountll(S[i&X]^T[i>>m])]++;
	return res;
}

int main(){
	n=rd(),m=rd();
	rep(i,1,n) {
		ll x=rd<ll>();
		drep(i,m-1,0) if(x&(1ll<<i)) {
			if(!d[i]) {
				d[i]=x,c++;
				break;
			} else x^=d[i];
		}
	}
	if(c<=27) {
		n=qpow(2,n-c);
		vector <int> res=Enum(d);
		rep(i,0,m) res[i]=1ll*res[i]*n%P;
		rep(i,0,m) printf("%d ",res[i]);
		return 0;
	}
	rep(i,0,m) rep(j,*C[i]=1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
	rep(i,0,m) { // F_i变成j之后的变化
		rep(j,0,m) rep(k,0,min(i,j)) {
			W[i][j]=(W[i][j]+1ll*(k&1?-1:1)*C[j][k]*C[m-j][i-k])%P;
		}
	}
	rep(i,0,m-1) if(d[i]) rep(j,i+1,m) if(d[j]&(1ll<<i)) d[j]^=d[i];
	rep(i,0,m-1) if(d[i]) {
		rep(j,0,i-1) if(d[i]&(1ll<<j)) e[j]|=1ll<<i;
	} else e[i]|=1ll<<i;
	vector <int> t=Enum(e),ans(m+1);
	n=qpow(2,n-c+c-m+P-1);
	rep(i,0,m) rep(j,0,m) ans[i]=(ans[i]+1ll*W[i][j]*t[j])%P;
	rep(i,0,m) ans[i]=1ll*(ans[i]+P)*n%P;
	rep(i,0,m) printf("%d ",ans[i]);
}