正題

題目鏈接: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}^n{F}_i$。設$G_i=IFWT(F_i)$那么顯然有$G_i[b_i]=1$其他都為$0$。

然后影響和就是$$\sum _{i=1}^{n}FWT(G_i)=FWT(\sum _{i=1}^n{G}_i)$$
所以直接把$G$都加起來然后$FWT$就好了，定義$y$的影響為$c_1$。

然后再同理搞出$z$和$y+z$的影響，分別為$c_2,c_3$，那么就有方程組
$$?\begin{array}{c}{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{array}$$
解出來就好了，然后用快速冪算出來$F={\prod }_{i=1}^{n}FWT(S_i)$，求一遍$IFWT(F)$即可。

時間復雜度$O(2^{k}k+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】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。