法嘛塔和sos dp说的都是子集前/后缀和，用来求解一类这样的问题 :
给出\(g\)，求
\[f(S)=\bigoplus_{T\subseteq S}g(T)\]，其中\(\oplus\)是任意交换律、结合律运算。
为什么要交换律?因为子集的枚举顺序很多，法嘛塔也不知道你要的是哪一种，并且一般情况下我们用到的运算都有交换律。
我的板子习惯和法法塔类似，写起来大概是
1
2
3
4
5
6
7
for(int l=2;l<=n;l<<=1)
{
int mid=l>>1;
for(int p=0;p<n;p+=l)
for(int i=0;i<mid;i++)
mod(A[p+mid+i]+=A[p+i]);//+ can be replaced by some operator you want
}
上面是子集前缀和，要求子集后缀和(超集和)只要把+=两边的东西反过来即可。
这个东西的过程可以理解为，\(2^k\)构成一个\(k\)维的立方体，我们依次处理每一维之间的贡献。
考虑\(a,b\)相容，等价于\(b\in\operatorname{not}a\)。
我们记\(c_i\)为任意满足\(a_j=i\)的\(a_j\)，如果没有这样的\(a_j\)则\(c_i=-1\)。
对\(c\)做子集前缀和，当然这里的\(a\oplus b\)定义为 : 如果\(a,b\)有一个不是\(-1\)，结果是随便一个不是\(-1\)的，否则结果是\(-1\)。
我们得到的新的\(c_i\)的含义是\(c_i\)为任意满足\(a_j\in i\)的\(a_j\)，于是对于每个数\(a_i\)输出\(c_{\operatorname{not}a_i}\)即可。
注意到4s，所以\(O(\vert\Sigma\vert2^{\vert\Sigma\vert})\)完全能过。
把每个串状压成二进制，第\(i\)位是\(1\)当且仅当包含第\(i\)个字母。
每次询问要求有多少个单词包含元音字母集合的至少一个，你发现至少一个比较难受，不如反过来求一个也没有，然后用总数减去它。
一个也没有怎么求?跟上一题类似，就是求被 元音字母集合的补集 包含的单词个数。
设\(c_i\)表示有多少个单词状态是\(i\)，做子集前缀和(\(\oplus=+\))之后就变成了有多少字母被\(i\)包含。每次询问直接输出答案即可。
我读错题/cy以为是构造方案/cy
显然是个背包，就是把所有\(z^U+z^{a_i}\)卷起来，当然\(U\)是全集。
直接卷复杂度是\(O(nv\log v)\)，这很不好。
对每一个生成函数先进行一次FMT，然后直接拿点值扔进去卷，复杂度还是\(O(nv\log v)\)/jy，瓶颈在于求每一个FMT。
不过这个生成函数很简单，我们说不定可以直接求出它的FMT的结果。
你发现这个结果可以这么算 : 一开始全初始化成\(0\)，然后\(U\)的所有子集\(+1\)，然后\(a_i\)的所有子集\(+1\)，这显然可以\(O(v)\)求。所以我们就可以\(O(nv)\)了。
可是这还是太慢了!
继续考虑上面的性质。更进一步，我们知道每次加入一个新的数\(a_i\)，就是把原来的点值先抄过来，然后对于\(a_i\)的所有子集给它们翻倍，打上一个子集翻倍的tag即可。
打完之后做一遍FMT超集和来推标记，就得到了所有生成函数卷起来的点值，所以再一遍逆FMT就可以得到答案。复杂度是\(O(n+v\log v)\)。
这个题意还挺离谱。
那个\(G(x)\)外面的\(x\)一看就知道是为了减小输出量加上的东西，所以我们可以先去掉它，最后再处理。
看到是十进制!最小值!你就知道是k进制法嘛塔!
k进制法嘛塔怎么做?
还是从小到大按位处理，我们假设当前处理到\(k\)位，那么所有\(k\)位较小的应该贡献给较大的，你发现这是一个前缀和，做就好了。复杂度应该是\(O(n\log n)\)。
诶等等，这个题怎么带个平方啊???
你发现法嘛塔是个合并的过程，并且它还是不交并，这让人不禁想到在线段树上我们怎么维护平方和。呃不管想不想的到，差不多就那意思（
考虑合并\(A,B\)之后多出来的贡献就是选一个\(a\subseteq A,b\subseteq B\)，然后\(a+b\)的贡献，不妨记为\((a+b)^2\)，可以写成这样 :
\[\begin{aligned} &\sum_{a\subseteq A}\sum_{b\subseteq B}(a+b)^2\\ =&\sum_{a\subseteq A}\sum_{b\subseteq B}(a^2+b^2+2ab)\\ =&\sum_{a\subseteq A}\sum_{b\subseteq B}a^2+\sum_{a\subseteq}\sum_{b\subseteq B}b^2+\sum_{a\subseteq A}\sum_{b\subseteq B}2ab\\ =&\left(\sum_{a\subseteq A}a^2\right)\left(\sum_{b\subseteq B}b^0\right)+\left(\sum_{a\subseteq A}a^0\right)\left(\sum_{b\subseteq B}b^2\right)+2\left(\sum_{a\subseteq A}a\right)\left(\sum_{b\subseteq B}b\right) \end{aligned}\]前面两个就是我们维护的\(2\)次方和乘\(0\)次方和，后面就是维护的\(1\)次方和的积。做完了。
另外对于k进制位运算卷积(\(\operatorname{and}\)是取\(\min\)，\(\operatorname{or}\)是取\(\max\)，\(\operatorname{xor}\)是加起来膜\(k\))，除了\(\operatorname{xor}\)以外跟二进制的推导几乎相同，可以很容易地用上面的k进制法嘛塔解决。至于\(\operatorname{xor}\)怎么做……那就是高维法法塔的工作了，这里不提!
算了还是提一下吧。考虑把每一位拆开，从低位到高位计算，那么每一位相当于一个膜\(z^k\)的循环卷积，用Bluestein硬算即可。类似于左偏树线性建树的复杂度，可以知道这个算法的复杂度是\(O(n\log n)\)，当然这里视\(k=O(1)\)。
不过卷积比起\(\min/\max\)卷积性质太差了，搬到上一个题看起来并不可做。
奇怪边权的完全图求MST，当然想到Boruvka别乳卡。问题变成，对于每个连通块，查询从连通块内选一个点，块外选一个点，可以得到的\(\operatorname{and}\)的最大值。
法嘛塔。对于每个值做子集后缀和，求出最多两个不同的包含它的连通块，一个简单方法是求出最大编号和最小编号的连通块。
这样我们扫过每个点，进行按位贪心，看其它连通块的点和这个点\(\operatorname{and}\)起来的最大值，并更新这个连通块的出边。
这样进行\(\log n\)轮之后一定会停止，所以复杂度就是\(O((n+v)\log n\log v)\)。
实际上使用Kruskal也是可以的，这是一种类似法嘛塔，但是又不完全是的做法。
考虑一开始每个点都是一个独立的连通块，接下来我们需要从大到小枚举一个边权\(w\)，然后在连通块之间找边权是\(w\)的边并合并连通块。
当我们枚举到\(w\)的时候，所有\(>w\)的边都连完了，所以所有点权真包含\(w\)的点已经连成了一个连通块，那么我们只需要枚举二进制恰好比\(w\)多一个\(1\)的权值们的超集，然后如果这些连通块不是同一个连通块，我们试图合并它们。
这启发我们做一些奇怪的操作。一开始我们把点权是\(i\)的点存在\(a_i\)这个位置。然后枚举一个\(w\)，枚举\(w\operatorname{or}2^i\)以得到需要合并的连通块，然后用并查集合并它们，最后再选一个代表元存在\(a_i\)。
注意一开始我们存的时候只能存一个点，不过这没有什么关系，因为点权相同的点之间连边是肯定不劣的，我们可以把这样的边连满，然后给每个点权选一个代表。
咕咕咕。