题解 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\} ，则有：

考虑最后一项的取值：

可以发现这个取值只和 |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 线性相关）

#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;
}