题解 CF1336E2 【Chiori and Doll Picking (hard version)】

求出这 $n$ 个数的线性基 $A$，假设线性基的秩为 $k$。 为了简洁，用 $|x|$ 表示 $x$ 二进制下 $1$ 的个数，即 $\text{ popcount }(x)$。 定义 $F_c=\{x:|x|=c,x<2^m\},(x,y) =|x\& y|$。 原问题即可转化求成 $2^{n-k}\times \sum_{x\in F_c}[x\in A]$，下面先不考虑前面的常数项。 构造 $B=\{y:\forall x\in A,(x,y)\equiv 0\pmod 2\}$ ，则有： $$ [x\in A]=\frac{1}{|B|}\sum_{y}(-1)^{(x,y)}[y\in B] $$ $$ \sum_{x\in F_c}[x\in A]=\frac{1}{|B|}\sum_y[y\in B](\sum_{x\in F_c}(-1)^{(x,y)}) $$ 考虑最后一项的取值： $$ \sum_{x\in F_c}(-1)^{(x,y)}=\sum_{x\in F_c}\sum_{(x,y)=k}(-1)^k\binom{|y|}{k}\binom{m-|y|}{|x|-k} $$ 可以发现这个取值只和 $|y|$ 有关，因此可以预处理出 $w_{c,d}=\sum_{x\in F_c}(-1)^{(x,y)}(c=|x|,d=|y|)$ 。 接下来构造 $B$，一个构造方法是先将 $A$ 消元成每个主元列只有一个 $1$，然后转置并交换所有的主元和非主元。  可以发现，对于 $A$ 中的一个基向量 $x$ 和 $B$ 中的一个基向量 $y$，只有当 $y$ 的主元对应到 $x$ 上的那一位为 $1$ 的时候才有 $(x,y)=2$，否则恒有 $(x,y)=0$。 因为 $|x\&z|+|y\&z|\equiv|(x\oplus y)\&z|\pmod 2$ ，而 $A$ 或 $B$ 能表示出的每个数都可以拆成若干的基向量的异或和，因此这就保证了 $(x,y)\equiv 0\pmod 2$ 对于 $x\in A,y\in B$ 恒成立。 并且，因为 $B$ 的每个主元列上只有一个 $1$，所以 $B$ 内的每个向量都线性无关，即 $B$ 是一个秩为 $m-k$ 的线性基。 那么可以在 $O(2^{m-k})$ 的时间内求出所有的 $y\in B$，结合预处理的 $w$ 就可以计算答案了。 如果 $k$ 较小，可以 $O(2^k)$ 枚举所有 $x\in A$ 并计算答案，如果 $k$ 较大，则可以按上述方法在 $O(2^{m-k})$ 的时间内计算答案。 取两者中较快的方法求解，即可达到 $O(nm+2^{m/2})$ 的总复杂度，可以通过全部的测试点。 P.S. 一组线性基对应一个线性空间，$B$ 就是 $A$ 在 $m$ 维空间中的正交，因为在这里每一维的取值都只有 $0,1$ 两种，所以 $B$ 是唯一的。（不唯一的时候，其余的正交空间都与 $B$ 线性相关） ```cpp #include<bits/stdc++.h> using namespace std; #define I inline int #define V inline void #define ll long long int #define cnt(x) __builtin_popcountll(x) #define FOR(i,a,b) for(int i=a;i<=b;i++) #define ROF(i,a,b) for(int i=a;i>=b;i--) const int N=2e5+1,M=64,mod=998244353; V check(int&x){x-=mod,x+=x>>31&mod;} int n,k,m,tot; ll a[N],f[M],g[M],t[M]; int ans[M],tmp[M],pw[N],c[M][M],w[M][M]; V ins(ll x){ ROF(i,m,0)if(x>>i&1){ if(f[i])x^=f[i]; else return f[i]=x,k++,void(); } } V dfs(int p,ll x){ if(p==tot)tmp[cnt(x)]++; else dfs(p+1,x),dfs(p+1,x^t[p]); } int main(){ cin.tie(0),cin>>n>>m,pw[0]=1,m--; FOR(i,1,n)cin>>a[i],ins(a[i]),check(pw[i]=pw[i-1]<<1); FOR(i,0,m)FOR(j,0,i-1)if(f[i]>>j&1)f[i]^=f[j]; if(k<=26){ FOR(i,0,m)if(f[i])t[tot++]=f[i]; dfs(0,0); FOR(i,0,m+1)cout<<1ll*pw[n-k]*tmp[i]%mod<<' '; } else{ FOR(i,0,m)FOR(j,0,m)g[j]|=(f[i]>>j&1)<<i; FOR(i,0,m)if(g[i]^=1ll<<i)t[tot++]=g[i]; k=++m-k,dfs(0,0); FOR(i,0,m)c[i][0]=1; FOR(i,1,m)FOR(j,1,m)check(c[i][j]=c[i-1][j]+c[i-1][j-1]); FOR(i,0,m)FOR(j,0,m)FOR(p,0,i) if(p&1)check(w[i][j]+=mod-1ll*c[j][p]*c[m-j][i-p]%mod); else check(w[i][j]+=1ll*c[j][p]*c[m-j][i-p]%mod); FOR(i,0,m)FOR(j,0,m) check(ans[i]+=1ll*tmp[j]*w[i][j]%mod); int tag=pw[max(0,n-m+k)]; FOR(i,1,k)tag=1ll*(mod+1>>1)*tag%mod; FOR(i,0,m)cout<<1ll*ans[i]*tag%mod<<' '; } return 0; } ```