正題

題目鏈接:https://www.luogu.com.cn/problem/P6097

---

題目大意

長(zhǎng)度為$2^n$的序列$a,b$求一個(gè)$c$滿足
$$c_k=\sum _{i|j=k,i\&j=?}{a}_i\times b_j$$

---

解題思路

從炫酷反演魔術(shù)過(guò)來(lái)的，順便寫掉這題

簡(jiǎn)單的說(shuō)就是求$k$的所有子集和其補(bǔ)集的乘積和。
只有$i|j=k$的話就是普通的$\text{FWT}$了，但是還有$i\&j=?$這個(gè)東西。
一個(gè)巧妙的想法是把這個(gè)條件轉(zhuǎn)換為$|i|+|j|=|i\cup j|$，顯然兩個(gè)之間是充要的。
然后可以把$a_i$存在$f_{ct(i),i}$這個(gè)位置，其中$ct(i)$表示$i$中$1$的個(gè)數(shù)。同理$b_i$存在$g_{ct(i),i}$這個(gè)位置。

然后就有卷積
$$h_{a,b}=\sum _{i+j=a,x|y=b}{f}_{i,x}\times g_{j,y}$$
這個(gè)先暴力$\text{FWT}$了$f,g$然后暴力卷積然后$\text{IFWT}$回去就好了。

時(shí)間復(fù)雜度$O(n^2{2}^n)$，不能全開(kāi)$\text{long?long}$不然會(huì)$\text{T}$的

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=21,P=1e9+9; int n,k,ct[1<<N],f[N][1<<N],g[N][1<<N],h[N][1<<N]; void FWT(int *f,int op){for(int p=2;p<=n;p<<=1)for(int k=0,len=p>>1;k<n;k+=p)for(int i=k;i<k+len;i++)(f[i+len]+=(f[i]*op+P)%P)%=P;return; } signed main() {// printf("%d",sizeof(f)>>20);scanf("%d",&k);n=(1<<k);for(int i=0;i<n;i++){if(i)ct[i]=ct[i-(i&-i)]+1;scanf("%d",&f[ct[i]][i]);}for(int i=0;i<n;i++)scanf("%d",&g[ct[i]][i]);for(int i=0;i<=k;i++)FWT(f[i],1),FWT(g[i],1);for(int i=0;i<=k;i++)for(int j=0;j<=i;j++)for(int x=0;x<n;x++)(h[i][x]+=1ll*f[j][x]*g[i-j][x]%P)%=P;for(int i=0;i<=k;i++)FWT(h[i],-1);for(int i=0;i<n;i++)printf("%d ",h[ct[i]][i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P6097-[模板]子集卷积的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。