https://wiki.cvbbacm.com/ 2026-04-30T07:43:53+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-05-09T21:36:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:alchemist:maxdumbledore:fft_ntt_fwt_ormore:subset_convolution&rev=1589031399&do=diff 子集卷积 简介 一般我们有如下一类的状压dp方程，如$dp[i]=\sum dp[j]*w[k]$ ($i,j,k$满足$j\lor k=i,j \land k=0$，这里符号表示按位与和按位或。 如果暴力枚举位的子集，那么效率是$3^n$的，难以承受。 实际上这个已经很接近一个FWT卷积的形式了，只不过是还要$j\land k=0$$j$$k$$i$$dp$$$ dp[cnt_i][i]=\sum_{(j|k)==i}dp[cnt_j][j]*w[cnt_i-cnt_j][k] $$$cnt_i$$cnt_i$$i$$dp$$w$$cnt$$dp$$dp[cnt_i]$$cnt_i$$dp$$n$$n^2$$O((2^n*n)*n+n^2*2^n)=O(n^2*2^n)$$i|j$$(i|j)+k$$((i|j)+k)\otimes h$…