正題

題目連結:https://www.luogu.com.cn/problem/CF1119H

題目大意

\(n\)個可重集，第\(i\)個裡有\(x\)個\(a_i\)，\(y\)個\(b_i\)，\(z\)個\(c_i\)。

對于每個\(t\in[0,2^k)\)求每個集合裡取出一個數使它們異或起來等于\(t\)的方案數。

解題思路

如果直接\(n\)個東西\(FWT\)起來肯定過不了，我們需要根據每個集合裡隻有三種數這個性質來優化。

因為是\(xor\)卷積，是以第\(i\)個位置\(FWT\)之後對\(j\)造成的影響是\((-1)^{cnt(i\&j)}\)（其中\(cnt(x)\)表示\(x\)在二進制下\(1\)的個數）

那麼就有

\[FWT(S_i)=\sum_{i=1}^{2^k-1}(-1)^{cnt(j\&a_i)}x+(-1)^{cnt(j\& b_i)}y+(-1)^{cnt(j\&b_i)}z

現在我們就可以單獨考慮每個\(x,y,z\)的貢獻了，然後每個\(FWT(S_i)[j]\)有\(8\)個狀态，為了友善我們縮減一下狀态先。

首先我們先讓所有的\(x\)都取到，也就是讓所有的\(b_i=b_i\ xor\ a_i,c_i=c_i\ xor\ a_i\)，然後詢問答案的時候我們再異或上一個\(a\)的異或和即可。

現在每個\(FWT(S_i)[j]\)有\(4\)種狀态，分别是\((x+y+z),(x+y-z),(x-y+z),(x-y-z)\)。定義這些狀态數量分别為\(a_1,a_2,a_3,a_4\)

我們先考慮集合\(i\)的每種狀态中\(y\)的影響\(F_i\)，有\(F_i[k]=cnt(k\& a_i)\)，而所有集合的影響和就是\(\sum_{i=1}^nF_i\)。設\(G_i=IFWT(F_i)\)那麼顯然有\(G_i[b_i]=1\)其他都為\(0\)。

然後影響和就是

\[\sum_{i=1}^nFWT(G_i)=FWT(\sum_{i=1}^nG_i)

是以直接把\(G\)都加起來然後\(FWT\)就好了，定義\(y\)的影響為\(c_1\)。

然後再同理搞出\(z\)和\(y+z\)的影響，分别為\(c_2,c_3\)，那麼就有方程組

\[\left\{\begin{matrix}

a_1+a_2+a_3+a_4=n\\

a_1+a_2-a_3-a_4=c_1\\

a_1-a_2+a_3-a_4=c_2\\

a_1-a_2-a_3+a_4=c_3

\end{matrix}\right.\]

解出來就好了，然後用快速幂算出來\(F=\prod_{i=1}^nFWT(S_i)\)，求一遍\(IFWT(F)\)即可。

時間複雜度\(O(\ 2^kk+n\log(x+y+z)\ )\)

\(code\)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=2e5+10,P=998244353;
const ll inv2=(P+1)/2;
ll n,k,x,y,z,xs;
ll f1[N],f2[N],f3[N],f[N];
ll power(ll x,ll b){
    ll ans=1;x%=P;
    while(b){
        if(b&1)ans=ans*x%P;
        x=x*x%P;b>>=1;
    }
    return ans;
}
void FWT(ll *f,ll n,ll op){
    for(ll p=2;p<=n;p<<=1)
        for(ll k=0,len=p>>1;k<n;k+=p)
            for(ll i=k;i<k+len;i++){
                ll x=f[i],y=f[i+len];
                if(op==1){
                    f[i]=x+y;
                    f[i+len]=x-y;
                }
                else{
                    f[i]=(x+y)*inv2%P;
                    f[i+len]=(x-y)*inv2%P;
                }
            }
    return;
}
signed main()
{
    scanf("%lld%lld",&n,&k);k=1<<k;
    scanf("%lld%lld%lld",&x,&y,&z);
    for(ll i=1;i<=n;i++){
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        xs^=a;b^=a;c^=a;
        f1[b]++;f2[c]++;f3[b^c]++;
    }
    FWT(f1,k,1);FWT(f2,k,1);FWT(f3,k,1);
    for(ll i=0;i<k;i++){
        ll c1=f1[i],c2=f2[i],c3=f3[i];
        ll a1,a2,a3,a4;
        a4=(c3-c1-c2+n)/4;
        a3=-(c1-n+2ll*a4)/2;
        a2=-(c2-n+2ll*a4)/2;
        a1=n-a2-a3-a4;
        f[i]=power(x+y+z,a1)%P*power(x+y-z,a2)%P;
        f[i]=f[i]*power(x-y+z,a3)%P*power(x-y-z,a4)%P;
    }
    FWT(f,k,-1);
    for(ll i=0;i<k;i++)
        printf("%lld ",(f[i^xs]+P)%P);
    return 0;
}

CF1119H-Triple【FWT】

正題

題目大意

解題思路

\(code\)