2020-2021:teams:alchemist:maxdumbledore:fft_ntt_fwt_ormore:subset_convolution
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:maxdumbledore:fft_ntt_fwt_ormore:subset_convolution [2020/05/09 21:33] maxdumbledore 创建 |
2020-2021:teams:alchemist:maxdumbledore:fft_ntt_fwt_ormore:subset_convolution [2020/05/09 21:36] (当前版本) maxdumbledore ↷ 页面名由2020-2021:teams:alchemist:maxdumbledore:fft_ntt_fwt_ormore:子集卷积改为2020-2021:teams:alchemist:maxdumbledore:fft_ntt_fwt_ormore:subset_convolution |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ==== 子集卷积 ==== | + | ====== 子集卷积 ====== |
| - | === 简介 === | + | ==== 简介 ==== |
| 一般我们有如下一类的状压dp方程，如$dp[i]=\sum dp[j]*w[k]$ ($i,j,k$满足$j\lor k=i,j \land k=0$，这里符号表示按位与和按位或。 | 一般我们有如下一类的状压dp方程，如$dp[i]=\sum dp[j]*w[k]$ ($i,j,k$满足$j\lor k=i,j \land k=0$，这里符号表示按位与和按位或。 | ||
| 行 15: | 行 15: | ||
| 虽然牺牲了一定空间，但是时间被优化到了$n$次FWT+$n^2$次对位乘法的复杂度：$O((2^n*n)*n+n^2*2^n)=O(n^2*2^n)$。 | 虽然牺牲了一定空间，但是时间被优化到了$n$次FWT+$n^2$次对位乘法的复杂度：$O((2^n*n)*n+n^2*2^n)=O(n^2*2^n)$。 | ||
| - | === 例题 === | + | ==== 例题 ==== |
| 模板题：https:%%//%%ac.nowcoder.com/acm/contest/5157/D | 模板题：https:%%//%%ac.nowcoder.com/acm/contest/5157/D | ||
| - | 很容易从题目的形式看出来实际上就是对四个数列求三重卷积，第一重是$i|j$的子集卷积，第二重$(i|j)+k$的FFT/NTT，第三重是$((i|j)+k)\otimes h$的FWT的异或卷积。代码参考个人主页的子集卷积内容。 | + | 很容易从题目的形式看出来实际上就是对四个数列求三重卷积，第一重是$i|j$的子集卷积，第二重$(i|j)+k$的FFT/NTT，第三重是$((i|j)+k)\otimes h$的FWT的异或卷积。 |
| <code cpp> | <code cpp> | ||
2020-2021/teams/alchemist/maxdumbledore/fft_ntt_fwt_ormore/subset_convolution.1589031187.txt.gz · 最后更改: 2020/05/09 21:33 由 maxdumbledore
