Discription

现在有 \(n\) 个物品，同时有 \(k\) 种属性，每个属性有其价值 \(w_i\)

每个物品的一种属性对应一个权值 \(a_{i,j}\in[0,2^m)\)

现在对于 \([0,2^m)\) 中的每个 \(x\) 求出

\[\sum\limits_{\{k_1,\dots k_n\}}\left[\oplus_{i=1}^n a_{i,k_i}=x\right]\prod_{i=1}^n w_{k_i} \]

\(n\le 10^5,m\le 16,m+k\le 20\)

Solution

“FWT 变换矩阵本来就是满秩的”

一种朴素的做法是求出每物品的每个属性所形成的集合幂级数暴力 \(\rm FWT\) 并将点值乘起来再还原

看起来还原的一步是不可少的，那么尝试加速求点值的部分

直接求得的 \([x^i]\rm FWT_{[1\sim n]}\) 的项数达到了 \(\Theta(n2^m)\) 级别，那么尝试对其分类，最直接的方式就是使用 \(\pm1\) 来表示点值系数的正负

更具体地，如果一个 \(i\) 的 \(\rm{FWT}\left(\sum_{j=1}^k x^{a_{i,j}}\right)\) 中系数表示法下的 \(k\) 个位置向点值表示法下的第 \(i\) 位贡献为 \(ctr_i\dots ctr_k\left(\forall \ i\in [1,k]\ ctr_i\in \{-1,1\}\right)\)，使用一个长度为 \(k\) 的二进制数字表示 \(ctr\) 数组，其中 \(ctr_i=-1\) 的位让 \(x\) 的第 \(i\) 为是 \(1\)

尝试对 \([0,2^m)\) 中的每个 \(i\) 维护长度为 \(2^k\) 的数组 \(cnt_i\)，其中 \(cnt_{i,j}\) 表示对点值表示法下位置 \(i\) 贡献状态为 \(j\) 的物品的数量

那么如果求出了 \(2^{m}\times 2^k\) 个 \(cnt_{i,j}\)，容易得到每个状态的 \(w_i\) 对该点值处的贡献和，快速幂再乘积即可得到正确点值

问题转化为了求所有的 \(cnt_{i,j}\)，一种常用的手段是找等量关系来解方程，为了简化问题，下面的讨论都只考虑对 \(\rm [x^q]FWT(ans)\) 处的 \(cnt\) 来展开

尝试取出 \(\{1,\dots k\}\) 的一个子集 \(T\)，设 \(b_i=\oplus_{j=1}^k a_{i,j}\)，写出其集合幂级数 \(\sum\limits_{i=1}^n {\rm{FWT}}\left(x^b_i\right)={\rm{FWT}}\left(\sum\limits_{i=1}^n x^{b_i}\right)\)

这里的和式变换是因为 \(\rm FWT\) 的过程中系数是统一的，也就是说\(\rm FWT\) 是线性变换，类似于可以使用一次函数进行 \(\rm Lagrange\) 插值

我们考察 \([x^q]{\rm{FWT}}\left(\sum\limits_{i=1}^n x^{b_i}\right)\) 和 \([x^T]{\rm{FWT}}\left(\sum\limits_{i=0}^{2^k-1} cnt_{q,i}x^i\right)\)，先看左边：

注意到 \(\oplus_{i=1}^n {\rm popcount}(a_i\&q)= {\rm popcount}\left(\left(\oplus_{i=1}^n a_i\right)\&q\right)\)

如果你不会证明

---

这个等量关系在 \(a_i,q\ge 1\) 的时候按二进制位拆开考虑即可，因为位之间独立，\(n=2\) 时讨论是 \(\exist q=a_i\) 与否即可

在 \(n>2\) 的时候可以令 \(a'_1=a_1\oplus a_2,[i\ge 2]a'_i=a_{i+1}\)，使用 \(n=2\) 的 RHS 把 LHS 两项缩成一项即可归到 \(n\leftarrow n-1\) 的子问题

---

所以根据 \(\rm FWT\) 的定义式子可以进行一些简单的和式变换：

\[\begin{aligned}&[x^q]{\rm{FWT}}\left(\sum\limits_{i=1}^n x^{b_i}\right)\\ \\&=\sum_{i=1}^n\prod_{j\in T}(-1)^{|a_{i,j}\&q|}\\ &=\sum_{s=0}^{2^{k}-1} cnt_{q,s}(-1)^{{\rm{popcount}}(s\&T)}\\ &=[x^T]{\rm{FWT}}\left(\sum\limits_{i=0}^{2^k-1} cnt_{q,i}x^i\right)\end{aligned} \]

第二行到第三行是发生了统计方式的转化：原来是逐物品枚举，同时将 \(T\) 包含的，给 \(q\) 点值有 \(-1\) 贡献的 \(j\) 给予 \(-1\) 贡献，而第三行不过是分类枚举，但是仍然强制在 \(T\) 集合内的 \(j\) 才能产生 \(-1\) 贡献，因此根据实际含义找到了这样一组等量关系

事已至此，时间复杂度 \(\Theta\left(2^{k}(n+m2^m)\right)\)

Sample Code

const int N=1e5+10,MaxS=1<<16;
int n,m,k,w[10],tas[N][10],sw[100];
vector c[MaxS];
signed main(){
    n=read(); m=read(); k=read();
    int U=1< ans; ans.resize(U);
    rep(i,1,k) w[i]=read();
    rep(i,1,n) rep(j,1,k) tas[i][j]=read();
    
    int S=1<>(j-1)&1) ckdel(sw[i],w[j]); 
            else ckadd(sw[i],w[j]);
        }
    }
    for(int i=0;i f; f.resize(U);
        for(int j=1;j<=n;++j){
            int xsum=0;
            for(int e=1;e<=k;++e) if(i>>(e-1)&1){
                xsum^=tas[j][e];
            }
            f[xsum]++;
        }
        FWT(f,U,1);
        for(int j=0;j