Warning: session_start(): open(/tmp/sess_5b4dea30af5377e99d23ebeb255b0b22, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/4/43994124a9168f34c03db2ff7cd35d94.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 本周推荐 ======
===== 陈铭煊 Max.D. =====
==== 子集卷积 ====
=== 简介 ===
一般我们有如下一类的状压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$中1的个数+$k$中1的个数=$i$中1的个数，那么当我们为$dp$增加一个“1的个数”的维度时，问题迎刃而解： $$
dp[cnt_i][i]=\sum_{(j|k)==i}dp[cnt_j][j]*w[cnt_i-cnt_j][k]
$$ 注意这里$cnt_i$表示1的个数，或者说子集中的物品数目。这里$cnt_i$和$i$的二进制1的个数如果不等，这个$dp$或者$w$值会置为0。此时只要我们从小到大枚举$cnt$来做FWT就可以得到答案了，实际操作过程中，所有的$dp$都是点值形式，因此得到新的$dp[cnt_i]$只需要做$cnt_i$次对位乘；最后，再将所有的$dp$逆FWT变换回原值。
虽然牺牲了一定空间，但是时间被优化到了$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
很容易从题目的形式看出来实际上就是对四个数列求三重卷积，第一重是$i|j$的子集卷积，第二重$(i|j)+k$的FFT/NTT，第三重是$((i|j)+k)\otimes h$的FWT的异或卷积。代码参考个人主页的子集卷积内容。
===== 龙鹏宇 Hardict =====
==== 总结 ====
- 多组数据多组询问尽可能考虑预处理,在单个数容斥中一般$\mu(i) \neq 0$才有贡献,可以预处理进行优化
- 计算几何处理相同点可以$\pm epsilon$
==== 统计数列中上升子序列个数====
对应数列$\{a_{i}\}_{i=1}^{n}$
考虑一个dp转移:$f[n]=1+\sum_{1\leq i