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}$，其中$\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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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]);
}