CF1119H Triple

· · 题解

传送门

首先一个显然的做法是直接 FWT。

设 F_{i,j}=FWT(f_i)_j，其中 f_i 是只有 a_i,b_i,c_i 三项分别是 x,y,z 的数组。设 g_i=\prod\limits_{j=1}^n F_{j,i}，则答案就是 IFWT(g)。

由于 f_i 非零项很少，考虑手动 FWT。

由于 FWT 是线性变换，所以 FWT(A+B)=FWT(A)+FWT(B)。

又由于 xor 卷积的变换系数是 (-1)^{|i\&j|}，所以 F_{i,j}=(-1)^{|j\&a_i|}x+(-1)^{|j\&b_i|}y+(-1)^{|j\&c_i|}z。

为了简便，可以将 \{a_i,b_i,c_i\} 变换为 \{0,a_i\oplus b_i,a_i\oplus c_i\}，最终答案 xor 上所有 a_i 即可。

考虑如何求 g。

g_j=\prod\limits_{i=1}^n[x+(-1)^{|j\&b_i|}y+(-1)^{|j\&c_i|}z]

枚举 y,z 的符号，问题转化为形如求有多少个 i，满足 (-1)^{|j\&b_i|}=1 且 (-1)^{|j\&c_i|}=1。

也就是 \sum\limits_{i=1}^n[(-1)^{|j\&b_i|}=1][(-1)^{|j\&c_i|}=1]。

注意到，[(-1)^x=1]=\frac{(-1)^x+1}{2}。

要求的就转化为 \frac 14\sum\limits_{i=1}^n[(-1)^{|j\&b_i|}+1][(-1)^{|j\&c_i|}+1]。

拆括号得：

\frac 14\sum\limits_{i=1}^n(-1)^{|j\&b_i|}(-1)^{|j\&c_i|}+\sum\limits_{i=1}^n(-1)^{|j\&b_i|}+\sum\limits_{i=1}^n(-1)^{|j\&c_i|}+n

注意到 (-1)^{|x\&a|}(-1)^{|x\&b|}=(-1)^{|x\&(a\oplus b)|}。

于是问题等价于求 \sum\limits_{i=1}^n(-1)^{|j\&X_i|}。

设 h_{i,j}=(-1)^{|j\&X_i|}，w_{i,j}=[j=X_i]，则 h_{i}=FWT(w_i)。

要求的相当于 \sum\limits_{i=1}^nh_i，也就是 \sum\limits_{i=1}^n FWT(w_i)=FWT(\sum\limits_{i=1}^nw_i)。

于是，我们在 O(k2^k) 解决了该问题。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1.4e5+5,mods=998244353;
int pows(int a,int b){
    if(b==0)return 1;
    int res=pows(a,b>>1);
    res=res*res%mods;
    if(b&1)res=res*a%mods;
    return res;
}
int n,k,x,y,z,a[N],b[N],c[N],al,f[4][N];
void fwt(int*p,int n,int w00,int w01,int w10,int w11){
    for(int mid=1;mid<n;mid<<=1){
        for(int i=0;i<n;i+=mid<<1){
            for(int j=0;j<mid;j++){
                int t0=p[i+j],t1=p[i+j+mid];
                p[i+j]=(t0*w00+t1*w10)%mods;
                p[i+j+mid]=(t0*w01+t1*w11)%mods;
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k>>x>>y>>z;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
        b[i]^=a[i];c[i]^=a[i];
        al^=a[i];
        f[1][b[i]]++;
        f[2][c[i]]++;
        f[3][b[i]^c[i]]++;
    }
    fwt(f[1],1<<k,1,1,1,-1);
    fwt(f[2],1<<k,1,1,1,-1);
    fwt(f[3],1<<k,1,1,1,-1);
    for(int i=0;i<(1<<k);i++){
        int tmp00=(f[3][i]+f[2][i]+f[1][i]+n)/4,tmp01=(-f[3][i]-f[2][i]+f[1][i]+n)/4,tmp10=(-f[3][i]+f[2][i]-f[1][i]+n)/4,tmp11=(f[3][i]-f[2][i]-f[1][i]+n)/4;
        f[0][i]=pows((x+y+z)%mods,tmp00)*pows((x+y-z)%mods,tmp01)%mods*pows((x-y+z)%mods,tmp10)%mods*pows((x-y-z)%mods,tmp11)%mods;
    }
    fwt(f[0],1<<k,499122177,-499122176,499122177,-499122177);
    for(int i=0;i<(1<<k);i++)cout<<(f[0][i^al]%mods+mods)%mods<<" ";
}